OpenRaiser/Intern-Atlas huggingface dataset:
A Greedy Omnidirectional Relay Scheme
Venue: arXiv cs.IT 2009
Year: 2009

A greedy omnidirectional relay scheme is developed, and the corresponding achievable rate region is obtained for the all-source all-cast problem. The discussions are first based on the general discrete memoryless channel model, and then applied to the additive white Gaussian noise (AWGN) models, with both full-duplex and half-duplex modes.
Towards a Framework for Observing Artificial Evolutionary Systems
Venue: arXiv cs.NE 2009
Year: 2009

Establishing the emergence of evolutionary behavior as a defining characteristic of 'life' is a major step in the Artificial life (ALife) studies. We present here an abstract formal framework for this aim based upon the notion of high-level observations made on the ALife model at hand during its simulations. An observation process is defined as a computable transformation from the underlying dynamic structure of the model universe to a tuple consisting of abstract components needed to establish the evolutionary processes in the model. Starting with defining entities and their evolutionary relationships observed during the simulations of the model, the framework prescribes a series of definitions, followed by the axioms (conditions) that must be met in order to establish the level of evolutionary behavior in the model. The examples of Cellular Automata based Langton Loops and Lambda calculus based Algorithmic Chemistry are used to illustrate the framework. Generic design suggestions for the ALife research are also drawn based upon the framework design and case study analysis.
Multishot Codes for Network Coding: Bounds and a Multilevel Construction
Venue: arXiv cs.IT 2009
Year: 2009

The subspace channel was introduced by Koetter and Kschischang as an adequate model for the communication channel from the source node to a sink node of a multicast network that performs random linear network coding. So far, attention has been given to one-shot subspace codes, that is, codes that use the subspace channel only once. In contrast, this paper explores the idea of using the subspace channel more than once and investigates the so called multishot subspace codes. We present definitions for the problem, a motivating example, lower and upper bounds for the size of codes, and a multilevel construction of codes based on block-coded modulation.
Degrees of Freedom of a Communication Channel: Using Generalised Singular Values
Venue: arXiv cs.IT 2009
Year: 2009

