OpenRaiser/Intern-Atlas huggingface dataset:
Completeness in Polylogarithmic Time and Space
Venue: arXiv cs.LO 2020
Year: 2020

Complexity theory can be viewed as the study of the relationship between computation and applications, understood the former as complexity classes and the latter as problems. Completeness results are clearly central to that view. Many natural algorithms resulting from current applications have polylogarithmic time (PolylogTime) or space complexity (PolylogSpace). The classical Karp notion of complete problem however does not plays well with these complexity classes. It is well known that PolylogSpace does not have complete problems under logarithmic space many-one reductions. In this paper we show similar results for deterministic and non-deterministic PolylogTime as well as for every other level of the polylogarithmic time hierarchy. We achieve that by following a different strategy based on proving the existence of proper hierarchies of problems inside each class. We then develop an alternative notion of completeness inspired by the concept of uniformity from circuit complexity and prove the existence of a (uniformly) complete problem for PolylogSpace under this new notion. As a consequence of this result we get that complete problems can still play an important role in the study of the interrelationship between polylogarithmic and other classical complexity classes.
Aggregated Massive Modular Paradigm: A 6G Telecom Infrastructure Vision
Venue: arXiv cs.NI 2020
Year: 2020

On the eve of 5G network deployment worldwide, a new boom in the mass digitization of our personal and professional lifestyles is looming. 5G marks a strong shift in the way in which connectivity will impact our societies and industries. This shift is taking place through a combination of technologies that have progressed business-as-usual with technical improvements. The future of 5G, already called 6G, currently belongs to the world of research, which must imagine the future development of mobile digital services in 10 years. In this ever more connected world, ownership of data and protection, control of ecological impact, both energetic and electromagnetic, in addition to guarantee an available, flexible network will be essential factors in the success of 6G. This new generation of networks brings along great challenges in terms of modularity, cost effectiveness and power efficiency. We present here a novel disruptive deployment strategy using cost-efficient modules along with aggregated connectivity meeting these requirements.
Where's Crypto?: Automated Identification and Classification of Proprietary Cryptographic Primitives in Binary Code
Venue: arXiv cs.CR 2020
Year: 2020

The continuing use of proprietary cryptography in embedded systems across many industry verticals, from physical access control systems and telecommunications to machine-to-machine authentication, presents a significant obstacle to black-box security-evaluation efforts. In-depth security analysis requires locating and classifying the algorithm in often very large binary images, thus rendering manual inspection, even when aided by heuristics, time consuming. In this paper, we present a novel approach to automate the identification and classification of (proprietary) cryptographic primitives within binary code. Our approach is based on Data Flow Graph (DFG) isomorphism, previously proposed by Lestringant et al. Unfortunately, their DFG isomorphism approach is limited to known primitives only, and relies on heuristics for selecting code fragments for analysis. By combining the said approach with symbolic execution, we overcome all limitations of their work, and are able to extend the analysis into the domain of unknown, proprietary cryptographic primitives. To demonstrate that our proposal is practical, we develop various signatures, each targeted at a distinct class of cryptographic primitives, and present experimental evaluations for each of them on a set of binaries, both publicly available (and thus providing reproducible results), and proprietary ones. Lastly, we provide a free and open-source implementation of our approach, called Where's Crypto?, in the form of a plug-in for the popular IDA disassembler.
A Methodological Approach to Model CBR-based Systems
Venue: arXiv cs.AI 2020
Year: 2020

Artificial intelligence (AI) has been used in various areas to support system optimization and find solutions where the complexity makes it challenging to use algorithmic and heuristics. Case-based Reasoning (CBR) is an AI technique intensively exploited in domains like management, medicine, design, construction, retail and smart grid. CBR is a technique for problem-solving and captures new knowledge by using past experiences. One of the main CBR deployment challenges is the target system modeling process. This paper presents a straightforward methodological approach to model CBR-based applications using the concepts of abstract and concrete models. Splitting the modeling process with two models facilitates the allocation of expertise between the application domain and the CBR technology. The methodological approach intends to facilitate the CBR modeling process and to foster CBR use in various areas outside computer science.
Plant Diseases recognition on images using Convolutional Neural Networks: A Systematic Review
Venue: arXiv cs.CV 2020
Year: 2020

