OpenRaiser/Intern-Atlas huggingface dataset:
Complexity classifications for different equivalence and audit problems for Boolean circuits
Venue: arXiv cs.CC 2012
Year: 2012

We study Boolean circuits as a representation of Boolean functions and consider different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, while for all other gate types we show these problems are at least NP-hard.
Optimistic Rates for Learning with a Smooth Loss
Venue: arXiv cs.LG 2012
Year: 2012

We establish an excess risk bound of O(H R_n^2 + R_n \sqrt{H L*}) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = \sqrt{R/n}, this translates to a learning rate of O(RH/n) in the separable (L*=0) case and O(RH/n + \sqrt{L^* RH/n}) more generally. We also provide similar guarantees for online and stochastic convex optimization with a smooth non-negative objective.
Robust Coin Flipping
Venue: arXiv cs.CC 2012
Year: 2012

Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $α$, as a function of data she receives from $p$ sources; she seeks privacy from any coalition of $r$ of them. We show: If $p/2 \leq r < p$, the bias can be any rational number and nothing else; if $0 < r < p/2$, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the $r=1$ case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.
Shortest path problem in rectangular complexes of global nonpositive curvature
Venue: arXiv cs.CG 2012
Year: 2012

CAT(0) metric spaces constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a CAT(0) metric space are connected by a unique shortest path γ(x,y). In this paper, we present an efficient algorithm for answering two-point distance queries in CAT(0) rectangular complexes and two of theirs subclasses, ramified rectilinear polygons (CAT(0) rectangular complexes in which the links of all vertices are bipartite graphs) and squaregraphs (CAT(0) rectangular complexes arising from plane quadrangulations in which all inner vertices have degrees \geq4). Namely, we show that for a CAT(0) rectangular complex K with n vertices, one can construct a data structure D of size $O(n^2)$ so that, given any two points x,y in K, the shortest path γ(x,y) between x and y can be computed in O(d(p,q)) time, where p and q are vertices of two faces of K containing the points x and y, respectively, such that γ(x,y) is contained in K(I(p,q)) and d(p,q) is the distance between p and q in the underlying graph of K. If K is a ramified rectilinear polygon, then one can construct a data structure D of optimal size O(n) and answer two-point shortest path queries in O(d(p,q)logΔ) time, where Δ is the maximal degree of a vertex of G(K). Finally, if K is a squaregraph, then one can construct a data structure D of size O(nlogn) and answer two-point shortest path queries in O(d(p,q)) time.
On the Capacity of the $K$-User Cyclic Gaussian Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the capacity region of a $K$-user cyclic Gaussian interference channel, where the $k$th user interferes with only the $(k-1)$th user (mod $K$) in the network. Inspired by the work of Etkin, Tse and Wang, who derived a capacity region outer bound for the two-user Gaussian interference channel and proved that a simple Han-Kobayashi power splitting scheme can achieve to within one bit of the capacity region for all values of channel parameters, this paper shows that a similar strategy also achieves the capacity region of the $K$-user cyclic interference channel to within a constant gap in the weak interference regime. Specifically, for the $K$-user cyclic Gaussian interference channel, a compact representation of the Han-Kobayashi achievable rate region using Fourier-Motzkin elimination is first derived, a capacity region outer bound is then established. It is shown that the Etkin-Tse-Wang power splitting strategy gives a constant gap of at most 2 bits in the weak interference regime. For the special 3-user case, this gap can be sharpened to 1 1/2 bits by time-sharing of several different strategies. The capacity result of the $K$-user cyclic Gaussian interference channel in the strong interference regime is also given. Further, based on the capacity results, this paper studies the generalized degrees of freedom (GDoF) of the symmetric cyclic interference channel. It is shown that the GDoF of the symmetric capacity is the same as that of the classic two-user interference channel, no matter how many users are in the network.
LR(1) Parser Generation System: LR(1) Error Recovery, Oracles, and Generic Tokens
Venue: arXiv cs.PL 2012
Year: 2012

The LR(1) Parser Generation System generates full LR(1) parsers that are comparable in speed and size to those generated by LALR(1) parser generators, such as yacc [5]. LR contains a number of novel feature. This paper discusses three of them in detail: an LR(1) grammar specified automatic error recovery algorithm, oracles, and generic tokens.
Symmetric Capacity of the Gaussian Interference Channel with an Out-of-Band Relay to within 1.15 Bits
Venue: arXiv cs.IT 2012
Year: 2012

