OpenRaiser/Intern-Atlas huggingface dataset:
Entropy Guided Spectrum Based Bug Localization Using Statistical Language Model
Venue: arXiv cs.SE 2018
Year: 2018

Locating bugs is challenging but one of the most important activities in software development and maintenance phase because there are no certain rules to identify all types of bugs. Existing automatic bug localization tools use various heuristics based on test coverage, pre-determined buggy patterns, or textual similarity with bug report, to rank suspicious program elements. However, since these techniques rely on information from single source, they often suffer when the respective source information is inadequate. For instance, the popular spectrum based bug localization may not work well under poorly written test suite. In this paper, we propose a new approach, EnSpec, that guides spectrum based bug localization using code entropy, a metric that basically represents naturalness of code derived from a statistical language model. Our intuition is that since buggy code are high entropic, spectrum based bug localization with code entropy would be more robust in discriminating buggy lines vs. non-buggy lines. We realize our idea in a prototype, and performed an extensive evaluation on two popular publicly available benchmarks. Our results demonstrate that EnSpec outperforms a state-of-the-art spectrum based bug localization technique.
High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups
Venue: arXiv cs.LG 2018
Year: 2018

Bayesian optimization (BO) is a popular technique for sequential black-box function optimization, with applications including parameter tuning, robotics, environmental monitoring, and more. One of the most important challenges in BO is the development of algorithms that scale to high dimensions, which remains a key open problem despite recent progress. In this paper, we consider the approach of Kandasamy et al. (2015), in which the high-dimensional function decomposes as a sum of lower-dimensional functions on subsets of the underlying variables. In particular, we significantly generalize this approach by lifting the assumption that the subsets are disjoint, and consider additive models with arbitrary overlap among the subsets. By representing the dependencies via a graph, we deduce an efficient message passing algorithm for optimizing the acquisition function. In addition, we provide an algorithm for learning the graph from samples based on Gibbs sampling. We empirically demonstrate the effectiveness of our methods on both synthetic and real-world data.
Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps
Venue: arXiv cs.DS 2018
Year: 2018

We use soft heaps to obtain simpler optimal algorithms for selecting the $k$-th smallest item, and the set of~$k$ smallest items, from a heap-ordered tree, from a collection of sorted lists, and from $X+Y$, where $X$ and $Y$ are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the $k$-th smallest item, or the set of~$k$ smallest items, from a collection of~$m$ sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where $k_i$ is the number of items of the $i$-th list that belong to the overall set of~$k$ smallest items.
Combining Textual Content and Structure to Improve Dialog Similarity
Venue: arXiv cs.CL 2018
Year: 2018

Chatbots, taking advantage of the success of the messaging apps and recent advances in Artificial Intelligence, have become very popular, from helping business to improve customer services to chatting to users for the sake of conversation and engagement (celebrity or personal bots). However, developing and improving a chatbot requires understanding their data generated by its users. Dialog data has a different nature of a simple question and answering interaction, in which context and temporal properties (turn order) creates a different understanding of such data. In this paper, we propose a novelty metric to compute dialogs' similarity based not only on the text content but also on the information related to the dialog structure. Our experimental results performed over the Switchboard dataset show that using evidence from both textual content and the dialog structure leads to more accurate results than using each measure in isolation.
A 3D Game Theoretical Framework for the Evaluation of Unmanned Aircraft Systems Airspace Integration Concepts
Venue: arXiv cs.GT 2018
Year: 2018

Predicting the outcomes of integrating Unmanned Aerial Systems (UAS) into the National Airspace System (NAS) is a complex problem which is required to be addressed by simulation studies before allowing the routine access of UAS into the NAS. This paper focuses on providing a 3-dimensional (3D) simulation framework using a game theoretical methodology to evaluate integration concepts using scenarios where manned and unmanned air vehicles co-exist. In the proposed method, human pilot interactive decision making process is incorporated into airspace models which can fill the gap in the literature where the pilot behavior is generally assumed to be known a priori. The proposed human pilot behavior is modeled using dynamic level-k reasoning concept and approximate reinforcement learning. The level-k reasoning concept is a notion in game theory and is based on the assumption that humans have various levels of decision making. In the conventional "static" approach, each agent makes assumptions about his or her opponents and chooses his or her actions accordingly. On the other hand, in the dynamic level-k reasoning, agents can update their beliefs about their opponents and revise their level-k rule. In this study, Neural Fitted Q Iteration, which is an approximate reinforcement learning method, is used to model time-extended decisions of pilots with 3D maneuvers. An analysis of UAS integration is conducted using an example 3D scenario in the presence of manned aircraft and fully autonomous UAS equipped with sense and avoid algorithms.
Analysis of the XRP Ledger Consensus Protocol
Venue: arXiv cs.DC 2018
Year: 2018

