OpenRaiser/Intern-Atlas huggingface dataset:
Sparse multivariate polynomial interpolation in the basis of Schubert polynomials
Venue: arXiv cs.CC 2016
Year: 2016

Schubert polynomials were discovered by A. Lascoux and M. Schützenberger in the study of cohomology rings of flag manifolds in 1980's. These polynomials generalize Schur polynomials, and form a linear basis of multivariate polynomials. In 2003, Lenart and Sottile introduced skew Schubert polynomials, which generalize skew Schur polynomials, and expand in the Schubert basis with the generalized Littlewood-Richardson coefficients. In this paper we initiate the study of these two families of polynomials from the perspective of computational complexity theory. We first observe that skew Schubert polynomials, and therefore Schubert polynomials, are in $\CountP$ (when evaluating on non-negative integral inputs) and $\VNP$. Our main result is a deterministic algorithm that computes the expansion of a polynomial $f$ of degree $d$ in $\Z[x_1, \dots, x_n]$ in the basis of Schubert polynomials, assuming an oracle computing Schubert polynomials. This algorithm runs in time polynomial in $n$, $d$, and the bit size of the expansion. This generalizes, and derandomizes, the sparse interpolation algorithm of symmetric polynomials in the Schur basis by Barvinok and Fomin (Advances in Applied Mathematics, 18(3):271--285). In fact, our interpolation algorithm is general enough to accommodate any linear basis satisfying certain natural properties. Applications of the above results include a new algorithm that computes the generalized Littlewood-Richardson coefficients.
Statistical Modeling and Estimation of Censored Pathloss Data
Venue: arXiv cs.IT 2016
Year: 2016

Pathloss is typically modeled using a log-distance power law with a large-scale fading term that is log-normal. However, the received signal is affected by the dynamic range and noise floor of the measurement system used to sound the channel, which can cause measurement samples to be truncated or censored. If the information about the censored samples are not included in the estimation method, as in ordinary least squares estimation, it can result in biased estimation of both the pathloss exponent and the large scale fading. This can be solved by applying a Tobit maximum-likelihood estimator, which provides consistent estimates for the pathloss parameters. This letter provides information about the Tobit maximum-likelihood estimator and its asymptotic variance under certain conditions.
Wasserstein continuity of entropy and outer bounds for interference channels
Venue: arXiv cs.IT 2016
Year: 2016

It is shown that under suitable regularity conditions, differential entropy is a Lipschitz functional on the space of distributions on $n$-dimensional Euclidean space with respect to the quadratic Wasserstein distance. Under similar conditions, (discrete) Shannon entropy is shown to be Lipschitz continuous in distributions over the product space with respect to Ornstein's $\bar d$-distance (Wasserstein distance corresponding to the Hamming distance). These results together with Talagrand's and Marton's transportation-information inequalities allow one to replace the unknown multi-user interference with its i.i.d. approximations. As an application, a new outer bound for the two-user Gaussian interference channel is proved, which, in particular, settles the "missing corner point" problem of Costa (1985).
Symbolic Manipulation of Code Properties
Venue: arXiv cs.FL 2016
Year: 2016

The FAdo system is a symbolic manipulator of formal languages objects, implemented in Python. In this work, we extend its capabilities by implementing methods to manipulate transducers and we go one level higher than existing formal language systems and implement methods to manipulate objects representing classes of independent languages (widely known as code properties). Our methods allow users to define their own code properties and combine them between themselves or with fixed properties such as prefix codes, suffix codes, error detecting codes, etc. The satisfaction and maximality decision questions are solvable for any of the definable properties. The new online system LaSer allows to query about code properties and obtain the answer in a batch mode. Our work is founded on independence theory as well as the theory of rational relations and transducers and contributes with improveded algorithms on these objects.
Complexity of Suffix-Free Regular Languages
Venue: arXiv cs.FL 2016
Year: 2016