Plant diseases are considered one of the main factors influencing food production and minimize losses in production, and it is essential that crop diseases have fast detection and recognition. The recent expansion of deep learning methods has found its application in plant disease detection, offering a robust tool with highly accurate results. In this context, this work presents a systematic review of the literature that aims to identify the state of the art of the use of convolutional neural networks(CNN) in the process of identification and classification of plant diseases, delimiting trends, and indicating gaps. In this sense, we present 121 papers selected in the last ten years with different approaches to treat aspects related to disease detection, characteristics of the data set, the crops and pathogens investigated. From the results of the systematic review, it is possible to understand the innovative trends regarding the use of CNNs in the identification of plant diseases and to identify the gaps that need the attention of the research community.
Learning Slab Classes to Alleviate Memory Holes in Memcached
Venue: arXiv cs.DC 2020
Year: 2020

We consider the problem of memory holes in slab allocators, where an item entered into memory occupies more memory than it actually requires due to a difference between the nearest larger slab class size and the size of the entered item. We solve this problem by using a greedy algorithm that analyses the pattern of the sizes of items previously entered into the memory and accordingly re-configuring the default slab classes to better suit the learned traffic pattern to minimize memory holes. Using this approach for a consistent data pattern, in our findings, has yielded significant reductions in memory wastage. We consider Memcached as it is one of the most widely used implementations of slab allocators today, and has native support to reconfigure its default slab classes.
What Makes People Join Conspiracy Communities?: Role of Social Factors in Conspiracy Engagement
Venue: arXiv cs.SI 2020
Year: 2020

Widespread conspiracy theories, like those motivating anti-vaccination attitudes or climate change denial, propel collective action and bear society-wide consequences. Yet, empirical research has largely studied conspiracy theory adoption as an individual pursuit, rather than as a socially mediated process. What makes users join communities endorsing and spreading conspiracy theories? We leverage longitudinal data from 56 conspiracy communities on Reddit to compare individual and social factors determining which users join the communities. Using a quasi-experimental approach, we first identify 30K future conspiracists-(FC) and 30K matched non-conspiracists-(NC). We then provide empirical evidence of importance of social factors across six dimensions relative to the individual factors by analyzing 6 million Reddit comments and posts. Specifically in social factors, we find that dyadic interactions with members of the conspiracy communities and marginalization outside of the conspiracy communities, are the most important social precursors to conspiracy joining-even outperforming individual factor baselines. Our results offer quantitative backing to understand social processes and echo chamber effects in conspiratorial engagement, with important implications for democratic institutions and online communities.
Sensitivity Analysis of the Maximum Matching Problem
Venue: arXiv cs.DS 2020
Year: 2020

We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. Algorithms with low sensitivity are desirable because they are robust to edge failure or attack. In this work, we show a randomized $(1-ε)$-approximation algorithm with worst-case sensitivity $O_ε(1)$, which substantially improves upon the $(1-ε)$-approximation algorithm of Varma and Yoshida (arXiv 2020) that obtains average sensitivity $n^{O(1/(1+ε^2))}$ sensitivity algorithm, and show a deterministic $1/2$-approximation algorithm with sensitivity $\exp(O(\log^*n))$ for bounded-degree graphs. We show that any deterministic constant-factor approximation algorithm must have sensitivity $Ω(\log^* n)$. Our results imply that randomized algorithms are strictly more powerful than deterministic ones in that the former can achieve sensitivity independent of $n$ whereas the latter cannot. We also show analogous results for vertex sensitivity, where we remove a vertex instead of an edge. As an application of our results, we give an algorithm for the online maximum matching with $O_ε(n)$ total replacements in the vertex-arrival model. By comparison, Bernstein et al. (J. ACM 2019) gave an online algorithm that always outputs the maximum matching, but only for bipartite graphs and with $O(n\log n)$ total replacements. Finally, we introduce the notion of normalized weighted sensitivity, a natural generalization of sensitivity that accounts for the weights of deleted edges. We show that if all edges in a graph have polynomially bounded weight, then given a trade-off parameter $α>2$, there exists an algorithm that outputs a $\frac{1}{4α}$-approximation to the maximum weighted matching in $O(m\log_α n)$ time, with normalized weighted sensitivity $O(1)$. See paper for full abstract.
Development of a Predictive Process Design kit for15-nm FinFETs: FreePDK15
Venue: arXiv cs.AR 2020
Year: 2020

FinFETs are predicted to advance semiconductorscaling for sub-20nm devices. In order to support their intro-duction into research and universities it is crucial to develop anopen source predictive process design kit. This paper discussesin detail the design process for such a kit for 15nm FinFETdevices, called the FreePDK15. The kit consists of a layerstack with thirteen-metal layers based on hierarchical-scalingused in ASIC architecture, Middle-of-Line local interconnectlayers and a set of Front-End-of-Line layers. The physical andgeometrical properties of these layers are defined and theseproperties determine the density and parasitics of the design. Thedesign rules are laid down considering additional guidelines forprocess variability, challenges involved in FinFET fabrication anda unique set of design rules are developed for critical dimensions.Layout extraction including modified rules for determining thegeometrical characteristics of FinFET layouts are implementedand discussed to obtain successful Layout Versus Schematicchecks for a set of layouts. Moreover, additional parasiticcomponents of a standard FinFET device are analyzed andthe parasitic extraction of sample layouts is performed. Theseextraction results are then compared and assessed against thevalidation models.
Subscribing to Big Data at Scale
Venue: arXiv cs.DB 2020
Year: 2020

