OpenRaiser/Intern-Atlas huggingface dataset:
Low-Density Graph Codes for slow fading Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

We study Low-Density Parity-Check (LDPC) codes with iterative decoding on block-fading (BF) Relay Channels. We consider two users that employ coded cooperation, a variant of decode-and-forward with a smaller outage probability than the latter. An outage probability analysis for discrete constellations shows that full diversity can be achieved only when the coding rate does not exceed a maximum value that depends on the level of cooperation. We derive a new code structure by extending the previously published full-diversity root-LDPC code, designed for the BF point-to-point channel, to exhibit a rate-compatibility property which is necessary for coded cooperation. We estimate the asymptotic performance through a new density evolution analysis and the word error rate performance is determined for finite length codes. We show that our code construction exhibits near-outage limit performance for all block lengths and for a range of coding rates up to 0.5, which is the highest possible coding rate for two cooperating users.
How random are a learner's mistakes?
Venue: arXiv cs.LG 2011
Year: 2011

Given a random binary sequence $X^{(n)}$ of random variables, $X_{t},$ $t=1,2,...,n$, for instance, one that is generated by a Markov source (teacher) of order $k^{*}$ (each state represented by $k^{*}$ bits). Assume that the probability of the event $X_{t}=1$ is constant and denote it by $β$. Consider a learner which is based on a parametric model, for instance a Markov model of order $k$, who trains on a sequence $x^{(m)}$ which is randomly drawn by the teacher. Test the learner's performance by giving it a sequence $x^{(n)}$ (generated by the teacher) and check its predictions on every bit of $x^{(n)}.$ An error occurs at time $t$ if the learner's prediction $Y_{t}$ differs from the true bit value $X_{t}$. Denote by $ξ^{(n)}$ the sequence of errors where the error bit $ξ_{t}$ at time $t$ equals 1 or 0 according to whether the event of an error occurs or not, respectively. Consider the subsequence $ξ^{(ν)}$ of $ξ^{(n)}$ which corresponds to the errors of predicting a 0, i.e., $ξ^{(ν)}$ consists of the bits of $ξ^{(n)}$ only at times $t$ such that $Y_{t}=0.$ In this paper we compute an estimate on the deviation of the frequency of 1s of $ξ^{(ν)}$ from $β$. The result shows that the level of randomness of $ξ^{(ν)}$ decreases relative to an increase in the complexity of the learner.
Error-and-Erasure Decoding for Block Codes with Feedback
Venue: arXiv cs.IT 2011
Year: 2011

Inner and outer bounds are derived on the optimal performance of fixed length block codes on discrete memoryless channels with feedback and errors-and-erasures decoding. First an inner bound is derived using a two phase encoding scheme with communication and control phases together with the optimal decoding rule for the given encoding scheme, among decoding rules that can be represented in terms of pairwise comparisons between the messages. Then an outer bound is derived using a generalization of the straight-line bound to errors-and-erasures decoders and the optimal error exponent trade off of a feedback encoder with two messages. In addition upper and lower bounds are derived, for the optimal erasure exponent of error free block codes in terms of the rate. Finally we present a proof of the fact that the optimal trade off between error exponents of a two message code does not increase with feedback on DMCs.
Dynamic FTSS in Asynchronous Systems: the Case of Unison
Venue: arXiv cs.DS 2011
Year: 2011

Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components. In this paper, we present the first study of dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present many impossibility results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
Feedback Vertex Sets in Tournaments
Venue: arXiv cs.DM 2011
Year: 2011

We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs. On the combinatorial side, we derive strong upper and lower bounds on the maximum number of minimal feedback vertex sets in an n-vertex tournament. We prove that every tournament on n vertices has at most 1.6740^n minimal feedback vertex sets, and that there is an infinite family of tournaments, all having at least 1.5448^n minimal feedback vertex sets. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal feedback vertex sets of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum size feedback vertex set in a tournament.
Cooperative encoding for secrecy in interference channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the fundamental performance limits of the two-user interference channel in the presence of an external eavesdropper. In this setting, we construct an inner bound, to the secrecy capacity region, based on the idea of cooperative encoding in which the two users cooperatively design their randomized codebooks and jointly optimize their channel prefixing distributions. Our achievability scheme also utilizes message-splitting in order to allow for partial decoding of the interference at the non-intended receiver. Outer bounds are then derived and used to establish the optimality of the proposed scheme in certain cases. In the Gaussian case, the previously proposed cooperative jamming and noise-forwarding techniques are shown to be special cases of our proposed approach. Overall, our results provide structural insights on how the interference can be exploited to increase the secrecy capacity of wireless networks.
On Relaxing Metric Information in Linear Temporal Logic
Venue: arXiv cs.LO 2011
Year: 2011