We study various complexity properties of suffix-free regular languages. The quotient complexity of a regular language $L$ is the number of left quotients of $L$; this is the same as the state complexity of $L$. A regular language $L'$ is a dialect of a regular language $L$ if it differs only slightly from $L$. The quotient complexity of an operation on regular languages is the maximal quotient complexity of the result of the operation expressed as a function of the quotient complexities of the operands. A sequence $(L_k,L_{k+1},\dots)$ of regular languages in some class ${\mathcal C}$, where $n$ is the quotient complexity of $L_n$, is called a stream. A stream is most complex in class ${\mathcal C}$ if its languages $L_n$ meet the complexity upper bounds for all basic measures. It is known that there exist such most complex streams in the class of regular languages, in the class of prefix-free languages, and also in the classes of right, left, and two-sided ideals. In contrast to this, we prove that there does not exist a most complex stream in the class of suffix-free regular languages. However, we do exhibit one ternary suffix-free stream that meets the bound for product and whose restrictions to binary alphabets meet the bounds for star and boolean operations. We also exhibit a quinary stream that meets the bounds for boolean operations, reversal, size of syntactic semigroup, and atom complexities. Moreover, we solve an open problem about the bound for the product of two languages of quotient complexities $m$ and $n$ in the binary case by showing that it can be met for infinitely many $m$ and $n$.
Information Complexity Density and Simulation of Protocols
Venue: arXiv cs.IT 2016
Year: 2016

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for indepedent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.
Online Adaptive Hidden Markov Model for Multi-Tracker Fusion
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a novel method for visual object tracking called HMMTxD. The method fuses observations from complementary out-of-the box trackers and a detector by utilizing a hidden Markov model whose latent states correspond to a binary vector expressing the failure of individual trackers. The Markov model is trained in an unsupervised way, relying on an online learned detector to provide a source of tracker-independent information for a modified Baum- Welch algorithm that updates the model w.r.t. the partially annotated data. We show the effectiveness of the proposed method on combination of two and three tracking algorithms. The performance of HMMTxD is evaluated on two standard benchmarks (CVPR2013 and VOT) and on a rich collection of 77 publicly available sequences. The HMMTxD outperforms the state-of-the-art, often significantly, on all datasets in almost all criteria.
Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
Venue: arXiv cs.IT 2016
Year: 2016

Under which conditions and with which distortions can we preserve the pairwise-distances of low-complexity vectors, e.g., for structured sets such as the set of sparse vectors or the one of low-rank matrices, when these are mapped in a finite set of vectors? This work addresses this general question through the specific use of a quantized and dithered random linear mapping which combines, in the following order, a sub-Gaussian random projection in $\mathbb R^M$ of vectors in $\mathbb R^N$, a random translation, or "dither", of the projected vectors and a uniform scalar quantizer of resolution $δ>0$ applied componentwise. Thanks to this quantized mapping we are first able to show that, with high probability, an embedding of a bounded set $\mathcal K \subset \mathbb R^N$ in $δ\mathbb Z^M$ can be achieved when distances in the quantized and in the original domains are measured with the $\ell_1$- and $\ell_2$-norm, respectively, and provided the number of quantized observations $M$ is large before the square of the "Gaussian mean width" of $\mathcal K$. In this case, we show that the embedding is actually "quasi-isometric" and only suffers of both multiplicative and additive distortions whose magnitudes decrease as $M^{-1/5}$ for general sets, and as $M^{-1/2}$ for structured set, when $M$ increases. Second, when one is only interested in characterizing the maximal distance separating two elements of $\mathcal K$ mapped to the same quantized vector, i.e., the "consistency width" of the mapping, we show that for a similar number of measurements and with high probability this width decays as $M^{-1/4}$ for general sets and as $1/M$ for structured ones when $M$ increases. Finally, as an important aspect of our work, we also establish how the non-Gaussianity of the mapping impacts the class of vectors that can be embedded or whose consistency width provably decays when $M$ increases.
On Freeze LTL with Ordered Attributes
Venue: arXiv cs.LO 2016
Year: 2016

This paper is concerned with Freeze LTL, a temporal logic on data words with registers. In a (multi-attributed) data word each position carries a letter from a finite alphabet and assigns a data value to a fixed, finite set of attributes. The satisfiability problem of Freeze LTL is undecidable if more than one register is available or tuples of data values can be stored and compared arbitrarily. Starting from the decidable one-register fragment we propose an extension that allows for specifying a dependency relation on attributes. This restricts in a flexible way how collections of attribute values can be stored and compared. This conceptual dimension is orthogonal to the number of registers or the available temporal operators. The extension is strict. Admitting arbitrary dependency relations satisfiability becomes undecidable. Tree-like relations, however, induce a family of decidable fragments escalating the ordinal-indexed hierarchy of fast-growing complexity classes, a recently introduced framework for non-primitive recursive complexities. This results in completeness for the class ${\bf F}_{ε_0}$. We employ nested counter systems and show that they relate to the hierarchy in terms of the nesting depth.
Towards Massive, Ultra-Reliable, and Low-Latency Wireless Communication with Short Packets
Venue: arXiv cs.IT 2016
Year: 2016