A fundamental problem in any communication system is: given a communication channel between a transmitter and a receiver, how many "independent" signals can be exchanged between them? Arbitrary communication channels that can be described by linear compact channel operators mapping between normed spaces are examined in this paper. The (well-known) notions of degrees of freedom at level $ε$ and essential dimension of such channels are developed in this general setting. We argue that the degrees of freedom at level $ε$ and the essential dimension fundamentally limit the number of independent signals that can be exchanged between the transmitter and the receiver. We also generalise the concept of singular values of compact operators to be applicable to compact operators defined on arbitrary normed spaces which do not necessarily carry a Hilbert space structure. We show how these generalised singular values can be used to calculate the degrees of freedom at level $ε$ and the essential dimension of compact operators that describe communication channels. We describe physically realistic channels that require such general channel models.
Entropy, Triangulation, and Point Location in Planar Subdivisions
Venue: arXiv cs.CG 2009
Year: 2009

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is H + O(H^{2/3}+1) where H=H(G,D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in G under the query distribution D. The preprocessing algorithm runs in O(n log n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.
Decoding Frequency Permutation Arrays under Infinite norm
Venue: arXiv cs.IT 2009
Year: 2009

A frequency permutation array (FPA) of length $n=mλ$ and distance $d$ is a set of permutations on a multiset over $m$ symbols, where each symbol appears exactly $λ$ times and the distance between any two elements in the array is at least $d$. FPA generalizes the notion of permutation array. In this paper, under the distance metric $\ell_\infty$-norm, we first prove lower and upper bounds on the size of FPA. Then we give a construction of FPA with efficient encoding and decoding capabilities. Moreover, we show our design is locally decodable, i.e., we can decode a message bit by reading at most $λ+1$ symbols, which has an interesting application for private information retrieval.
Coding for Parallel Links to Maximize Expected Decodable-Message Value
Venue: arXiv cs.IT 2009
Year: 2009

Future communication scenarios for NASA spacecraft may involve multiple communication links and relay nodes, so that there is essentially a network in which there may be multiple paths from a sender to a destination. The availability of individual links may be uncertain. In this paper, scenarios are considered in which the goal is to maximize a payoff that assigns weight based on the worth of data and the probability of successful transmission. Ideally, the choice of what information to send over the various links will provide protection of high value data when many links are unavailable, yet result in communication of significant additional data when most links are available. Here the focus is on the simple network of multiple parallel links, where the links have known capacities and outage probabilities. Given a set of simple inter-link codes, linear programming can be used to find the optimal timesharing strategy among these codes. Some observations are made about the problem of determining all potentially useful codes, and techniques to assist in such determination are presented.
A Trace Based Bisimulation for the Spi Calculus
Venue: arXiv cs.CR 2009
Year: 2009

A notion of open bisimulation is formulated for the spi calculus, an extension of the pi-calculus with cryptographic primitives. In this formulation, open bisimulation is indexed by pairs of symbolic traces, which represent the history of interactions between the environment with the pairs of processes being checked for bisimilarity. The use of symbolic traces allows for a symbolic treatment of bound input in bisimulation checking which avoids quantification over input values. Open bisimilarity is shown to be sound with respect to testing equivalence, and futher, it is shown to be an equivalence relation on processes and a congruence relation on finite processes. As far as we know, this is the first formulation of open bisimulation for the spi calculus for which the congruence result is proved.
Iterative Spectrum Shaping with Opportunistic Multiuser Detection
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies a new decentralized resource allocation strategy, named iterative spectrum shaping (ISS), for the multi-carrier-based multiuser communication system, where two coexisting users independently and sequentially update transmit power allocations over parallel subcarriers to maximize their individual transmit rates. Unlike the conventional iterative water-filling (IWF) algorithm that applies the single-user detection (SD) at each user's receiver by treating the interference from the other user as additional noise, the proposed ISS algorithm applies multiuser detection techniques to decode both the desired user's and interference user's messages if it is feasible, thus termed as opportunistic multiuser detection (OMD). Two encoding methods are considered for ISS: One is carrier independent encoding where independent codewords are modulated by different subcarriers for which different decoding methods can be applied; the other is carrier joint encoding where a single codeword is modulated by all the subcarriers for which a single decoder is applied. For each encoding method, this paper presents the associated optimal user power and rate allocation strategy at each iteration of transmit adaptation. It is shown that under many circumstances the proposed ISS algorithm employing OMD is able to achieve substantial throughput gains over the conventional IWF algorithm employing SD for decentralized spectrum sharing. Applications of ISS in cognitive radio communication systems are also discussed.
Feasible alphabets for communicating the sum of sources over a network
Venue: arXiv cs.IT 2009
Year: 2009

We consider directed acyclic {\em sum-networks} with $m$ sources and $n$ terminals where the sources generate symbols from an arbitrary alphabet field $F$, and the terminals need to recover the sum of the sources over $F$. We show that for any co-finite set of primes, there is a sum-network which is solvable only over fields of characteristics belonging to that set. We further construct a sum-network where a scalar solution exists over all fields other than the binary field $F_2$. We also show that a sum-network is solvable over a field if and only if its reverse network is solvable over the same field.
Performance and Construction of Polar Codes on Symmetric Binary-Input Memoryless Channels
Venue: arXiv cs.IT 2009
Year: 2009

Channel polarization is a method of constructing capacity achieving codes for symmetric binary-input discrete memoryless channels (B-DMCs) [1]. In the original paper, the construction complexity is exponential in the blocklength. In this paper, a new construction method for arbitrary symmetric binary memoryless channel (B-MC) with linear complexity in the blocklength is proposed. Furthermore, new upper and lower bounds of the block error probability of polar codes are derived for the BEC and the arbitrary symmetric B-MC, respectively.
Q-CSMA: Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks
Venue: arXiv cs.NI 2009
Year: 2009

Recently, it has been shown that CSMA-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as distributed approximations of greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, they may only achieve a fraction of the capacity region in general. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm which is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single time slot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate mechanisms which lead to very good delay performance while retaining the throughput-optimality property. It also resolves the hidden and exposed terminal problems associated with wireless networks.
MIMO Broadcast Channel Optimization under General Linear Constraints
Venue: arXiv cs.IT 2009
Year: 2009

The optimization of the transmit parameters (power allocation and steering vectors) for the MIMO BC under general linear constraints is treated under the optimal DPC coding strategy and the simple suboptimal linear zero-forcing beamforming strategy. In the case of DPC, we show that "SINR duality" and "min-max duality" yield the same dual MAC problem, and compare two alternatives for its efficient solution. In the case of zero-forcing beamforming, we provide a new efficient algorithm based on the direct optimization of a generalized inverse matrix. In both cases, the algorithms presented here address the problems in the most general form and can be applied to special cases previously considered, such as per-antenna and per-group of antennas power constraints, "forbidden interference direction" constraints, or any combination thereof.
TR01: Time-continuous Sparse Imputation
Venue: arXiv cs.SD 2009
Year: 2009

An effective way to increase the noise robustness of automatic speech recognition is to label noisy speech features as either reliable or unreliable (missing) prior to decoding, and to replace the missing ones by clean speech estimates. We present a novel method to obtain such clean speech estimates. Unlike previous imputation frameworks which work on a frame-by-frame basis, our method focuses on exploiting information from a large time-context. Using a sliding window approach, denoised speech representations are constructed using a sparse representation of the reliable features in an overcomplete basis of fixed-length exemplar fragments. We demonstrate the potential of our approach with experiments on the AURORA-2 connected digit database.
Fast Encoding and Decoding of Gabidulin Codes
Venue: arXiv cs.IT 2009
Year: 2009

Gabidulin codes are the rank-metric analogs of Reed-Solomon codes and have a major role in practical error control for network coding. This paper presents new encoding and decoding algorithms for Gabidulin codes based on low-complexity normal bases. In addition, a new decoding algorithm is proposed based on a transform-domain approach. Together, these represent the fastest known algorithms for encoding and decoding Gabidulin codes.
A Faithful Semantics for Generalised Symbolic Trajectory Evaluation
Venue: arXiv cs.LO 2009
Year: 2009

Generalised Symbolic Trajectory Evaluation (GSTE) is a high-capacity formal verification technique for hardware. GSTE uses abstraction, meaning that details of the circuit behaviour are removed from the circuit model. A semantics for GSTE can be used to predict and understand why certain circuit properties can or cannot be proven by GSTE. Several semantics have been described for GSTE. These semantics, however, are not faithful to the proving power of GSTE-algorithms, that is, the GSTE-algorithms are incomplete with respect to the semantics. The abstraction used in GSTE makes it hard to understand why a specific property can, or cannot, be proven by GSTE. The semantics mentioned above cannot help the user in doing so. The contribution of this paper is a faithful semantics for GSTE. That is, we give a simple formal theory that deems a property to be true if-and-only-if the property can be proven by a GSTE-model checker. We prove that the GSTE algorithm is sound and complete with respect to this semantics.
Capacity Scaling of SDMA in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider an ad hoc network in which each multi-antenna transmitter sends independent streams to multiple receivers in a Poisson field of interferers. We provide the outage probability and transmission capacity scaling laws, aiming at investigating the fundamental limits of Space Division Multiple Access (SDMA). We first show that super linear capacity scaling with the number of receive/transmit antennas can be achieved using dirty paper coding. Nevertheless, the potential benefits of multi-stream, multi-antenna communications fall off quickly if linear precoding is employed, leading to sublinear capacity growth in the case of single-antenna receivers. A key finding is that receive antenna array processing is of vital importance in SDMA ad hoc networks, as a means to cancel the increased residual interference and boost the signal power through diversity.
Some Open Problems in Combinatorial Physics
Venue: arXiv cs.SC 2009
Year: 2009

We point out four problems which have arisen during the recent research in the domain of Combinatorial Physics.
Dirty Paper Coding for Fading Channels with Partial Transmitter Side Information
Venue: arXiv cs.IT 2009
Year: 2009

The problem of Dirty Paper Coding (DPC) over the Fading Dirty Paper Channel (FDPC) Y = H(X + S)+Z, a more general version of Costa's channel, is studied for the case in which there is partial and perfect knowledge of the fading process H at the transmitter (CSIT) and the receiver (CSIR), respectively. A key step in this problem is to determine the optimal inflation factor (under Costa's choice of auxiliary random variable) when there is only partial CSIT. Towards this end, two iterative numerical algorithms are proposed. Both of these algorithms are seen to yield a good choice for the inflation factor. Finally, the high-SNR (signal-to-noise ratio) behavior of the achievable rate over the FDPC is dealt with. It is proved that FDPC (with t transmit and r receive antennas) achieves the largest possible scaling factor of min(t,r) log SNR even with no CSIT. Furthermore, in the high SNR regime, the optimality of Costa's choice of auxiliary random variable is established even when there is partial (or no) CSIT in the special case of FDPC with t <= r. Using the high-SNR scaling-law result of the FDPC (mentioned before), it is shown that a DPC-based multi-user transmission strategy, unlike other beamforming-based multi-user strategies, can achieve a single-user sum-rate scaling factor over the multiple-input multiple-output Gaussian Broadcast Channel with partial (or no) CSIT.
Measuring communication complexity using instance complexity with oracles
Venue: arXiv cs.CC 2009
Year: 2009

We establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let $\overline{x}$, $\overline{y}$ and $Y_1(\overline{x})$ be respectively the input known by Alice, the input known by Bob, and the set of all values of $y$ such that $f(\overline{x},y)=1$; a string is a witness of the non-deterministic communication protocol iff it is a program $p$ that "corresponds exactly" to the instance complexity $\ic^{f,t}(\overline{y}:Y_1(\overline{x}))$.
Average number of flips in pancake sorting
Venue: arXiv cs.DM 2009
Year: 2009

We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down. We present an algorithm with the average number of flips, needed to sort a stack of n burnt pancakes, equal to 7n/4+O(1) and a randomized algorithm for the unburnt version with at most 17n/12+O(1) flips on average. In addition, we show that in the burnt version, the average number of flips of any algorithm is at least n+Ω(n/log n) and conjecture that some algorithm can reach n+Θ(n/log n). We also slightly increase the lower bound on g(n), the minimum number of flips needed to sort the worst stack of n burnt pancakes. This bound, together with the upper bound found by Heydari and Sudborough in 1997, gives the exact number of flips to sort the previously conjectured worst stack -I_n for n=3 mod 4 and n>=15. Finally we present exact values of f(n) up to n=19 and of g(n) up to n=17 and disprove a conjecture of Cohen and Blum by showing that the burnt stack -I_{15} is not the worst one for n=15.
Low-SNR Analysis of Interference Channels under Secrecy Constraints
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the secrecy rates over weak Gaussian interference channels for different transmission schemes. We focus on the low-SNR regime and obtain the minimum bit energy E_b/N_0_min values, and the wideband slope regions for both TDMA and multiplexed transmission schemes. We show that secrecy constraints introduce a penalty in both the minimum bit energy and the slope regions. Additionally, we identify under what conditions TDMA or multiplexed transmission is optimal. Finally, we show that TDMA is more likely to be optimal in the presence of secrecy constraints.
Matrix Completion from a Few Entries
Venue: arXiv cs.LG 2009
Year: 2009

Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE <= C(rn/|E|)^0.5 . Further, if r=O(1), M can be reconstructed exactly from |E| = O(n log(n)) entries. These results apply beyond random matrices to general low-rank incoherent matrices. This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log(n)), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.
Limits of Deterministic Compressed Sensing Considering Arbitrary Orthonormal Basis for Sparsity
Venue: arXiv cs.IT 2009
Year: 2009