Metric LTL formulas rely on the next operator to encode time distances, whereas qualitative LTL formulas use only the until operator. This paper shows how to transform any metric LTL formula M into a qualitative formula Q, such that Q is satisfiable if and only if M is satisfiable over words with variability bounded with respect to the largest distances used in M (i.e., occurrences of next), but the size of Q is independent of such distances. Besides the theoretical interest, this result can help simplify the verification of systems with time-granularity heterogeneity, where large distances are required to express the coarse-grain dynamics in terms of fine-grain time units.
Capacity of a Class of Linear Binary Field Multi-source Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

Characterizing the capacity region of multi-source wireless relay networks is one of the fundamental issues in network information theory. The problem is, however, quite challenging due to inter-user interference when there exist multiple source--destination (S--D) pairs in the network. By focusing on a special class of networks, we show that the capacity can be found. Namely, we study a layered linear binary field network with time-varying channels, which is a simplified model reflecting broadcast, interference, and fading natures of wireless communications. We observe that fading can play an important role in mitigating inter-user interference effectively for both single-hop and multi-hop networks. We propose new encoding and relaying schemes with randomized channel pairing, which exploit such channel variations, and derive their achievable rates. By comparing them with the cut-set upper bound, the capacity region of single-hop networks and the sum capacity of multi-hop networks can be characterized for some classes of channel distributions and network topologies. For these classes, we show that the capacity region or sum capacity can be interpreted as the max-flow min-cut theorem.
An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
Venue: arXiv cs.CC 2011
Year: 2011

We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant's algebraic analog of the P not equal to NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate.
Complexity Classes of Equivalence Problems Revisited
Venue: arXiv cs.CC 2011
Year: 2011

To determine if two lists of numbers are the same set, we sort both lists and see if we get the same result. The sorted list is a canonical form for the equivalence relation of set equality. Other canonical forms arise in graph isomorphism algorithms, and the equality of permutation groups given by generators. To determine if two graphs are cospectral (have the same eigenvalues), however, we compute their characteristic polynomials and see if they are the same; the characteristic polynomial is a complete invariant for the equivalence relation of cospectrality. This is weaker than a canonical form, and it is not known whether a polynomial-time canonical form for cospectrality exists. Note that it is a priori possible for an equivalence relation to be decidable in polynomial time without either a complete invariant or canonical form. Blass and Gurevich (SIAM J. Comput., 1984) ask whether these conditions on equivalence relations -- having an FP canonical form, having an FP complete invariant, and simply being in P -- are in fact different. They showed that this question requires non-relativizing techniques to resolve. Here we extend their results, and give new connections to probabilistic and quantum computation.
Concatenated Coding for the AWGN Channel with Noisy Feedback
Venue: arXiv cs.IT 2011
Year: 2011

The use of open-loop coding can be easily extended to a closed-loop concatenated code if the channel has access to feedback. This can be done by introducing a feedback transmission scheme as an inner code. In this paper, this process is investigated for the case when a linear feedback scheme is implemented as an inner code and, in particular, over an additive white Gaussian noise (AWGN) channel with noisy feedback. To begin, we look to derive an optimal linear feedback scheme by optimizing over the received signal-to-noise ratio. From this optimization, an asymptotically optimal linear feedback scheme is produced and compared to other well-known schemes. Then, the linear feedback scheme is implemented as an inner code to a concatenated code over the AWGN channel with noisy feedback. This code shows improvements not only in error exponent bounds, but also in bit-error-rate and frame-error-rate. It is also shown that the if the concatenated code has total blocklength L and the inner code has blocklength, N, the inner code blocklength should scale as N = O(C/R), where C is the capacity of the channel and R is the rate of the concatenated code. Simulations with low density parity check (LDPC) and turbo codes are provided to display practical applications and their error rate benefits.
The Kalman Like Particle Filter : Optimal Estimation With Quantized Innovations/Measurements
Venue: arXiv cs.IT 2011
Year: 2011

