OpenRaiser/Intern-Atlas huggingface dataset:
Capacity of Discrete-Time Wiener Phase Noise Channels to Within a Constant Gap
Venue: arXiv cs.IT 2017
Year: 2017

The capacity of the discrete-time channel affected by both additive Gaussian noise and Wiener phase noise is studied. Novel inner and outer bounds are presented, which differ of at most $6.65$ bits per channel use for all channel parameters. The capacity of this model can be subdivided in three regimes: (i) for large values of the frequency noise variance, the channel behaves similarly to a channel with circularly uniform iid phase noise; (ii) when the frequency noise variance is small, the effects of the additive noise dominate over those of the phase noise, while (iii) for intermediate values of the frequency noise variance, the transmission rate over the phase modulation channel has to be reduced due to the presence of phase noise.
Local Modules in Imperative Languages
Venue: arXiv cs.PL 2017
Year: 2017

We propose a notion of local modules for imperative langauges. To be specific, we introduce a new implication statement of the form $D \supset G$ where $D$ is a module (i.e., a set of procedure declarations) and $G$ is a statement. This statement tells the machine to add $D$ to the program in the course of executing $G$. Thus, $D$ acts as a local module and will be discarded after executing $G$. It therefore provides efficient module management. We illustrate our idea via C^{mod}, an extension of the core C with the new statement. In addition, we describe a new constructive module language to improve code reuse. Finally, we describe a scheme which considerably improves the heap management in traditional languages.
On the Computational Complexity of Variants of Combinatorial Voter Control in Elections
Venue: arXiv cs.MA 2017
Year: 2017

Voter control problems model situations in which an external agent tries toaffect the result of an election by adding or deleting the fewest number of voters. The goal of the agent is to make a specific candidate either win (\emph{constructive} control) or lose (\emph{destructive} control) the election. We study the constructive and destructive voter control problems whenadding and deleting voters have a \emph{combinatorial flavor}: If we add (resp.\ delete) a voter~$v$, we also add (resp.\ delete) a bundle~$κ(v) $ of voters that are associated with~$v$. While the bundle~$κ(v)$ may have more than one voter, a voter may also be associated with more than one voter. We analyze the computational complexity of the four voter control problems for the Plurality rule. We obtain that, in general, making a candidate lose is computationally easier than making her win. In particular, if the bundling relation is symmetric (i.e.\ $\forall w\colon w \in κ(v) \Leftrightarrow v \in κ(w) $), and if each voter has at most two voters associated with him, then destructive control is polynomial-time solvable while the constructive variant remains $\NP$-hard. Even if the bundles are disjoint (i.e.\ $\forall w\colon w \in κ(v) \Leftrightarrow κ(v) = κ(w) $), the constructive problem variants remain intractable. Finally, the minimization variant of constructive control by adding voters does not admit an efficient approximation algorithm, unless P=NP.
Downlink Non-Orthogonal Multiple Access with Limited Feedback
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we analyze downlink non-orthogonal multiple access (NOMA) networks with limited feedback. Our goal is to derive appropriate transmission rates for rate adaptation and minimize outage probability of minimum rate for the constant-rate data service, based on distributed channel feedback information from receivers. We propose an efficient quantizer with variable-length encoding that approaches the best performance of the case where perfect channel state information is available everywhere. We prove that in the typical application with two receivers, the losses in the minimum rate and outage probability decay at least exponentially with the minimum feedback rate. We analyze the diversity gain and provide a sufficient condition for the quantizer to achieve the maximum diversity order. For NOMA with $K$ receivers where $K > 2$, we solve the minimum rate maximization problem within an accuracy of $ε$ in time complexity of $O\left(K\log\frac{1}ε\right)$, then, we apply the previously proposed quantizers for $K = 2$ to the case of $K > 2$. Numerical simulations are presented to demonstrate the efficiency of our proposed quantizers and the accuracy of the analytical results.
Range-efficient consistent sampling and locality-sensitive hashing for polygons
Venue: arXiv cs.CG 2017
Year: 2017

Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. min-wise hashing) to these point sets would require time proportional to the number of points. We seek to achieve time that is much lower than direct approaches. Technically, we introduce new primitives for range-efficient consistent sampling (of independent interest), and show how to turn such samples into LSH values. Another application of our technique is a data structure for quickly estimating the size of the intersection or union of a set of preprocessed polygons. Curiously, our consistent sampling method uses transformation to a geometric problem.
Randomized Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem
Venue: arXiv cs.DS 2017
Year: 2017