Today, data is being actively generated by a variety of devices, services, and applications. Such data is important not only for the information that it contains, but also for its relationships to other data and to interested users. Most existing Big Data systems focus on passively answering queries from users, rather than actively collecting data, processing it, and serving it to users. To satisfy both passive and active requests at scale, users need either to heavily customize an existing passive Big Data system or to glue multiple systems together. Either choice would require significant effort from users and incur additional overhead. In this paper, we present the BAD (Big Active Data) system, which is designed to preserve the merits of passive Big Data systems and introduce new features for actively serving Big Data to users at scale. We show the design and implementation of the BAD system, demonstrate how BAD facilitates providing both passive and active data services, investigate the BAD system's performance at scale, and illustrate the complexities that would result from instead providing BAD-like services with a "glued" system.
Emora: An Inquisitive Social Chatbot Who Cares For You
Venue: arXiv cs.CL 2020
Year: 2020

Inspired by studies on the overwhelming presence of experience-sharing in human-human conversations, Emora, the social chatbot developed by Emory University, aims to bring such experience-focused interaction to the current field of conversational AI. The traditional approach of information-sharing topic handlers is balanced with a focus on opinion-oriented exchanges that Emora delivers, and new conversational abilities are developed that support dialogues that consist of a collaborative understanding and learning process of the partner's life experiences. We present a curated dialogue system that leverages highly expressive natural language templates, powerful intent classification, and ontology resources to provide an engaging and interesting conversational experience to every user.
Accelerating High-Order Stencils on GPUs
Venue: arXiv cs.DC 2020
Year: 2020

Stencil computations are widely used in HPC applications. Today, many HPC platforms use GPUs as accelerators. As a result, understanding how to perform stencil computations fast on GPUs is important. While implementation strategies for low-order stencils on GPUs have been well-studied in the literature, not all of proposed enhancements work well for high-order stencils, such as those used for seismic modeling. Furthermore, coping with boundary conditions often requires different computational logic, which complicates efficient exploitation of the thread-level parallelism on GPUs. In this paper, we study high-order stencils and their unique characteristics on GPUs. We manually crafted a collection of implementations of a 25-point seismic modeling stencil in CUDA and related boundary conditions. We evaluate their code shapes, memory hierarchy usage, data-fetching patterns, and other performance attributes. We conducted an empirical evaluation of these stencils using several mature and emerging tools and discuss our quantitative findings. Among our implementations, we achieve twice the performance of a proprietary code developed in C and mapped to GPUs using OpenACC. Additionally, several of our implementations have excellent performance portability.
MicroGrad: A Centralized Framework for Workload Cloning and Stress Testing
Venue: arXiv cs.AR 2020
Year: 2020

We present MicroGrad, a centralized automated framework that is able to efficiently analyze the capabilities, limits and sensitivities of complex modern processors in the face of constantly evolving application domains. MicroGrad uses Microprobe, a flexible code generation framework as its back-end and a Gradient Descent based tuning mechanism to efficiently enable the evolution of the test cases to suit tasks such as Workload Cloning and Stress Testing. MicroGrad can interface with a variety of execution infrastructure such as performance and power simulators as well as native hardware. Further, the modular 'abstract workload model' approach to building MicroGrad allows it to be easily extended for further use. In this paper, we evaluate MicroGrad over different use cases and architectures and showcase that MicroGrad can achieve greater than 99\% accuracy across different tasks within few tuning epochs and low resource requirements. We also observe that MicroGrad's accuracy is 25 to 30\% higher than competing techniques. At the same time, it is 1.5x to 2.5x faster or would consume 35 to 60\% less compute resources (depending on implementation) over alternate mechanisms. Overall, MicroGrad's fast, resource efficient and accurate test case generation capability allow it to perform rapid evaluation of complex processors.
Adjusting Bias in Long Range Stereo Matching: A semantics guided approach
Venue: arXiv cs.CV 2020
Year: 2020