We study the problem of optimal estimation and control of linear systems using quantized measurements, with a focus on applications over sensor networks. We show that the state conditioned on a causal quantization of the measurements can be expressed as the sum of a Gaussian random vector and a certain truncated Gaussian vector. This structure bears close resemblance to the full information Kalman filter and so allows us to effectively combine the Kalman structure with a particle filter to recursively compute the state estimate. We call the resulting filter the Kalman like particle filter (KLPF) and observe that it delivers close to optimal performance using far fewer particles than that of a particle filter directly applied to the original problem. We show that the conditional state density follows a, so called, generalized closed skew-normal (GCSN) distribution. We further show that for such systems the classical separation property between control and estimation holds and that the certainty equivalent control law is LQG optimal.
Interference Alignment for the $K$ User MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider the $K$-user Multiple Input Multiple Output (MIMO) Gaussian interference channel with $M$ antennas at each transmitter and $N$ antennas at each receiver. It is assumed that channel coefficients are constant and are available at all transmitters and at all receivers. The main objective of this paper is to characterize the Degrees of Freedom (DoF) for this channel. Using a new interference alignment technique which has been recently introduced in \cite{abolfazl-final}, we show that $\frac{MN}{M+N} K$ degrees of freedom can be achieved for almost all channel realizations. Also, a new upper-bound on the DoF of this channel is provided. This upper-bound coincides with our achievable DoF for $K\geq K_u\define\frac{M+N}{\gcd(M,N)}$, where $\gcd(M,N)$ denotes the greatest common divisor of $M$ and $N$. This gives an exact characterization of DoF for $M\times N$ MIMO Gaussian interference channel in the case of $K\geq K_u$.
Pseudorandom Generators for Polynomial Threshold Functions
Venue: arXiv cs.CC 2011
Year: 2011

We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)} fooling degree d PTFs with error at most eps. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error eps. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter eps and obtain a PRG with seed-length O(log n + log^2(1/eps)). Previously, only PRGs with seed length O(log n log^2(1/eps)/eps^2) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the n-dimensional unit sphere. The main theme of our constructions and analysis is the use of invariance principles to construct pseudorandom generators. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate eps for halfspaces. These techniques may be of independent interest.
Spatial games and global optimization for mobile association problems
Venue: arXiv cs.GT 2011
Year: 2011

The basic optimal transportation problem consists in finding the most effective way of moving masses from one location to another, while minimizing the transportation cost. Such concept has been found to be useful to understand various mathematical, economical, and control theory phenomena, such as Witsenhausen's counterexam-ple in stochastic control theory, principal-agent problem in microeco- nomic theory, location and planning problems, etc. In this work, we focus on mobile association problems: the determina-tion of the cells corresponding to each base station, i.e., the locations at which intelligent mobile terminals prefer to connect to a given base station rather than to others. This work combines game theory and optimal transport theory to characterize the solution based on fluid approximations. We characterize the optimal solution from both the global network and the mobile user points of view.
Capturing Polynomial Time on Interval Graphs
Venue: arXiv cs.LO 2011
Year: 2011

We prove a characterization of all polynomial-time computable queries on the class of interval graphs by sentences of fixed-point logic with counting. More precisely, it is shown that on the class of unordered interval graphs, any query is polynomial-time computable if and only if it is definable in fixed-point logic with counting. This result is one of the first establishing the capturing of polynomial time on a graph class which is defined by forbidden induced subgraphs. For this, we define a canonical form of interval graphs using a type of modular decomposition, which is different from the method of tree decomposition that is used in most known capturing results for other graph classes, specifically those defined by forbidden minors. The method might also be of independent interest for its conceptual simplicity. Furthermore, it is shown that fixed-point logic with counting is not expressive enough to capture polynomial time on the classes of chordal graphs or incomparability graphs.
Statistical exponential families: A digest with flash cards
Venue: arXiv cs.LG 2011
Year: 2011

This document describes concisely the ubiquitous class of exponential family distributions met in statistics. The first part recalls definitions and summarizes main properties and duality with Bregman divergences (all proofs are skipped). The second part lists decompositions and related formula of common exponential family distributions. We recall the Fisher-Rao-Riemannian geometries and the dual affine connection information geometries of statistical manifolds. It is intended to maintain and update this document and catalog by adding new distribution items.
Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes
Venue: arXiv cs.IT 2011
Year: 2011