It is previously shown that proper random linear samples of a finite discrete signal (vector) which has a sparse representation in an orthonormal basis make it possible (with probability 1) to recover the original signal. Moreover, the choice of the linear samples does not depend on the sparsity domain. In this paper, we will show that the replacement of random linear samples with deterministic functions of the signal (not necessarily linear) will not result in unique reconstruction of k-sparse signals except for k=1. We will show that there exist deterministic nonlinear sampling functions for unique reconstruction of 1- sparse signals while deterministic linear samples fail to do so.
Homotopy methods for multiplication modulo triangular sets
Venue: arXiv cs.SC 2009
Year: 2009

We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given to notably addition of algebraic numbers in small characteristic.
The Complexity of Computing Minimal Unidirectional Covering Sets
Venue: arXiv cs.CC 2009
Year: 2009

Given a binary dominance relation on a set of alternatives, a common thread in the social sciences is to identify subsets of alternatives that satisfy certain notions of stability. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer [BF08] proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal upward or downward covering set. For both problems, we raise this lower bound to the Theta_{2}^{p} level of the polynomial hierarchy and provide a Sigma_{2}^{p} upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size covering sets are hard or complete for either of NP, coNP, and Theta_{2}^{p}. An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer's result that minimal bidirectional covering sets (i.e., sets that are both minimal upward and minimal downward covering sets) are polynomial-time computable.