The XRP Ledger Consensus Protocol is a previously developed consensus protocol powering the XRP Ledger. It is a low-latency Byzantine agreement protocol, capable of reaching consensus without full agreement on which nodes are members of the network. We present a detailed explanation of the algorithm and derive conditions for its safety and liveness.
How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts
Venue: arXiv cs.CR 2018
Year: 2018

We study secure and undetectable communication in a world where governments can read all encrypted communications of citizens. We consider a world where the only permitted communication method is via a government-mandated encryption scheme, using government-mandated keys. Citizens caught trying to communicate otherwise (e.g., by encrypting strings which do not appear to be natural language plaintexts) will be arrested. The one guarantee we suppose is that the government-mandated encryption scheme is semantically secure against outsiders: a perhaps advantageous feature to secure communication against foreign entities. But what good is semantic security against an adversary that has the power to decrypt? Even in this pessimistic scenario, we show citizens can communicate securely and undetectably. Informally, there is a protocol between Alice and Bob where they exchange ciphertexts that look innocuous even to someone who knows the secret keys and thus sees the corresponding plaintexts. And yet, in the end, Alice will have transmitted her secret message to Bob. Our security definition requires indistinguishability between unmodified use of the mandated encryption scheme, and conversations using the mandated encryption scheme in a modified way for subliminal communication. Our topics may be thought to fall broadly within the realm of steganography: the science of hiding secret communication in innocent-looking messages, or cover objects. However, we deal with the non-standard setting of adversarial cover object distributions (i.e., a stronger-than-usual adversary). We leverage that our cover objects are ciphertexts of a secure encryption scheme to bypass impossibility results which we show for broader classes of steganographic schemes. We give several constructions of subliminal communication schemes based on any key exchange protocol with random messages (e.g., Diffie-Hellman).
A Study into the similarity in generator and discriminator in GAN architecture
Venue: arXiv cs.LG 2018
Year: 2018

One popular generative model that has high-quality results is the Generative Adversarial Networks(GAN). This type of architecture consists of two separate networks that play against each other. The generator creates an output from the input noise that is given to it. The discriminator has the task of determining if the input to it is real or fake. This takes place constantly eventually leads to the generator modeling the target distribution. This paper includes a study into the actual weights learned by the network and a study into the similarity of the discriminator and generator networks. The paper also tries to leverage the similarity between these networks and shows that indeed both the networks may have a similar structure with experimental evidence with a novel shared architecture.
Inapproximability of Matrix $p\rightarrow q$ Norms
Venue: arXiv cs.CC 2018
Year: 2018

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been widely studied in various regimes. When $p \geq q$, the problem exhibits a dichotomy: constant factor approximation algorithms are known if $2 \in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 \notin [q,p]$. The regime when $p < q$, known as \emph{hypercontractive norms}, is particularly significant for various applications but much less well understood. The case with $p = 2$ and $q > 2$ was studied by [Barak et al, STOC'12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any $p < q$. We study the hardness of approximating matrix norms in both the above cases and prove the following results: - We show that for any $1< p < q < \infty$ with $2 \notin [p,q]$, $\|A\|_{p\rightarrow q}$ is hard to approximate within $2^{O(\log^{1-ε}\!n)}$ assuming $NP \not\subseteq BPTIME(2^{\log^{O(1)}\!n})$. This suggests that, similar to the case of $p \geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$. - For all $p \geq q$ with $2 \in [q,p]$, we show $\|A\|_{p\rightarrow q}$ is hard to approximate within any factor than $1/(γ_{p^*} \cdot γ_q)$, where for any $r$, $γ_r$ denotes the $r^{th}$ norm of a gaussian, and $p^*$ is the dual norm of $p$.
Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)
Venue: arXiv cs.LG 2018
Year: 2018

Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential and popular variants of MCMC for problems when an MCMC state consists of an unknown number of components. It is well known that state-of-the-art methods for split-merge MCMC do not scale well. Strategies for rapid mixing requires smart and informative proposals to reduce the rejection rate. However, all known smart proposals involve expensive operations to suggest informative transitions. As a result, the cost of each iteration is prohibitive for massive scale datasets. It is further known that uninformative but computationally efficient proposals, such as random split-merge, leads to extremely slow convergence. This tradeoff between mixing time and per update cost seems hard to get around. In this paper, we show a sweet spot. We leverage some unique properties of weighted MinHash, which is a popular LSH, to design a novel class of split-merge proposals which are significantly more informative than random sampling but at the same time efficient to compute. Overall, we obtain a superior tradeoff between convergence and per update cost. As a direct consequence, our proposals are around 6X faster than the state-of-the-art sampling methods on two large real datasets KDDCUP and PubMed with several millions of entities and thousands of clusters.
Spatial Morphing Kernel Regression For Feature Interpolation
Venue: arXiv cs.CV 2018
Year: 2018

