OpenRaiser/Intern-Atlas huggingface dataset:
Counterexamples to the Low-Degree Conjecture
Venue: arXiv cs.CC 2020
Year: 2020

A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.
Model-driven Engineering of Safety and Security Systems: A Systematic Mapping Study
Venue: arXiv cs.SE 2020
Year: 2020

This paper presents a systematic mapping study on the model-driven engineering of safety and security concerns in systems. Integrated modeling and development of both safety and security concerns is an emerging field of research. Our mapping study provides an overview of the current state-of-the-art in this field. Through a rigorous and systematic process, this study carefully selected 95 publications out of 17,927 relevant papers published between 1992 and 2018. This paper then proposes and answers several relevant research questions about frequently used methods, development stages where these concerns are typically investigated in, or application domains. Additionally, we identify the community's preference for publication venues and trends.
Fork-Resilient Cross-Blockchain Transactions through Algebraic Topology
Venue: arXiv cs.DC 2020
Year: 2020

The cross-blockchain transaction (CBT) serves as a cornerstone for the next-generation, blockchain-based data management systems. However, state-of-the-art CBT models do not address the effect of the possible local fork suspension that might invalidate the entire CBT. This paper takes an algebraic-topological approach to abstract the blockchains and their transactions into simplicial complexes and shows that CBTs cannot complete in either a \textit{committed} or an \textit{aborted} status by a $t$-resilient message-passing protocol. This result implies that a more sophisticated model is in need to support CBTs and, thus, sheds light on the future blockchain designs.
Improving The Effectiveness of Automatically Generated Test Suites Using Metamorphic Testing
Venue: arXiv cs.SE 2020
Year: 2020

Automated test generation has helped to reduce the cost of software testing. However, developing effective test oracles for these automatically generated test inputs is a challenging task. Therefore, most automated test generation tools use trivial oracles that reduce the fault detection effectiveness of these automatically generated test cases. In this work, we provide results of an empirical study showing that utilizing metamorphic relations can increase the fault detection effectiveness of automatically generated test cases.
Effect of Text Color on Word Embeddings
Venue: arXiv cs.CV 2020
Year: 2020

In natural scenes and documents, we can find the correlation between a text and its color. For instance, the word, "hot", is often printed in red, while "cold" is often in blue. This correlation can be thought of as a feature that represents the semantic difference between the words. Based on this observation, we propose the idea of using text color for word embeddings. While text-only word embeddings (e.g. word2vec) have been extremely successful, they often represent antonyms as similar since they are often interchangeable in sentences. In this paper, we try two tasks to verify the usefulness of text color in understanding the meanings of words, especially in identifying synonyms and antonyms. First, we quantify the color distribution of words from the book cover images and analyze the correlation between the color and meaning of the word. Second, we try to retrain word embeddings with the color distribution of words as a constraint. By observing the changes in the word embeddings of synonyms and antonyms before and after re-training, we aim to understand the kind of words that have positive or negative effects in their word embeddings when incorporating text color information.
Decoder Error Propagation Mitigation for Spatially Coupled LDPC Codes
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we introduce two new methods of mitigating decoder error propagation for low-latency sliding window decoding (SWD) of spatially coupled low density parity check (SC-LDPC) codes. Building on the recently introduced idea of \emph{check node (CN) doping} of regular SC-LDPC codes, here we employ variable node (VN) doping to fix (set to a known value) a subset of variable nodes in the coupling chain. Both of these doping methods have the effect of allowing SWD to recover from error propagation, at a cost of a slight rate loss. Experimental results show that, similar to CN doping, VN doping improves performance by up to two orders of magnitude compared to undoped SC-LDPC codes in the typical signal-to-noise ratio operating range. Further, compared to CN doping, VN doping has the advantage of not requiring any changes to the decoding process.In addition, a log-likelihood-ratio based window extension algorithm is proposed to reduce the effect of error propagation. Using this approach, we show that decoding latency can be reduced by up to a significant fraction without suffering any loss in performance.
Self-Exploration in Complex Unknown Environments using Hybrid Map Representation
Venue: arXiv cs.RO 2020
Year: 2020