Stereo vision generally involves the computation of pixel correspondences and estimation of disparities between rectified image pairs. In many applications, including simultaneous localization and mapping (SLAM) and 3D object detection, the disparities are primarily needed to calculate depth values and the accuracy of depth estimation is often more compelling than disparity estimation. The accuracy of disparity estimation, however, does not directly translate to the accuracy of depth estimation, especially for faraway objects. In the context of learning-based stereo systems, this is largely due to biases imposed by the choices of the disparity-based loss function and the training data. Consequently, the learning algorithms often produce unreliable depth estimates of foreground objects, particularly at large distances~($>50$m). To resolve this issue, we first analyze the effect of those biases and then propose a pair of novel depth-based loss functions for foreground and background, separately. These loss functions are tunable and can balance the inherent bias of the stereo learning algorithms. The efficacy of our solution is demonstrated by an extensive set of experiments, which are benchmarked against state of the art. We show on KITTI~2015 benchmark that our proposed solution yields substantial improvements in disparity and depth estimation, particularly for objects located at distances beyond 50 meters, outperforming the previous state of the art by $10\%$.
Enhanced Quadratic Video Interpolation
Venue: arXiv cs.CV 2020
Year: 2020

With the prosperity of digital video industry, video frame interpolation has arisen continuous attention in computer vision community and become a new upsurge in industry. Many learning-based methods have been proposed and achieved progressive results. Among them, a recent algorithm named quadratic video interpolation (QVI) achieves appealing performance. It exploits higher-order motion information (e.g. acceleration) and successfully models the estimation of interpolated flow. However, its produced intermediate frames still contain some unsatisfactory ghosting, artifacts and inaccurate motion, especially when large and complex motion occurs. In this work, we further improve the performance of QVI from three facets and propose an enhanced quadratic video interpolation (EQVI) model. In particular, we adopt a rectified quadratic flow prediction (RQFP) formulation with least squares method to estimate the motion more accurately. Complementary with image pixel-level blending, we introduce a residual contextual synthesis network (RCSN) to employ contextual information in high-dimensional feature space, which could help the model handle more complicated scenes and motion patterns. Moreover, to further boost the performance, we devise a novel multi-scale fusion network (MS-Fusion) which can be regarded as a learnable augmentation process. The proposed EQVI model won the first place in the AIM2020 Video Temporal Super-Resolution Challenge.
Key-Point Sequence Lossless Compression for Intelligent Video Analysis
Venue: arXiv cs.MM 2020
Year: 2020

Feature coding has been recently considered to facilitate intelligent video analysis for urban computing. Instead of raw videos, extracted features in the front-end are encoded and transmitted to the back-end for further processing. In this article, we present a lossless key-point sequence compression approach for efficient feature coding. The essence of this predict-and-encode strategy is to eliminate the spatial and temporal redundancies of key points in videos. Multiple prediction modes with an adaptive mode selection method are proposed to handle key-point sequences with various structures and motion. Experimental results validate the effectiveness of the proposed scheme on four types of widely used key-point sequences in video analysis.
Large-scale nonlinear Granger causality: A data-driven, multivariate approach to recovering directed networks from short time-series data
Venue: arXiv cs.LG 2020
Year: 2020

To gain insight into complex systems it is a key challenge to infer nonlinear causal directional relations from observational time-series data. Specifically, estimating causal relationships between interacting components in large systems with only short recordings over few temporal observations remains an important, yet unresolved problem. Here, we introduce a large-scale Nonlinear Granger Causality (lsNGC) approach for inferring directional, nonlinear, multivariate causal interactions between system components from short high-dimensional time-series recordings. By modeling interactions with nonlinear state-space transformations from limited observational data, lsNGC identifies casual relations with no explicit a priori assumptions on functional interdependence between component time-series in a computationally efficient manner. Additionally, our method provides a mathematical formulation revealing statistical significance of inferred causal relations. We extensively study the ability of lsNGC to recovering network structure from two-node to thirty-four node chaotic time-series systems. Our results suggest that lsNGC captures meaningful interactions from limited observational data, where it performs favorably when compared to traditionally used methods. Finally, we demonstrate the applicability of lsNGC to estimating causality in large, real-world systems by inferring directional nonlinear, multivariate causal relationships among a large number of relatively short time-series acquired from functional Magnetic Resonance Imaging (fMRI) data of the human brain.
Analyze the Effects of Weighting Functions on Cost Function in the Glove Model
Venue: arXiv cs.CL 2020
Year: 2020

When dealing with the large vocabulary size and corpus size, the run-time for training Glove model is long, it can even be up to several dozen hours for data, which is approximately 500MB in size. As a result, finding and selecting the optimal parameters for the weighting function create many difficulties for weak hardware. Of course, to get the best results, we need to test benchmarks many times. In order to solve this problem, we derive a weighting function, which can save time for choosing parameters and making benchmarks. It also allows one to obtain nearly similar accuracy at the same given time without concern for experimentation.