This work studies the Gaussian interference channel (IC) with a relay, which transmits and receives in a band that is orthogonal to the IC. The channel associated with the relay is thus an out-of-band relay channel (OBRC). The focus is on a symmetric channel model, in order to assess the fundamental impact of the OBRC on the signal interaction of the IC, in the simplest possible setting. First, the linear deterministic model is investigated and the sum capacity of this channel is established for all possible channel parameters. In particular, it is observed that the impact of OBRC, as its links get stronger, is similar to that of output feedback for the IC. The insights obtained from the deterministic model are then used to design achievable schemes for the Gaussian model. The interference links are classified as extremely strong, very strong, strong, moderate, weak, and very weak. For strong and moderate interference, separate encoding is near optimal. For very strong and extremely strong interference, the interference links provide side information to the destinations, which can help the transmission through the OBRC. For weak or very weak interference, an extension of the Han-Kobayashi scheme for the IC is utilized, where the messages are split into common and private. To achieve higher rates, it is beneficial to further split the common message into two parts, and the OBRC plays an important role in decoding the common message. It is shown that our strategy achieves the symmetric capacity to within 1.14625 bits per channel use with duplexing factor 0.5, and 1.27125 bits per channel use for arbitrary duplexing factors, for all channel parameters. An important observation from the constant gap result is that strong interference can be beneficial with the presence of an OBR.
On the Capacity of Multiple-Access-Z-Interference Channels
Venue: arXiv cs.IT 2012
Year: 2012

The capacity of a network in which a multiple access channel (MAC) generates interference to a single-user channel is studied. An achievable rate region based on superposition coding and joint decoding is established for the discrete case. If the interference is very strong, the capacity region is obtained for both the discrete memoryless channel and the Gaussian channel. For the strong interference case, the capacity region is established for the discrete memoryless channel; for the Gaussian case, we attain a line segment on the boundary of the capacity region. Moreover, the capacity region for the Gaussian channel is identified for the case when one interference link being strong, and the other being very strong. For a subclass of Gaussian channels with mixed interference, a boundary point of the capacity region is determined. Finally, for the Gaussian channel with weak interference, sum capacities are obtained under various channel coefficient and power constraint conditions.
Gradient Computation In Linear-Chain Conditional Random Fields Using The Entropy Message Passing Algorithm
Venue: arXiv cs.AI 2012
Year: 2012

The paper proposes a numerically stable recursive algorithm for the exact computation of the linear-chain conditional random field gradient. It operates as a forward algorithm over the log-domain expectation semiring and has the purpose of enhancing memory efficiency when applied to long observation sequences. Unlike the traditional algorithm based on the forward-backward recursions, the memory complexity of our algorithm does not depend on the sequence length. The experiments on real data show that it can be useful for the problems which deal with long sequences.
CRAM: Compressed Random Access Memory
Venue: arXiv cs.DS 2012
Year: 2012

We present a new data structure called the \emph{Compressed Random Access Memory} (CRAM) that can store a dynamic string $T$ of characters, e.g., representing the memory of a computer, in compressed form while achieving asymptotically almost-optimal bounds (in terms of empirical entropy) on the compression ratio. It allows short substrings of $T$ to be decompressed and retrieved efficiently and, significantly, characters at arbitrary positions of $T$ to be modified quickly during execution \emph{without decompressing the entire string}. This can be regarded as a new type of data compression that can update a compressed file directly. Moreover, at the cost of slightly increasing the time spent per operation, the CRAM can be extended to also support insertions and deletions. Our key observation that the empirical entropy of a string does not change much after a small change to the string, as well as our simple yet efficient method for maintaining an array of variable-length blocks under length modifications, may be useful for many other applications as well.
Clustering and Latent Semantic Indexing Aspects of the Singular Value Decomposition
Venue: arXiv cs.LG 2012
Year: 2012