Most of the recent advances in the design of high-speed wireless systems are based on information-theoretic principles that demonstrate how to efficiently transmit long data packets. However, the upcoming wireless systems, notably the 5G system, will need to support novel traffic types that use short packets. For example, short packets represent the most common form of traffic generated by sensors and other devices involved in Machine-to-Machine (M2M) communications. Furthermore, there are emerging applications in which small packets are expected to carry critical information that should be received with low latency and ultra-high reliability. Current wireless systems are not designed to support short-packet transmissions. For example, the design of current systems relies on the assumption that the metadata (control information) is of negligible size compared to the actual information payload. Hence, transmitting metadata using heuristic methods does not affect the overall system performance. However, when the packets are short, metadata may be of the same size as the payload, and the conventional methods to transmit it may be highly suboptimal. In this article, we review recent advances in information theory, which provide the theoretical principles that govern the transmission of short packets. We then apply these principles to three exemplary scenarios (the two-way channel, the downlink broadcast channel, and the uplink random access channel), thereby illustrating how the transmission of control information can be optimized when the packets are short. The insights brought by these examples suggest that new principles are needed for the design of wireless protocols supporting short packets. These principles will have a direct impact on the system design.
Random Forest for the Contextual Bandit Problem - extended version
Venue: arXiv cs.LG 2016
Year: 2016