In recent years, geotagged social media has become popular as a novel source for geographic knowledge discovery. Ground-level images and videos provide a different perspective than overhead imagery and can be applied to a range of applications such as land use mapping, activity detection, pollution mapping, etc. The sparse and uneven distribution of this data presents a problem, however, for generating dense maps. We therefore investigate the problem of spatially interpolating the high-dimensional features extracted from sparse social media to enable dense labeling using standard classifiers. Further, we show how prior knowledge about region boundaries can be used to improve the interpolation through spatial morphing kernel regression. We show that an interpolate-then-classify framework can produce dense maps from sparse observations but that care must be taken in choosing the interpolation method. We also show that the spatial morphing kernel improves the results.
An Information-Theoretical Analysis of the Minimum Cost to Erase Information
Venue: arXiv cs.IT 2018
Year: 2018

We normally hold a lot of confidential information in hard disk drives and solid-state drives. When we want to erase such information to prevent the leakage, we have to overwrite the sequence of information with a sequence of symbols independent of the information. The overwriting is needed only at places where overwritten symbols are different from original symbols. Then, the cost of overwrites such as the number of overwritten symbols to erase information is important. In this paper, we clarify the minimum cost such as the minimum number of overwrites to erase information under weak and strong independence criteria. The former (resp. the latter) criterion represents that the mutual information between the original sequence and the overwritten sequence normalized (resp. not normalized) by the length of the sequences is less than a given desired value.
Personal research information system. About developing the methods for searching patent analogs of invention
Venue: arXiv cs.DL 2018
Year: 2018

The article describes information model and the method for searching patent analogs for Personal Research Information System.
Collaboratively Weighting Deep and Classic Representation via L2 Regularization for Image Classification
Venue: arXiv cs.CV 2018
Year: 2018

Deep convolutional neural networks provide a powerful feature learning capability for image classification. The deep image features can be utilized to deal with many image understanding tasks like image classification and object recognition. However, the robustness obtained in one dataset can be hardly reproduced in the other domain, which leads to inefficient models far from state-of-the-art. We propose a deep collaborative weight-based classification (DeepCWC) method to resolve this problem, by providing a novel option to fully take advantage of deep features in classic machine learning. It firstly performs the L2-norm based collaborative representation on the original images, as well as the deep features extracted by deep CNN models. Then, two distance vectors, obtained based on the pair of linear representations, are fused together via a novel collaborative weight. This collaborative weight enables deep and classic representations to weigh each other. We observed the complementarity between two representations in a series of experiments on 10 facial and object datasets. The proposed DeepCWC produces very promising classification results, and outperforms many other benchmark methods, especially the ones claimed for Fashion-MNIST. The code is going to be published in our public repository.
"How to squash a mathematical tomato", Rubic's cube-like surfaces and their connection to reversible computation
Venue: arXiv cs.GR 2018
Year: 2018

Here we show how reversible computation processes, like Margolus diffusion, can be envisioned as physical turning operations on a 2-dimensional rigid surface that is cut by a regular pattern of intersecting circles. We then briefly explore the design-space of these patterns, and report on the discovery of an interesting fractal subdivision of space by iterative circle packings. We devise two different ways for creating this fractal, both showing interesting properties, some resembling properties of the dragon curve. The patterns presented here can have interesting applications to the engineering of modular, kinetic, active surfaces.
Learning to Synthesize
Venue: arXiv cs.SE 2018
Year: 2018