This paper studies randomized approximation algorithm for a variant of the set cover problem called minimum submodular cost partial multi-cover (SCPMC), in which each element $e$ has a covering requirement $r_e$ and a profit $p_e$, and the cost function on sub-collection of sets is submodular, the goal is to find a minimum cost sub-collection of sets which fully covers at least $q$-percentage of total profit, where an element $e$ is fully covered by sub-collection $S'$ if and only if it belongs to at least $r_e$ sets of $\mathcal S'$. Previous work shows that such a combination enormously increases the difficulty of studies, even when the cost function is linear. In this paper, assuming that the maximum covering requirement $r_{\max}=\max_e r_e$ is a constant and the cost function is nonnegative, monotone nondecreasing, and submodular, we give the first randomized bicriteria algorithm for SCPMC the output of which fully covers at least $(q-\varepsilon)$-percentage of all elements and the performance ratio is $O(b/\varepsilon)$ with a high probability, where $b=\max_e\binom{f}{r_{e}}$ and $f$ is the maximum number of sets containing a common element. The algorithm is based on a novel non-linear program. Furthermore, in the case when the covering requirement $r\equiv 1$, a bicriteria $O(f/\varepsilon)$-approximation can be achieved even when monotonicity requirement is dropped off from the cost function.
Pixel Objectness
Venue: arXiv cs.CV 2017
Year: 2017

We propose an end-to-end learning framework for generating foreground object segmentations. Given a single novel image, our approach produces pixel-level masks for all "object-like" regions---even for object categories never seen during training. We formulate the task as a structured prediction problem of assigning foreground/background labels to all pixels, implemented using a deep fully convolutional network. Key to our idea is training with a mix of image-level object category examples together with relatively few images with boundary-level annotations. Our method substantially improves the state-of-the-art on foreground segmentation for ImageNet and MIT Object Discovery datasets. Furthermore, on over 1 million images, we show that it generalizes well to segment object categories unseen in the foreground maps used for training. Finally, we demonstrate how our approach benefits image retrieval and image retargeting, both of which flourish when given our high-quality foreground maps.
The Power of Non-Determinism in Higher-Order Implicit Complexity
Venue: arXiv cs.CC 2017
Year: 2017

We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several authors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to cons-free programs taking data of order 0 does not increase expressivity; we prove that this - dramatically - is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets. Finally we show how, even with non-deterministic choice, the original hierarchy of characterisations is restored by imposing different restrictions.
FusionSeg: Learning to combine motion and appearance for fully automatic segmention of generic objects in videos
Venue: arXiv cs.CV 2017
Year: 2017

We propose an end-to-end learning framework for segmenting generic objects in videos. Our method learns to combine appearance and motion information to produce pixel level segmentation masks for all prominent objects in videos. We formulate this task as a structured prediction problem and design a two-stream fully convolutional neural network which fuses together motion and appearance in a unified framework. Since large-scale video datasets with pixel level segmentations are problematic, we show how to bootstrap weakly annotated videos together with existing image recognition datasets for training. Through experiments on three challenging video segmentation benchmarks, our method substantially improves the state-of-the-art for segmenting generic (unseen) objects. Code and pre-trained models are available on the project website.
Do Code Clones Matter?
Venue: arXiv cs.SE 2017
Year: 2017

Code cloning is not only assumed to inflate maintenance costs but also considered defect-prone as inconsistent changes to code duplicates can lead to unexpected behavior. Consequently, the identification of duplicated code, clone detection, has been a very active area of research in recent years. Up to now, however, no substantial investigation of the consequences of code cloning on program correctness has been carried out. To remedy this shortcoming, this paper presents the results of a large-scale case study that was undertaken to find out if inconsistent changes to cloned code can indicate faults. For the analyzed commercial and open source systems we not only found that inconsistent changes to clones are very frequent but also identified a significant number of faults induced by such changes. The clone detection tool used in the case study implements a novel algorithm for the detection of inconsistent clones. It is available as open source to enable other researchers to use it as basis for further investigations.
Optimizing Provenance Computations
Venue: arXiv cs.DB 2017
Year: 2017

