OpenRaiser/Intern-Atlas huggingface dataset:
Linear time construction of compressed text indices in compact space
Venue: arXiv cs.DS 2016
Year: 2016

We show that the compressed suffix array and the compressed suffix tree for a string of length $n$ over an integer alphabet of size $σ\leq n$ can both be built in $O(n)$ (randomized) time using only $O(n\logσ)$ bits of working space. The previously fastest construction algorithms that used $O(n\logσ)$ bits of space took times $O(n\log\logσ)$ and $O(n\log^εn)$ respectively (where $ε$ is any positive constant smaller than $1$). In the passing, we show that the Burrows-Wheeler transform of a string of length $n$ over an alphabet of size $σ$ can be built in deterministic $O(n)$ time and space $O(n\logσ)$. We also show that within the same time and space, we can carry many sequence analysis tasks and construct some variants of the compressed suffix array and compressed suffix tree.
Test Problem Construction for Single-Objective Bilevel Optimization
Venue: arXiv cs.MS 2016
Year: 2016

In this paper, we propose a procedure for designing controlled test problems for single-objective bilevel optimization. The construction procedure is flexible and allows its user to control the different complexities that are to be included in the test problems independently of each other. In addition to properties that control the difficulty in convergence, the procedure also allows the user to introduce difficulties caused by interaction of the two levels. As a companion to the test problem construction framework, the paper presents a standard test suite of twelve problems, which includes eight unconstrained and four constrained problems. Most of the problems are scalable in terms of variables and constraints. To provide baseline results, we have solved the proposed test problems using a nested bilevel evolutionary algorithm. The results can be used for comparison, while evaluating the performance of any other bilevel optimization algorithm. The codes related to the paper may be accessed from the website \url{http://bilevel.org}.
Operads, quasiorders, and regular languages
Venue: arXiv cs.FL 2016
Year: 2016

We generalize the construction of multitildes in the aim to provide multitilde operators for regular languages. We show that the underliying algebraic structure involves the action of some operads. An operad is an algebraic structure that mimics the composition of the functions. The involved operads are described in terms of combinatorial objects. These operads are obtained from more primitive objects, namely precompositions, whose algebraic counter-parts are investigated. One of these operads acts faithfully on languages in the sense that two different operators act in two different ways.
BSMBench: a flexible and scalable supercomputer benchmark from computational particle physics
Venue: arXiv cs.DC 2016
Year: 2016

Lattice Quantum ChromoDynamics (QCD), and by extension its parent field, Lattice Gauge Theory (LGT), make up a significant fraction of supercomputing cycles worldwide. As such, it would be irresponsible not to evaluate machines' suitability for such applications. To this end, a benchmark has been developed to assess the performance of LGT applications on modern HPC platforms. Distinct from previous QCD-based benchmarks, this allows probing the behaviour of a variety of theories, which allows varying the ratio of demands between on-node computations and inter-node communications. The results of testing this benchmark on various recent HPC platforms are presented, and directions for future development are discussed.
Analysis of A Nonsmooth Optimization Approach to Robust Estimation
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we consider the problem of identifying a linear map from measurements which are subject to intermittent and arbitarily large errors. This is a fundamental problem in many estimation-related applications such as fault detection, state estimation in lossy networks, hybrid system identification, robust estimation, etc. The problem is hard because it exhibits some intrinsic combinatorial features. Therefore, obtaining an effective solution necessitates relaxations that are both solvable at a reasonable cost and effective in the sense that they can return the true parameter vector. The current paper discusses a nonsmooth convex optimization approach and provides a new analysis of its behavior. In particular, it is shown that under appropriate conditions on the data, an exact estimate can be recovered from data corrupted by a large (even infinite) number of gross errors.
Anisotropic Mesh Adaptation for Image Representation
Venue: arXiv cs.CV 2016
Year: 2016

Triangular meshes have gained much interest in image representation and have been widely used in image processing. This paper introduces a framework of anisotropic mesh adaptation (AMA) methods to image representation and proposes a GPRAMA method that is based on AMA and greedy-point removal (GPR) scheme. Different than many other methods that triangulate sample points to form the mesh, the AMA methods start directly with a triangular mesh and then adapt the mesh based on a user-defined metric tensor to represent the image. The AMA methods have clear mathematical framework and provides flexibility for both image representation and image reconstruction. A mesh patching technique is developed for the implementation of the GPRAMA method, which leads to an improved version of the popular GPRFS-ED method. The GPRAMA method can achieve better quality than the GPRFS-ED method but with lower computational cost.
Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns
Venue: arXiv cs.IT 2016
Year: 2016

In this work we analyze the problem of phase retrieval from Fourier measurements with random diffraction patterns. To this end, we consider the recently introduced PhaseLift algorithm, which expresses the problem in the language of convex optimization. We provide recovery guarantees which require O(log^2 d) different diffraction patterns, thus improving on recent results by Candes et al. [arXiv:1310.3240], which require O(log^4 d) different patterns.
ARSENAL: Automatic Requirements Specification Extraction from Natural Language
Venue: arXiv cs.CL 2016
Year: 2016

Requirements are informal and semi-formal descriptions of the expected behavior of a complex system from the viewpoints of its stakeholders (customers, users, operators, designers, and engineers). However, for the purpose of design, testing, and verification for critical systems, we can transform requirements into formal models that can be analyzed automatically. ARSENAL is a framework and methodology for systematically transforming natural language (NL) requirements into analyzable formal models and logic specifications. These models can be analyzed for consistency and implementability. The ARSENAL methodology is specialized to individual domains, but the approach is general enough to be adapted to new domains.
On Negotiation as Concurrency Primitive II: Deterministic Cyclic Negotiations
Venue: arXiv cs.LO 2016
Year: 2016

We continue our study of negotations, a concurrency model with multiparty negotiation as primitive. In a previous paper (arXiv:13072145) we have provided a correct and complete set of reduction rules for sound, acyclic, and (weakly) deterministic negotiations. In this paper we extend this result to all deterministic negotiations, including cyclic ones. We also show that this set of rules allows one to decide soundness and to summarize negotiations in polynomial time.
Adaptive Control of Robot Manipulators With Uncertain Kinematics and Dynamics
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we investigate the adaptive control problem for robot manipulators with both the uncertain kinematics and dynamics. We propose two adaptive control schemes to realize the objective of task-space trajectory tracking irrespective of the uncertain kinematics and dynamics. The proposed controllers have the desirable separation property, and we also show that the first adaptive controller with appropriate modifications can yield improved performance, without the expense of conservative gain choice. The performance of the proposed controllers is shown by numerical simulations.
A Hydraulic Approach to Equilibria of Resource Selection Games
Venue: arXiv cs.GT 2016
Year: 2016

Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games (i.e., asymmetric singleton congestion games) with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the uniqueness of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (unique) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on linear programming, or on the existence of a potential (though our analysis does provide powerful insights into the potential, via a natural concrete physical interpretation). A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing the existence of strong equilibria, and showing that while resource costs are no longer unique across Nash equilibria in games of this family, they are nonetheless unique across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.
Further scramblings of Marsaglia's xorshift generators
Venue: arXiv cs.DS 2016
Year: 2016

xorshift* generators are a variant of Marsaglia's xorshift generators that eliminate linear artifacts typical of generators based on $\mathbf Z/2\mathbf Z$-linear operations using multiplication by a suitable constant. Shortly after high-dimensional xorshift* generators were introduced, Saito and Matsumoto suggested a different way to eliminate linear artifacts based on addition in $\mathbf Z/2^{32}\mathbf Z$, leading to the XSadd generator. Starting from the observation that the lower bits of XSadd are very weak, as its reverse fails systematically several statistical tests, we explore xorshift+, a variant of XSadd using 64-bit operations, which leads, in small dimension, to extremely fast high-quality generators.
On the rank of random matrices over finite fields
Venue: arXiv cs.IT 2016
Year: 2016

A novel lower bound is introduced for the full rank probability of random finite field matrices, where a number of elements with known location are identically zero, and remaining elements are chosen independently of each other, uniformly over the field. The main ingredient is a result showing that constraining additional elements to be zero cannot result in a higher probability of full rank. The bound then follows by "zeroing" elements to produce a block-diagonal matrix, whose full rank probability can be computed exactly. The bound is shown to be at least as tight and can be strictly tighter than existing bounds.
Nonparametric Infinite Horizon Kullback-Leibler Stochastic Control
Venue: arXiv cs.SY 2016
Year: 2016

We present two nonparametric approaches to Kullback-Leibler (KL) control, or linearly-solvable Markov decision problem (LMDP) based on Gaussian processes (GP) and Nyström approximation. Compared to recently developed parametric methods, the proposed data-driven frameworks feature accurate function approximation and efficient on-line operations. Theoretically, we derive the mathematical connection of KL control based on dynamic programming with earlier work in control theory which relies on information theoretic dualities for the infinite time horizon case. Algorithmically, we give explicit optimal control policies in nonparametric forms, and propose on-line update schemes with budgeted computational costs. Numerical results demonstrate the effectiveness and usefulness of the proposed frameworks.
A Bitcoin system with no mining and no history transactions: Build a compact Bitcoin system
Venue: arXiv cs.CE 2016
Year: 2016

We give an explicit definition of decentralization and show you that decentralization is almost impossible for the current stage and Bitcoin is the first truly noncentralized currency in the currency history. We propose a new framework of noncentralized cryptocurrency system with an assumption of the existence of a weak adversary for a bank alliance. It abandons the mining process and blockchain, and removes history transactions from data synchronization. We propose a consensus algorithm named Converged Consensus for a noncentralized cryptocurrency system.
Analogy Between Gambling and Measurement-Based Work Extraction
Venue: arXiv cs.IT 2016
Year: 2016

In information theory, one area of interest is gambling, where mutual information characterizes the maximal gain in wealth growth rate due to knowledge of side information; the betting strategy that achieves this maximum is named the Kelly strategy. In the field of physics, it was recently shown that mutual information can characterize the maximal amount of work that can be extracted from a single heat bath using measurement-based control protocols, i.e., using "information engines". However, to the best of our knowledge, no relation between gambling and information engines has been presented before. In this paper, we briefly review the two concepts and then demonstrate an analogy between gambling, where bits are converted into wealth, and information engines, where bits representing measurements are converted into energy. From this analogy follows an extension of gambling to the continuous-valued case, which is shown to be useful for investments in currency exchange rates or in the stock market using options. Moreover, the analogy enables us to use well-known methods and results from one field to solve problems in the other. We present three such cases: maximum work extraction when the probability distributions governing the system and measurements are unknown, work extraction when some energy is lost in each cycle, e.g., due to friction, and an analysis of systems with memory. In all three cases, the analogy enables us to use known results in order to obtain new ones.
Approximate Capacity Region of the Two-User MISO Broadcast Channels with Delayed CSIT
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of multiple-input single-output Broadcast Channels with Rayleigh fading where the transmitter has access to delayed knowledge of the channel state information. We first characterize the capacity region of this channel with two users to within constant number of bits for all values of the transmit power. The proposed signaling strategy utilizes the delayed knowledge of the channel state information and the previously transmitted signals, in order to create a signal of common interest for both receivers. This signal would be the quantized version of the summation of the previously transmitted signals. A challenge that arises in deriving the result for finite signal-to-noise ratio regimes is the correlation that exists between the quantization noise and the signal. To guarantee the independence of quantization noise and signal, we extend the framework of lattice quantizers with dither together with an interleaving step. For converse, we use the fact that the capacity region of this problem is upper-bounded by the capacity region of a physically degraded broadcast channel with no channel state information where one receiver has two antennas. Then, we derive an outer-bound on the capacity region of this degraded broadcast channel. Finally, we show how to extend our results to obtain the approximate capacity of the $K$-user multiple-input single-output Broadcast Channel with delayed knowledge of the channel state information at the transmitter to within $2 \log_2 \left( K + 2 \right)$ bits/s/Hz.
Inapproximability of Nash Equilibrium
Venue: arXiv cs.GT 2016
Year: 2016

We prove that finding an $ε$-approximate Nash equilibrium is PPAD-complete for constant $ε$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative $ε$-Well Supported Nash Equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen, Deng, and Teng [CDT'09], and for approximate competitive equilibrium from equal incomes with indivisible goods.
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma
Venue: arXiv cs.CC 2016
Year: 2016

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of parallel computing and the "sensitivity vs. block sensitivity" conjecture. In this paper, we take a deeper look at the size of such sets and their structure. We show an unexpected "gap theorem": if $S\subseteq\{0, 1\}^n$ has sensitivity $s$, then we either have $|S|=2^{n-s}$ or $|S|\geq \frac{3}{2} 2^{n-s}$. This is shown via classifying such sets into sets that can be constructed from low-sensitivity subsets of $\{0, 1\}^{n'}$ for $n'<n$ and irreducible sets which cannot be constructed in such a way and then proving a lower bound on the size of irreducible sets. This provides new insights into the structure of low sensitivity subsets of the Boolean hypercube $\{0, 1\}^n$.
Point visibility graph recognition is NP-hard
Venue: arXiv cs.CG 2016
Year: 2016

Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.
Flow Allocation for Maximum Throughput and Bounded Delay on Multiple Disjoint Paths for Random Access Wireless Multihop Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we consider random access, wireless, multi-hop networks, with multi-packet reception capabilities, where multiple flows are forwarded to the gateways through node disjoint paths. We explore the issue of allocating flow on multiple paths, exhibiting both intra- and inter-path interference, in order to maximize average aggregate flow throughput (AAT) and also provide bounded packet delay. A distributed flow allocation scheme is proposed where allocation of flow on paths is formulated as an optimization problem. Through an illustrative topology it is shown that the corresponding problem is non-convex. Furthermore, a simple, but accurate model is employed for the average aggregate throughput achieved by all flows, that captures both intra- and inter-path interference through the SINR model. The proposed scheme is evaluated through Ns2 simulations of several random wireless scenarios. Simulation results reveal that, the model employed, accurately captures the AAT observed in the simulated scenarios, even when the assumption of saturated queues is removed. Simulation results also show that the proposed scheme achieves significantly higher AAT, for the vast majority of the wireless scenarios explored, than the following flow allocation schemes: one that assigns flows on paths on a round-robin fashion, one that optimally utilizes the best path only, and another one that assigns the maximum possible flow on each path. Finally, a variant of the proposed scheme is explored, where interference for each link is approximated by considering its dominant interfering nodes only.
Learning Laplacian Matrix in Smooth Graph Signal Representations
Venue: arXiv cs.LG 2016
Year: 2016

The construction of a meaningful graph plays a crucial role in the success of many graph-based representations and algorithms for handling structured data, especially in the emerging field of graph signal processing. However, a meaningful graph is not always readily available from the data, nor easy to define depending on the application domain. In particular, it is often desirable in graph signal processing applications that a graph is chosen such that the data admit certain regularity or smoothness on the graph. In this paper, we address the problem of learning graph Laplacians, which is equivalent to learning graph topologies, such that the input data form graph signals with smooth variations on the resulting topology. To this end, we adopt a factor analysis model for the graph signals and impose a Gaussian probabilistic prior on the latent variables that control these signals. We show that the Gaussian prior leads to an efficient representation that favors the smoothness property of the graph signals. We then propose an algorithm for learning graphs that enforces such property and is based on minimizing the variations of the signals on the learned graph. Experiments on both synthetic and real world data demonstrate that the proposed graph learning framework can efficiently infer meaningful graph topologies from signal observations under the smoothness prior.
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
Venue: arXiv cs.CC 2016
Year: 2016

For a positive integer $k$, a $k$-colouring of a graph $G=(V,E)$ is a mapping $c: V\rightarrow\{1,2,...,k\}$ such that $c(u)\neq c(v)$ whenever $uv\in E$. The Colouring problem is to decide, for a given $G$ and $k$, whether a $k$-colouring of $G$ exists. If $k$ is fixed (that is, it is not part of the input), we have the decision problem $k$-Colouring instead. We survey known results on the computational complexity of Colouring and $k$-Colouring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial colouring, or where lists of permissible colours are given for each vertex.
Space Lower Bounds for Itemset Frequency Sketches
Venue: arXiv cs.DS 2016
Year: 2016

Given a database, computing the fraction of rows that contain a query itemset or determining whether this fraction is above some threshold are fundamental operations in data mining. A uniform sample of rows is a good sketch of the database in the sense that all sufficiently frequent itemsets and their approximate frequencies are recoverable from the sample, and the sketch size is independent of the number of rows in the original database. For many seemingly similar problems there are better sketching algorithms than uniform sampling. In this paper we show that for itemset frequency sketching this is not the case. That is, we prove that there exist classes of databases for which uniform sampling is a space optimal sketch for approximate itemset frequency analysis, up to constant or iterated-logarithmic factors.
A Sane Proof that COLk \le COL3
Venue: arXiv cs.CC 2016
Year: 2016

Let COLk be the set of all k-colorable graphs. It is easy to show that if a<b then COLa \le COLb (poly time reduction). Using the Cook-Levin theorem it is easy to show that if 3 \le a< b then COLb \le COLa. However this proof is insane in that it translates a graph to a formula and then the formula to a graph. We give a simple proof that COLk \le COL3.