A hybrid map representation, which consists of a modified generalized Voronoi Diagram (GVD)-based topological map and a grid-based metric map, is proposed to facilitate a new frontier-driven exploration strategy. Exploration frontiers are the regions on the boundary between open space and unexplored space. A mobile robot is able to construct its map by adding new space and moving to unvisited frontiers until the entire environment has been explored. The existing exploration methods suffer from low exploration efficiency in complex environments due to the lack of a systematical way to determine and assign optimal exploration command. Leveraging on the abstracted information from the GVD map (global) and the detected frontier in the local sliding window, a global-local exploration strategy is proposed to handle the exploration task in a hierarchical manner. The new exploration algorithm is able to create a modified tree structure to represent the environment while consolidating global frontier information during the self-exploration. The proposed method is verified in simulated environments, and then tested in real-world office environments as well.
Color Image Segmentation using Adaptive Particle Swarm Optimization and Fuzzy C-means
Venue: arXiv cs.CV 2020
Year: 2020

Segmentation partitions an image into different regions containing pixels with similar attributes. A standard non-contextual variant of Fuzzy C-means clustering algorithm (FCM), considering its simplicity is generally used in image segmentation. Using FCM has its disadvantages like it is dependent on the initial guess of the number of clusters and highly sensitive to noise. Satisfactory visual segments cannot be obtained using FCM. Particle Swarm Optimization (PSO) belongs to the class of evolutionary algorithms and has good convergence speed and fewer parameters compared to Genetic Algorithms (GAs). An optimized version of PSO can be combined with FCM to act as a proper initializer for the algorithm thereby reducing its sensitivity to initial guess. A hybrid PSO algorithm named Adaptive Particle Swarm Optimization (APSO) which improves in the calculation of various hyper parameters like inertia weight, learning factors over standard PSO, using insights from swarm behaviour, leading to improvement in cluster quality can be used. This paper presents a new image segmentation algorithm called Adaptive Particle Swarm Optimization and Fuzzy C-means Clustering Algorithm (APSOF), which is based on Adaptive Particle Swarm Optimization (APSO) and Fuzzy C-means clustering. Experimental results show that APSOF algorithm has edge over FCM in correctly identifying the optimum cluster centers, there by leading to accurate classification of the image pixels. Hence, APSOF algorithm has superior performance in comparison with classic Particle Swarm Optimization (PSO) and Fuzzy C-means clustering algorithm (FCM) for image segmentation.
UDDSketch: Accurate Tracking of Quantiles in Data Streams
Venue: arXiv cs.DS 2020
Year: 2020

We present UDDSketch (Uniform DDSketch), a novel sketch for fast and accurate tracking of quantiles in data streams. This sketch is heavily inspired by the recently introduced DDSketch, and is based on a novel bucket collapsing procedure that allows overcoming the intrinsic limits of the corresponding DDSketch procedures. Indeed, the DDSketch bucket collapsing procedure does not allow the derivation of formal guarantees on the accuracy of quantile estimation for data which does not follow a sub-exponential distribution. On the contrary, UDDSketch is designed so that accuracy guarantees can be given over the full range of quantiles and for arbitrary distribution in input. Moreover, our algorithm fully exploits the budgeted memory adaptively in order to guarantee the best possible accuracy over the full range of quantiles. Extensive experimental results on synthetic datasets confirm the validity of our approach.
Optimization in Machine Learning: A Distribution Space Approach
Venue: arXiv cs.LG 2020
Year: 2020

We present the viewpoint that optimization problems encountered in machine learning can often be interpreted as minimizing a convex functional over a function space, but with a non-convex constraint set introduced by model parameterization. This observation allows us to repose such problems via a suitable relaxation as convex optimization problems in the space of distributions over the training parameters. We derive some simple relationships between the distribution-space problem and the original problem, e.g. a distribution-space solution is at least as good as a solution in the original space. Moreover, we develop a numerical algorithm based on mixture distributions to perform approximate optimization directly in distribution space. Consistency of this approximation is established and the numerical efficacy of the proposed algorithm is illustrated on simple examples. In both theory and practice, this formulation provides an alternative approach to large-scale optimization in machine learning.
Efficient Synthesis of Compact Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNNs) have been deployed in myriad machine learning applications. However, advances in their accuracy are often achieved with increasingly complex and deep network architectures. These large, deep models are often unsuitable for real-world applications, due to their massive computational cost, high memory bandwidth, and long latency. For example, autonomous driving requires fast inference based on Internet-of-Things (IoT) edge devices operating under run-time energy and memory storage constraints. In such cases, compact DNNs can facilitate deployment due to their reduced energy consumption, memory requirement, and inference latency. Long short-term memories (LSTMs) are a type of recurrent neural network that have also found widespread use in the context of sequential data modeling. They also face a model size vs. accuracy trade-off. In this paper, we review major approaches for automatically synthesizing compact, yet accurate, DNN/LSTM models suitable for real-world applications. We also outline some challenges and future areas of exploration.
Fully Parallel Mesh I/O using PETSc DMPlex with an Application to Waveform Modeling
Venue: arXiv cs.MS 2020
Year: 2020