Suppose Alice wishes to send messages to Bob through a communication channel C_1, but her transmissions also reach an eavesdropper Eve through another channel C_2. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of Eve's equivocation ratio. Wyner showed that the situation is characterized by a single constant C_s, called the secrecy capacity, which has the following meaning: for all $ε> 0$, there exist coding schemes of rate $R \ge C_s - ε$ that asymptotically achieve both the reliability and the security objectives. However, his proof of this result is based upon a nonconstructive random-coding argument. To date, despite a considerable research effort, the only case where we know how to construct coding schemes that achieve secrecy capacity is when Eve's channel C_2 is an erasure channel, or a combinatorial variation thereof. Polar codes were recently invented by Arikan; they approach the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. Herein, we use polar codes to construct a coding scheme that achieves the secrecy capacity for a wide range of wiretap channels. Our construction works for any instantiation of the wiretap channel model, as long as both C_1 and C_2 are symmetric and binary-input, and C_2 is degraded with respect to C_1. Moreover, we show how to modify our construction in order to provide strong security, in the sense defined by Maurer, while still operating at a rate that approaches the secrecy capacity. In this case, we cannot guarantee that the reliability condition will be satisfied unless the main channel C_1 is noiseless, although we believe it can be always satisfied in practice.
Truthful Assignment without Money
Venue: arXiv cs.GT 2011
Year: 2011

We study the design of truthful mechanisms that do not use payments for the generalized assignment problem (GAP) and its variants. An instance of the GAP consists of a bipartite graph with jobs on one side and machines on the other. Machines have capacities and edges have values and sizes; the goal is to construct a welfare maximizing feasible assignment. In our model of private valuations, motivated by impossibility results, the value and sizes on all job-machine pairs are public information; however, whether an edge exists or not in the bipartite graph is a job's private information. We study several variants of the GAP starting with matching. For the unweighted version, we give an optimal strategyproof mechanism; for maximum weight bipartite matching, however, we show give a 2-approximate strategyproof mechanism and show by a matching lowerbound that this is optimal. Next we study knapsack-like problems, which are APX-hard. For these problems, we develop a general LP-based technique that extends the ideas of Lavi and Swamy to reduce designing a truthful mechanism without money to designing such a mechanism for the fractional version of the problem, at a loss of a factor equal to the integrality gap in the approximation ratio. We use this technique to obtain strategyproof mechanisms with constant approximation ratios for these problems. We then design an O(log n)-approximate strategyproof mechanism for the GAP by reducing, with logarithmic loss in the approximation, to our solution for the value-invariant GAP. Our technique may be of independent interest for designing truthful mechanisms without money for other LP-based problems.
States and exceptions considered as dual effects
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we consider the two major computational effects of states and exceptions, from the point of view of diagrammatic logics. We get a surprising result: there exists a symmetry between these two effects, based on the well-known categorical duality between products and coproducts. More precisely, the lookup and update operations for states are respectively dual to the throw and catch operations for exceptions. This symmetry is deeply hidden in the programming languages; in order to unveil it, we start from the monoidal equational logic and we add progressively the logical features which are necessary for dealing with either effect. This approach gives rise to a new point of view on states and exceptions, which bypasses the problems due to the non-algebraicity of handling exceptions.
Divide-and-conquer: Approaching the capacity of the two-pair bidirectional Gaussian relay network
Venue: arXiv cs.IT 2011
Year: 2011

The capacity region of multi-pair bidirectional relay networks, in which a relay node facilitates the communication between multiple pairs of users, is studied. This problem is first examined in the context of the linear shift deterministic channel model. The capacity region of this network when the relay is operating at either full-duplex mode or half-duplex mode for arbitrary number of pairs is characterized. It is shown that the cut-set upper-bound is tight and the capacity region is achieved by a so called divide-and-conquer relaying strategy. The insights gained from the deterministic network are then used for the Gaussian bidirectional relay network. The strategy in the deterministic channel translates to a specific superposition of lattice codes and random Gaussian codes at the source nodes and successive interference cancelation at the receiving nodes for the Gaussian network. The achievable rate of this scheme with two pairs is analyzed and it is shown that for all channel gains it achieves to within 3 bits/sec/Hz per user of the cut-set upper-bound. Hence, the capacity region of the two-pair bidirectional Gaussian relay network to within 3 bits/sec/Hz per user is characterized.