To address the contextual bandit problem, we propose an online random forest algorithm. The analysis of the proposed algorithm is based on the sample complexity needed to find the optimal decision stump. Then, the decision stumps are assembled in a random collection of decision trees, Bandit Forest. We show that the proposed algorithm is optimal up to logarithmic factors. The dependence of the sample complexity upon the number of contextual variables is logarithmic. The computational cost of the proposed algorithm with respect to the time horizon is linear. These analytical results allow the proposed algorithm to be efficient in real applications, where the number of events to process is huge, and where we expect that some contextual variables, chosen from a large set, have potentially non- linear dependencies with the rewards. In the experiments done to illustrate the theoretical analysis, Bandit Forest obtain promising results in comparison with state-of-the-art algorithms.
Dynamic index, LZ factorization, and LCE queries in compressed space
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we present the following results: (1) We propose a new \emph{dynamic compressed index} of $O(w)$ space, that supports searching for a pattern $P$ in the current text in $O(|P| f(M,w) + \log w \log |P| \log^* M (\log N + \log |P| \log^* M) + \mathit{occ} \log N)$ time and insertion/deletion of a substring of length $y$ in $O((y+ \log N\log^* M)\log w \log N \log^* M)$ time, where $N$ is the length of the current text, $M$ is the maximum length of the dynamic text, $z$ is the size of the Lempel-Ziv77 (LZ77) factorization of the current text, $f(a,b) = O(\min \{ \frac{\log\log a \log\log b}{\log\log\log a}, \sqrt{\frac{\log b}{\log\log b}} \})$ and $w = O(z \log N \log^*M)$. (2) We propose a new space-efficient LZ77 factorization algorithm for a given text of length $N$, which runs in $O(N f(N,w') + z \log w' \log^3 N (\log^* N)^2)$ time with $O(w')$ working space, where $w' =O(z \log N \log^* N)$. (3) We propose a data structure of $O(w)$ space which supports longest common extension (LCE) queries on the text in $O(\log N + \log \ell \log^* N)$ time, where $\ell$ is the output LCE length. On top of the above contributions, we show several applications of our data structures which improve previous best known results on grammar-compressed string processing.
Polynomial Factorization over Finite Fields By Computing Euler-Poincare Characteristics of Drinfeld Modules
Venue: arXiv cs.CC 2016
Year: 2016

We propose and rigorously analyze two randomized algorithms to factor univariate polynomials over finite fields using rank $2$ Drinfeld modules. The first algorithm estimates the degree of an irreducible factor of a polynomial from Euler-Poincare characteristics of random Drinfeld modules. Knowledge of a factor degree allows one to rapidly extract all factors of that degree. As a consequence, the problem of factoring polynomials over finite fields in time nearly linear in the degree is reduced to finding Euler-Poincare characteristics of random Drinfeld modules with high probability. Notably, the worst case complexity of polynomial factorization over finite fields is reduced to the average case complexity of a problem concerning Drinfeld modules. The second algorithm is a random Drinfeld module analogue of Berlekamp's algorithm. During the course of its analysis, we prove a new bound on degree distributions in factorization patterns of polynomials over finite fields in certain short intervals.
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Venue: arXiv cs.DS 2016
Year: 2016

Given a static reference string $R$ and a source string $S$, a relative compression of $S$ with respect to $R$ is an encoding of $S$ as a sequence of references to substrings of $R$. Relative compression schemes are a classic model of compression and have recently proved very successful for compressing highly-repetitive massive data sets such as genomes and web-data. We initiate the study of relative compression in a dynamic setting where the compressed source string $S$ is subject to edit operations. The goal is to maintain the compressed representation compactly, while supporting edits and allowing efficient random access to the (uncompressed) source string. We present new data structures that achieve optimal time for updates and queries while using space linear in the size of the optimal relative compression, for nearly all combinations of parameters. We also present solutions for restricted and extended sets of updates. To achieve these results, we revisit the dynamic partial sums problem and the substring concatenation problem. We present new optimal or near optimal bounds for these problems. Plugging in our new results we also immediately obtain new bounds for the string indexing for patterns with wildcards problem and the dynamic text and static pattern matching problem.
Multiuser Wireless Power Transfer via Magnetic Resonant Coupling: Performance Analysis, Charging Control, and Power Region Characterization
Venue: arXiv cs.SY 2016
Year: 2016

Magnetic resonant coupling (MRC) is an efficient method for realizing the near-field wireless power transfer (WPT). Although the MRC enabled WPT (MRC-WPT) with a single pair of transmitter and receiver has been thoroughly studied in the literature, there is limited work on the general setup with multiple transmitters and/or receivers. In this paper, we consider a point-to-multipoint MRC-WPT system with one transmitter delivering wireless power to a set of distributed receivers. We aim to introduce new applications of signal processing and optimization techniques to the performance characterization and optimization in multiuser WPT via MRC. We first derive closed-form expressions for the power drawn from the energy source at the transmitter and that delivered to the load at each receiver. We identify a "near-far" fairness issue in multiuser power transmission due to receivers' distance-dependent mutual inductance with the transmitter. To tackle this issue, we propose a centralized charging control algorithm to jointly optimize the receivers' load resistance to minimize the total transmitter power drawn while meeting the given power requirement of each individual load. For ease of practical implementation, we also devise a distributed algorithm for the receivers to adjust their load resistance independently in an iterative manner. Last, we characterize the power region that constitutes all the achievable power-tuples of the loads via controlling their adjustable resistance. In particular, we compare the power regions without versus with the time sharing of users' power transmission, where it is shown that time sharing yields a larger power region in general. Extensive simulation results are provided to validate our analysis and corroborate our study on the multiuser MRC-WPT system.
Frequency-Asynchronous Multiuser Joint Channel-Parameter Estimation, CFO Compensation and Channel Decoding
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates a channel-coded multiuser system operated with orthogonal frequency-division multiplexing (OFDM) and interleaved division multiple-access (IDMA). To realize the potential advantage of OFDM-IDMA, two challenges must be addressed. The first challenge is the estimation of multiple channel parameters. An issue is how to contain the estimation errors of the channel parameters of the multiple users, considering that the overall estimation errors may increase with the number of users because the estimations of their channel parameters are intertwined with each other. The second challenge is that the transmitters of the multiple users may be driven by different RF oscillators. The associated frequency asynchrony may cause multiple CFOs at the receiver. Compared with a single-user receiver where the single CFO can be compensated away, a particular difficulty for a multiuser receiver is that it is not possible to compensate for all the multiple CFOs simultaneously. To tackle the two challenges, we put forth a framework to solve the problems of multiuser channel-parameter estimation, CFO compensation, and channel decoding jointly and iteratively. The framework employs the space alternating generalized expectation-maximization (SAGE) algortihm to decompose the multisuser problem into multiple single-user problems, and the expectation-conditional maximization (ECM) algorithm to tackle each of the single-user subproblems. Iterative executions of SAGE and ECM in the framework allow the two aforementioned challenges to be tackled in an optimal manner. Simulations and real experiments based on software-defined radio indicate that, compared with other approaches, our approach can achieve significant performance gains.
Reinforcement Learning Neural Turing Machines - Revised
Venue: arXiv cs.LG 2016
Year: 2016

The Neural Turing Machine (NTM) is more expressive than all previously considered models because of its external memory. It can be viewed as a broader effort to use abstract external Interfaces and to learn a parametric model that interacts with them. The capabilities of a model can be extended by providing it with proper Interfaces that interact with the world. These external Interfaces include memory, a database, a search engine, or a piece of software such as a theorem verifier. Some of these Interfaces are provided by the developers of the model. However, many important existing Interfaces, such as databases and search engines, are discrete. We examine feasibility of learning models to interact with discrete Interfaces. We investigate the following discrete Interfaces: a memory Tape, an input Tape, and an output Tape. We use a Reinforcement Learning algorithm to train a neural network that interacts with such Interfaces to solve simple algorithmic tasks. Our Interfaces are expressive enough to make our model Turing complete.