This paper discusses clustering and latent semantic indexing (LSI) aspects of the singular value decomposition (SVD). The purpose of this paper is twofold. The first is to give an explanation on how and why the singular vectors can be used in clustering. And the second is to show that the two seemingly unrelated SVD aspects actually originate from the same source: related vertices tend to be more clustered in the graph representation of lower rank approximate matrix using the SVD than in the original semantic graph. Accordingly, the SVD can improve retrieval performance of an information retrieval system since queries made to the approximate matrix can retrieve more relevant documents and filter out more irrelevant documents than the same queries made to the original matrix. By utilizing this fact, we will devise an LSI algorithm that mimicks SVD capability in clustering related vertices. Convergence analysis shows that the algorithm is convergent and produces a unique solution for each input. Experimental results using some standard datasets in LSI research show that retrieval performances of the algorithm are comparable to the SVD's. In addition, the algorithm is more practical and easier to use because there is no need to determine decomposition rank which is crucial in driving retrieval performance of the SVD.
Time-Varying Graphs and Dynamic Networks
Venue: arXiv cs.DC 2012
Year: 2012

The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.
Generating constrained random graphs using multiple edge switches
Venue: arXiv cs.SI 2012
Year: 2012

The generation of random graphs using edge swaps provides a reliable method to draw uniformly random samples of sets of graphs respecting some simple constraints, e.g. degree distributions. However, in general, it is not necessarily possible to access all graphs obeying some given con- straints through a classical switching procedure calling on pairs of edges. We therefore propose to get round this issue by generalizing this classical approach through the use of higher-order edge switches. This method, which we denote by "k-edge switching", makes it possible to progres- sively improve the covered portion of a set of constrained graphs, thereby providing an increasing, asymptotically certain confidence on the statistical representativeness of the obtained sample.
A Type System for the Vectorial Aspect of the Linear-Algebraic Lambda-Calculus
Venue: arXiv cs.LO 2012
Year: 2012

We describe a type system for the linear-algebraic lambda-calculus. The type system accounts for the part of the language emulating linear operators and vectors, i.e. it is able to statically describe the linear combinations of terms resulting from the reduction of programs. This gives rise to an original type theory where types, in the same way as terms, can be superposed into linear combinations. We show that the resulting typed lambda-calculus is strongly normalizing and features a weak subject-reduction.
Formal Theories for Linear Algebra
Venue: arXiv cs.LO 2012
Year: 2012

We introduce two-sorted theories in the style of [CN10] for the complexity classes \oplusL and DET, whose complete problems include determinants over Z2 and Z, respectively. We then describe interpretations of Soltys' linear algebra theory LAp over arbitrary integral domains, into each of our new theories. The result shows equivalences of standard theorems of linear algebra over Z2 and Z can be proved in the corresponding theory, but leaves open the interesting question of whether the theorems themselves can be proved.
From coinductive proofs to exact real arithmetic: theory and applications
Venue: arXiv cs.LO 2012
Year: 2012

Based on a new coinductive characterization of continuous functions we extract certified programs for exact real number computation from constructive proofs. The extracted programs construct and combine exact real number algorithms with respect to the binary signed digit representation of real numbers. The data type corresponding to the coinductive definition of continuous functions consists of finitely branching non-wellfounded trees describing when the algorithm writes and reads digits. We discuss several examples including the extraction of programs for polynomials up to degree two and the definite integral of continuous maps.
Matched Filtering from Limited Frequency Samples
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study a simple correlation-based strategy for estimating the unknown delay and amplitude of a signal based on a small number of noisy, randomly chosen frequency-domain samples. We model the output of this "compressive matched filter" as a random process whose mean equals the scaled, shifted autocorrelation function of the template signal. Using tools from the theory of empirical processes, we prove that the expected maximum deviation of this process from its mean decreases sharply as the number of measurements increases, and we also derive a probabilistic tail bound on the maximum deviation. Putting all of this together, we bound the minimum number of measurements required to guarantee that the empirical maximum of this random process occurs sufficiently close to the true peak of its mean function. We conclude that for broad classes of signals, this compressive matched filter will successfully estimate the unknown delay (with high probability, and within a prescribed tolerance) using a number of random frequency-domain samples that scales inversely with the signal-to-noise ratio and only logarithmically in the in the observation bandwidth and the possible range of delays.
Transductive-Inductive Cluster Approximation Via Multivariate Chebyshev Inequality
Venue: arXiv cs.CV 2012
Year: 2012