In many scenarios we need to find the most likely program under a local context, where the local context can be an incomplete program, a partial specification, natural language description, etc. We call such problem program estimation. In this paper we propose an abstract framework, learning to synthesis, or L2S in short, to address this problem. L2S combines four tools to achieve this: syntax is used to define the search space and search steps, constraints are used to prune off invalid candidates at each search step, machine-learned models are used to estimate conditional probabilities for the candidates at each search step, and search algorithms are used to find the best possible solution. The main goal of L2S is to lay out the design space to motivate the research on program estimation. We have performed a preliminary evaluation by instantiating this framework for synthesizing conditions of an automated program repair (APR) system. The training data are from the project itself and related JDK packages. Compared to ACS, a state-of-the-art condition synthesis system for program repair, our approach could deal with a larger search space such that we fixed 4 additional bugs outside the search space of ACS, and relies only on the source code of the current projects.
MIS in the Congested Clique Model in $O(\log \log Δ)$ Rounds
Venue: arXiv cs.DC 2018
Year: 2018

We give a maximal independent set (MIS) algorithm that runs in $O(\log \log Δ)$ rounds in the congested clique model, where $Δ$ is the maximum degree of the input graph. This improves upon the $O(\frac{\log(Δ) \cdot \log \log Δ}{\sqrt{\log n}} + \log \log Δ)$ rounds algorithm of [Ghaffari, PODC '17], where $n$ is the number of vertices of the input graph. In the first stage of our algorithm, we simulate the first $O(\frac{n}{\text{poly} \log n})$ iterations of the sequential random order Greedy algorithm for MIS in the congested clique model in $O(\log \log Δ)$ rounds. This thins out the input graph relatively quickly: After this stage, the maximum degree of the residual graph is poly-logarithmic. In the second stage, we run the MIS algorithm of [Ghaffari, PODC '17] on the residual graph, which completes in $O(\log \log Δ)$ rounds on graphs of poly-logarithmic degree.
Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
Venue: arXiv cs.CV 2018
Year: 2018

Sparse subspace clustering (SSC) is one of the current state-of-the-art methods for partitioning data points into the union of subspaces, with strong theoretical guarantees. However, it is not practical for large data sets as it requires solving a LASSO problem for each data point, where the number of variables in each LASSO problem is the number of data points. To improve the scalability of SSC, we propose to select a few sets of anchor points using a randomized hierarchical clustering method, and, for each set of anchor points, solve the LASSO problems for each data point allowing only anchor points to have a non-zero weight (this reduces drastically the number of variables). This generates a multilayer graph where each layer corresponds to a different set of anchor points. Using the Grassmann manifold of orthogonal matrices, the shared connectivity among the layers is summarized within a single subspace. Finally, we use $k$-means clustering within that subspace to cluster the data points, similarly as done by spectral clustering in SSC. We show on both synthetic and real-world data sets that the proposed method not only allows SSC to scale to large-scale data sets, but that it is also much more robust as it performs significantly better on noisy data and on data with close susbspaces and outliers, while it is not prone to oversegmentation.
Non-Malleable Codes for Small-Depth Circuits
Venue: arXiv cs.CC 2018
Year: 2018

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. $\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length $2^{O(\sqrt{k})}$. Our construction remains efficient for circuit depths as large as $Θ(\log(n)/\log\log(n))$ (indeed, our codeword length remains $n\leq k^{1+ε})$, and extending our result beyond this would require separating $\mathsf{P}$ from $\mathsf{NC^1}$. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.
ARRIVAL: Next Stop in CLS
Venue: arXiv cs.CC 2018
Year: 2018

We study the computational complexity of ARRIVAL, a zero-player game on $n$-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in $\text{NP} \cap \text{coNP}$. Karthik C. S. recently introduced a search variant of ARRIVAL and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of ARRIVAL. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of ARRIVAL is in $\text{UP} \cap \text{coUP}$. Second, we prove that the search variant of ARRIVAL is contained in CLS. Third, we give a randomized $\mathcal{O}(1.4143^n)$-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the ARRIVAL game, and (b) an efficient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The efficient sampling procedure yields the first algorithm for the problem that has expected runtime $\mathcal{O}(c^n)$ with $c<2$.