Data provenance is essential for debugging query results, auditing data in cloud environments, and explaining outputs of Big Data analytics. A well-established technique is to represent provenance as annotations on data and to instrument queries to propagate these annotations to produce results annotated with provenance. However, even sophisticated optimizers are often incapable of producing efficient execution plans for instrumented queries, because of their inherent complexity and unusual structure. Thus, while instrumentation enables provenance support for databases without requiring any modification to the DBMS, the performance of this approach is far from optimal. In this work, we develop provenance specific optimizations to address this problem. Specifically, we introduce algebraic equivalences targeted at instrumented queries and discuss alternative, equivalent ways of instrumenting a query for provenance capture. Furthermore, we present an extensible heuristic and cost-based optimization (CBO) framework that governs the application of these optimizations and implement this framework in our GProM provenance system. Our CBO is agnostic to the plan space shape, uses a DBMS for cost estimation, and enables retrofitting of optimization choices into existing code by adding a few LOC. Our experiments confirm that these optimizations are highly effective, often improving performance by several orders of magnitude for diverse provenance tasks.
Synthetic to Real Adaptation with Generative Correlation Alignment Networks
Venue: arXiv cs.CV 2017
Year: 2017

Synthetic images rendered from 3D CAD models are useful for augmenting training data for object recognition algorithms. However, the generated images are non-photorealistic and do not match real image statistics. This leads to a large domain discrepancy, causing models trained on synthetic data to perform poorly on real domains. Recent work has shown the great potential of deep convolutional neural networks to generate realistic images, but has not utilized generative models to address synthetic-to-real domain adaptation. In this work, we propose a Deep Generative Correlation Alignment Network (DGCAN) to synthesize images using a novel domain adaption algorithm. DGCAN leverages a shape preserving loss and a low level statistic matching loss to minimize the domain discrepancy between synthetic and real images in deep feature space. Experimentally, we show training off-the-shelf classifiers on the newly generated data can significantly boost performance when testing on the real image domains (PASCAL VOC 2007 benchmark and Office dataset), improving upon several existing methods.
Deep Neural Networks - A Brief History
Venue: arXiv cs.NE 2017
Year: 2017

Introduction to deep neural networks and their history.
Jigsaw Cryptanalysis of Audio Scrambling Systems
Venue: arXiv cs.CR 2017
Year: 2017

Recently it was shown that permutation-only multimedia ciphers can completely be broken in a chosen-plaintext scenario. Apparently, chosen-plaintext scenario models a very resourceful adversary and does not hold in many practical situations. To show that these ciphers are totally broken, we propose a cipher-text only attack on these ciphers. To that end, we investigate speech permutation-only ciphers and show that inherent redundancies of speech signal can pave the path for a successful cipher-text only attack. For this task different concepts and techniques are merged together. First, Short Time Fourier Transform (STFT) is employed to extract regularities of audio signal in both time and frequency. Then, it is shown that cipher-texts can be considered as a set of scrambled puzzles. Then different techniques such as estimation, image processing, branch and bound, and graph theory are fused together to create and solve these puzzles. After extracting the keys from the solved puzzles, they are applied on the scrambled signal. Conducted tests show that the proposed method achieves objective and subjective intelligibility of 87.8% and 92.9%. These scores are 50.9% and 34.6% higher than scores of previous method.
NLP2Code: Code Snippet Content Assist via Natural Language Tasks
Venue: arXiv cs.SE 2017
Year: 2017

Developers increasingly take to the Internet for code snippets to integrate into their programs. To save developers the time required to switch from their development environments to a web browser in the quest for a suitable code snippet, we introduce NLP2Code, a content assist for code snippets. Unlike related tools, NLP2Code integrates directly into the source code editor and provides developers with a content assist feature to close the vocabulary gap between developers' needs and code snippet meta data. Our preliminary evaluation of NLP2Code shows that the majority of invocations lead to code snippets rated as helpful by users and that the tool is able to support a wide range of tasks.
Improved Algorithms For Structured Sparse Recovery
Venue: arXiv cs.IT 2017
Year: 2017

It is known that certain structures of the signal in addition to the standard notion of sparsity (called structured sparsity) can improve the sample complexity in several compressive sensing applications. Recently, Hegde et al. proposed a framework, called approximation-tolerant model-based compressive sensing, for recovering signals with structured sparsity. Their framework requires two oracles, the head- and the tail-approximation projection oracles. The two oracles should return approximate solutions in the model which is closest to the query signal. In this paper, we consider two structured sparsity models and obtain improved projection algorithms. The first one is the tree sparsity model, which captures the support structure in the wavelet decomposition of piecewise-smooth signals. We propose a linear time $(1-ε)$-approximation algorithm for head-approximation projection and a linear time $(1+ε)$-approximation algorithm for tail-approximation projection. The best previous result is an $\tilde{O}(n\log n)$ time bicriterion approximation algorithm (meaning that their algorithm may return a solution of sparsity larger than $k$) by Hegde et al. Our result provides an affirmative answer to the open problem mentioned in the survey of Hegde and Indyk. As a corollary, we can recover a constant approximate $k$-sparse signal. The other is the Constrained Earth Mover Distance (CEMD) model, which is useful to model the situation where the positions of the nonzero coefficients of a signal do not change significantly as a function of spatial (or temporal) locations. We obtain the first single criterion constant factor approximation algorithm for the head-approximation projection. The previous best known algorithm is a bicriterion approximation. Using this result, we can get a faster constant approximation algorithm with fewer measurements for the recovery problem in CEMD model.
Efficiently Computing Provenance Graphs for Queries with Negation
Venue: arXiv cs.DB 2017
Year: 2017