Approximating adequate number of clusters in multidimensional data is an open area of research, given a level of compromise made on the quality of acceptable results. The manuscript addresses the issue by formulating a transductive inductive learning algorithm which uses multivariate Chebyshev inequality. Considering clustering problem in imaging, theoretical proofs for a particular level of compromise are derived to show the convergence of the reconstruction error to a finite value with increasing (a) number of unseen examples and (b) the number of clusters, respectively. Upper bounds for these error rates are also proved. Non-parametric estimates of these error from a random sample of sequences empirically point to a stable number of clusters. Lastly, the generalization of algorithm can be applied to multidimensional data sets from different fields.
Throughput-optimal Scheduling in Multi-hop Wireless Networks without Per-flow Information
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we consider the problem of link scheduling in multi-hop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings, and show that the proposed schemes can substantially improve the delay performance in most scenarios.
Evaluation Codes from smooth Quadric Surfaces and Twisted Segre Varieties
Venue: arXiv cs.IT 2012
Year: 2012

We give the parameters of any evaluation code on a smooth quadric surface. For hyperbolic quadrics the approach uses elementary results on product codes and the parameters of codes on elliptic quadrics are obtained by detecting a BCH structure of these codes and using the BCH bound. The elliptic quadric is a twist of the surface P^1 x P^1 and we detect a similar BCH structure on twists of the Segre embedding of a product of any d copies of the projective line.
Zero-Delay Joint Source-Channel Coding for a Bivariate Gaussian on a Gaussian MAC
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, delay-free, low complexity, joint source-channel coding (JSCC) for transmission of two correlated Gaussian memoryless sources over a Gaussian Multiple Access Channel (GMAC) is considered. The main contributions of the paper are two distributed JSCC schemes: one discrete scheme based on nested scalar quantization, and one hybrid discrete-analog scheme based on a scalar quantizer and a linear continuous mapping. The proposed schemes show promising performance which improve with increasing correlation and are robust against variations in noise level. Both schemes exhibit a constant gap to the performance upper bound when the channel signal-to-noise ratio gets large.
Confluence via strong normalisation in an algebraic λ-calculus with rewriting
Venue: arXiv cs.LO 2012
Year: 2012

The linear-algebraic lambda-calculus and the algebraic lambda-calculus are untyped lambda-calculi extended with arbitrary linear combinations of terms. The former presents the axioms of linear algebra in the form of a rewrite system, while the latter uses equalities. When given by rewrites, algebraic lambda-calculi are not confluent unless further restrictions are added. We provide a type system for the linear-algebraic lambda-calculus enforcing strong normalisation, which gives back confluence. The type system allows an abstract interpretation in System F.
Topology Discovery of Sparse Random Graphs With Few Participants
Venue: arXiv cs.SI 2012
Year: 2012

We consider the task of topology discovery of sparse random graphs using end-to-end random measurements (e.g., delay) between a subset of nodes, referred to as the participants. The rest of the nodes are hidden, and do not provide any information for topology discovery. We consider topology discovery under two routing models: (a) the participants exchange messages along the shortest paths and obtain end-to-end measurements, and (b) additionally, the participants exchange messages along the second shortest path. For scenario (a), our proposed algorithm results in a sub-linear edit-distance guarantee using a sub-linear number of uniformly selected participants. For scenario (b), we obtain a much stronger result, and show that we can achieve consistent reconstruction when a sub-linear number of uniformly selected nodes participate. This implies that accurate discovery of sparse random graphs is tractable using an extremely small number of participants. We finally obtain a lower bound on the number of participants required by any algorithm to reconstruct the original random graph up to a given edit distance. We also demonstrate that while consistent discovery is tractable for sparse random graphs using a small number of participants, in general, there are graphs which cannot be discovered by any algorithm even with a significant number of participants, and with the availability of end-to-end information along all the paths between the participants.
The identities of additive binary arithmetics
Venue: arXiv cs.DM 2012
Year: 2012

Operations of arbitrary arity expressible via addition modulo 2^n and bitwise addition modulo 2 admit a simple description. The identities connecting these two additions have finite basis. Moreover, the universal algebra with these two operations is rationally equivalent to a nilpotent ring and, therefore, generates a Specht variety.