Large-scale PDE simulations using high-order finite-element methods on unstructured meshes are an indispensable tool in science and engineering. The widely used open-source PETSc library offers an efficient representation of generic unstructured meshes within its DMPlex module. This paper details our recent implementation of parallel mesh reading and topological interpolation (computation of edges and faces from a cell-vertex mesh) into DMPlex. We apply these developments to seismic wave propagation scenarios on Mars as an example application. The principal motivation is to overcome single-node memory limits and reach mesh sizes which were impossible before. Moreover, we demonstrate that scalability of I/O and topological interpolation goes beyond 12'000 cores, and memory-imposed limits on mesh size vanish.
Are we pretraining it right? Digging deeper into visio-linguistic pretraining
Venue: arXiv cs.CV 2020
Year: 2020

Numerous recent works have proposed pretraining generic visio-linguistic representations and then finetuning them for downstream vision and language tasks. While architecture and objective function design choices have received attention, the choice of pretraining datasets has received little attention. In this work, we question some of the default choices made in literature. For instance, we systematically study how varying similarity between the pretraining dataset domain (textual and visual) and the downstream domain affects performance. Surprisingly, we show that automatically generated data in a domain closer to the downstream task (e.g., VQA v2) is a better choice for pretraining than "natural" data but of a slightly different domain (e.g., Conceptual Captions). On the other hand, some seemingly reasonable choices of pretraining datasets were found to be entirely ineffective for some downstream tasks. This suggests that despite the numerous recent efforts, vision & language pretraining does not quite work "out of the box" yet. Overall, as a by-product of our study, we find that simple design choices in pretraining can help us achieve close to state-of-art results on downstream tasks without any architectural changes.
Interactive Patch Filtering as Debugging Aid
Venue: arXiv cs.SE 2020
Year: 2020

It is widely recognized that program repair tools need to have a high precision to be useful, i.e., the generated patches need to have a high probability to be correct. However, it is fundamentally difficult to ensure the correctness of the patches, and many tools compromise other aspects of repair performance such as recall for an acceptable precision. In this paper we ask a question: can a repair tool with a low precision be still useful? To explore this question, we propose an interactive filtering approach to patch review, which filters out incorrect patches by asking questions to the developers. Our intuition is that incorrect patches can still help understand the bug. With proper tool support, the benefit outweighs the cost even if there are many incorrect patches. We implemented the approach as an Eclipse plugin tool, InPaFer, and evaluated it with a simulated experiment and a user study with 30 developers. The results show that our approach improve the repair performance of developers, with 62.5% more successfully repaired bugs and 25.3% less debugging time in average. In particular, even if the generated patches are all incorrect, the performance of the developers would not be significantly reduced, and could be improved when some patches provide useful information for repairing, such as the faulty location and a partial fix.
Code Review in the Classroom
Venue: arXiv cs.CY 2020
Year: 2020

This paper presents a case study to examine the affinity of the code review process among young developers in an academic setting. Code review is indispensable considering the positive outcomes it generates. However, it is not an individual activity and requires substantial interaction among stakeholders, deliverance, and acceptance of feedback, timely actions upon feedback as well as the ability to agree on a solution in the wake of diverse viewpoints. Young developers in a classroom setting provide a clear picture of the potential favourable and problematic areas of the code review process. Their feedback suggests that the process has been well received with some points to better the process. This paper can be used as guidelines to perform code reviews in the classroom.
Decision Problems in Information Theory
Venue: arXiv cs.IT 2020
Year: 2020

Constraints on entropies are considered to be the laws of information theory. Even though the pursuit of their discovery has been a central theme of research in information theory, the algorithmic aspects of constraints on entropies remain largely unexplored. Here, we initiate an investigation of decision problems about constraints on entropies by placing several different such problems into levels of the arithmetical hierarchy. We establish the following results on checking the validity over all almost-entropic functions: first, validity of a Boolean information constraint arising from a monotone Boolean formula is co-recursively enumerable; second, validity of "tight" conditional information constraints is in $Π^0_3$. Furthermore, under some restrictions, validity of conditional information constraints "with slack" is in $Σ^0_2$, and validity of information inequality constraints involving max is Turing equivalent to validity of information inequality constraints (with no max involved). We also prove that the classical implication problem for conditional independence statements is co-recursively enumerable.
BanFakeNews: A Dataset for Detecting Fake News in Bangla
Venue: arXiv cs.CL 2020
Year: 2020