Explaining why an answer is in the result of a query or why it is missing from the result is important for many applications including auditing, debugging data and queries, and answering hypothetical questions about data. Both types of questions, i.e., why and why-not provenance, have been studied extensively. In this work, we present the first practical approach for answering such questions for queries with negation (first-order queries). Our approach is based on a rewriting of Datalog rules (called firing rules) that captures successful rule derivations within the context of a Datalog query. We extend this rewriting to support negation and to capture failed derivations that explain missing answers. Given a (why or why-not) provenance question, we compute an explanation, i.e., the part of the provenance that is relevant to answer the question. We introduce optimizations that prune parts of a provenance graph early on if we can determine that they will not be part of the explanation for a given question. We present an implementation that runs on top of a relational database using SQL to compute explanations. Our experiments demonstrate that our approach scales to large instances and significantly outperforms an earlier approach which instantiates the full provenance to compute explanations.
Physical Layer Security Jamming: Theoretical Limits and Practical Designs in Wireless Networks
Venue: arXiv cs.IT 2017
Year: 2017

Physical layer security has been recently recognized as a promising new design paradigm to provide security in wireless networks. In addition to the existing conventional cryptographic methods, physical layer security exploits the dynamics of fading channels to enhance secured wireless links. In this approach, jamming plays a key role by generating noise signals to confuse the potential eavesdroppers, and significantly improves quality and reliability of secure communications between legitimate terminals. This article presents theoretical limits and practical designs of jamming approaches for physical layer security. In particular, the theoretical limits explore the achievable secrecy rates of user cooperation based jamming whilst the centralized, and game theoretic based precoding techniques are reviewed for practical implementations. In addition, the emerging wireless energy harvesting techniques are exploited to harvest the required energy to transmit jamming signals. Future directions of these approaches, and the associated research challenges are also briefly outlined.
A Large-scale Dataset and Benchmark for Similar Trademark Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Trademark retrieval (TR) has become an important yet challenging problem due to an ever increasing trend in trademark applications and infringement incidents. There have been many promising attempts for the TR problem, which, however, fell impracticable since they were evaluated with limited and mostly trivial datasets. In this paper, we provide a large-scale dataset with benchmark queries with which different TR approaches can be evaluated systematically. Moreover, we provide a baseline on this benchmark using the widely-used methods applied to TR in the literature. Furthermore, we identify and correct two important issues in TR approaches that were not addressed before: reversal of contrast, and presence of irrelevant text in trademarks severely affect the TR methods. Lastly, we applied deep learning, namely, several popular Convolutional Neural Network models, to the TR problem. To the best of the authors, this is the first attempt to do so.
Low-complexity Receiver for Multi-Level Polar Coded Modulation in Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

Non-orthogonal multiple access (NOMA) schemes have been proved to increase the multiple-access achievable rate with respect to orthogonal multiple access (OMA). In this paper we propose a novel communication system that combines multi-level coded modulation and polar codes in a NOMA scenario. Computational complexity decreases with the proposed scheme with respect to state-of-the-art solutions. We also highlight the trade-off between error rate performance and computational complexity.
A Higher-Order Logic for Concurrent Termination-Preserving Refinement
Venue: arXiv cs.PL 2017
Year: 2017

Compiler correctness proofs for higher-order concurrent languages are difficult: they involve establishing a termination-preserving refinement between a concurrent high-level source language and an implementation that uses low-level shared memory primitives. However, existing logics for proving concurrent refinement either neglect properties such as termination, or only handle first-order state. In this paper, we address these limitations by extending Iris, a recent higher-order concurrent separation logic, with support for reasoning about termination-preserving refinements. To demonstrate the power of these extensions, we prove the correctness of an efficient implementation of a higher-order, session-typed language. To our knowledge, this is the first program logic capable of giving a compiler correctness proof for such a language. The soundness of our extensions and our compiler correctness proof have been mechanized in Coq.