Observing the damages that can be done by the rapid propagation of fake news in various sectors like politics and finance, automatic identification of fake news using linguistic analysis has drawn the attention of the research community. However, such methods are largely being developed for English where low resource languages remain out of the focus. But the risks spawned by fake and manipulative news are not confined by languages. In this work, we propose an annotated dataset of ~50K news that can be used for building automated fake news detection systems for a low resource language like Bangla. Additionally, we provide an analysis of the dataset and develop a benchmark system with state of the art NLP techniques to identify Bangla fake news. To create this system, we explore traditional linguistic features and neural network based methods. We expect this dataset will be a valuable resource for building technologies to prevent the spreading of fake news and contribute in research with low resource languages.
Mobility-Assisted Covert Communication over Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2020
Year: 2020

We study the effect of node mobility on the throughput scaling of the covert communication over a wireless adhoc network. It is assumed that $n$ mobile nodes want to communicate each other in a unit disk while keeping the presence of the communication secret from each of $Θ(n^s)$ non-colluding wardens ($s>0$). Our results show that the node mobility greatly improves the throughput scaling, compared to the case of fixed node location. In particular, for $0<s<1$, the aggregate throughput scaling is shown to be linear in $n$ when the number of channel uses that each warden uses to judge the presence of communication is not too large compared to $n$. For the achievability, we modify the two-hop based scheme by Grossglauser and Tse (2002), which was proposed for a wireless ad hoc network without a covertness constraint, by introducing a preservation region around each warden in which the senders are not allowed to transmit and by carefully analyzing the effect of covertness constraint on the transmit power and the resultant transmission rates. This scheme is shown to be optimal for $0<s<1$ under an assumption that each node outside preservation regions around wardens uses the same transmit power.
Role-Wise Data Augmentation for Knowledge Distillation
Venue: arXiv cs.LG 2020
Year: 2020

Knowledge Distillation (KD) is a common method for transferring the ``knowledge'' learned by one machine learning model (the \textit{teacher}) into another model (the \textit{student}), where typically, the teacher has a greater capacity (e.g., more parameters or higher bit-widths). To our knowledge, existing methods overlook the fact that although the student absorbs extra knowledge from the teacher, both models share the same input data -- and this data is the only medium by which the teacher's knowledge can be demonstrated. Due to the difference in model capacities, the student may not benefit fully from the same data points on which the teacher is trained. On the other hand, a human teacher may demonstrate a piece of knowledge with individualized examples adapted to a particular student, for instance, in terms of her cultural background and interests. Inspired by this behavior, we design data augmentation agents with distinct roles to facilitate knowledge distillation. Our data augmentation agents generate distinct training data for the teacher and student, respectively. We find empirically that specially tailored data points enable the teacher's knowledge to be demonstrated more effectively to the student. We compare our approach with existing KD methods on training popular neural architectures and demonstrate that role-wise data augmentation improves the effectiveness of KD over strong prior approaches. The code for reproducing our results can be found at https://github.com/bigaidream-projects/role-kd
DP-Cryptography: Marrying Differential Privacy and Cryptography in Emerging Applications
Venue: arXiv cs.CR 2020
Year: 2020

Differential privacy (DP) has arisen as the state-of-the-art metric for quantifying individual privacy when sensitive data are analyzed, and it is starting to see practical deployment in organizations such as the US Census Bureau, Apple, Google, etc. There are two popular models for deploying differential privacy - standard differential privacy (SDP), where a trusted server aggregates all the data and runs the DP mechanisms, and local differential privacy (LDP), where each user perturbs their own data and perturbed data is analyzed. Due to security concerns arising from aggregating raw data at a single server, several real world deployments in industry have embraced the LDP model. However, systems based on the LDP model tend to have poor utility - "a gap" in the utility achieved as compared to systems based on the SDP model. In this work, we survey and synthesize emerging directions of research at the intersection of differential privacy and cryptography. First, we survey solutions that combine cryptographic primitives like secure computation and anonymous communication with differential privacy to give alternatives to the LDP model that avoid a trusted server as in SDP but close the gap in accuracy. These primitives introduce performance bottlenecks and necessitate efficient alternatives. Second, we synthesize work in an area we call "DP-Cryptography" - cryptographic primitives that are allowed to leak differentially private outputs. These primitives have orders of magnitude better performance than standard cryptographic primitives. DP-cryptographic primitives are perfectly suited for implementing alternatives to LDP, but are also applicable to scenarios where standard cryptographic primitives do not have practical implementations. Through this unique lens of research taxonomy, we survey ongoing research in these directions while also providing novel directions for future research.