OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Verification-based Decoding on the q-ary Symmetric Channel for Large q
Venue: arXiv cs.IT 2011
Year: 2011

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, we provide an analysis of the node-based algorithms from that paper and verify that it matches simulation results. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.
From Multi-Keyholes to Measure of Correlation and Power Imbalance in MIMO Channels: Outage Capacity Analysis
Venue: arXiv cs.IT 2011
Year: 2011

An information-theoretic analysis of a multi-keyhole channel, which includes a number of statistically independent keyholes with possibly different correlation matrices, is given. When the number of keyholes or/and the number of Tx/Rx antennas is large, there is an equivalent Rayleigh-fading channel such that the outage capacities of both channels are asymptotically equal. In the case of a large number of antennas and for a broad class of fading distributions, the instantaneous capacity is shown to be asymptotically Gaussian in distribution, and compact, closed-form expressions for the mean and variance are given. Motivated by the asymptotic analysis, a simple, full-ordering scalar measure of spatial correlation and power imbalance in MIMO channels is introduced, which quantifies the negative impact of these two factors on the outage capacity in a simple and well-tractable way. It does not require the eigenvalue decomposition, and has the full-ordering property. The size-asymptotic results are used to prove Telatar's conjecture for semi-correlated multi-keyhole and Rayleigh channels. Since the keyhole channel model approximates well the relay channel in the amplify-and-forward mode in certain scenarios, these results also apply to the latter
Noise-Resilient Group Testing: Limitations and Constructions
Venue: arXiv cs.DM 2011
Year: 2011

We study combinatorial group testing schemes for learning $d$-sparse Boolean vectors using highly unreliable disjunctive measurements. We consider an adversarial noise model that only limits the number of false observations, and show that any noise-resilient scheme in this model can only approximately reconstruct the sparse vector. On the positive side, we take this barrier to our advantage and show that approximate reconstruction (within a satisfactory degree of approximation) allows us to break the information theoretic lower bound of $\tildeΩ(d^2 \log n)$ that is known for exact reconstruction of $d$-sparse vectors of length $n$ via non-adaptive measurements, by a multiplicative factor $\tildeΩ(d)$. Specifically, we give simple randomized constructions of non-adaptive measurement schemes, with $m=O(d \log n)$ measurements, that allow efficient reconstruction of $d$-sparse vectors up to $O(d)$ false positives even in the presence of $δm$ false positives and $O(m/d)$ false negatives within the measurement outcomes, for any constant $δ< 1$. We show that, information theoretically, none of these parameters can be substantially improved without dramatically affecting the others. Furthermore, we obtain several explicit constructions, in particular one matching the randomized trade-off but using $m = O(d^{1+o(1)} \log n)$ measurements. We also obtain explicit constructions that allow fast reconstruction in time $\poly(m)$, which would be sublinear in $n$ for sufficiently sparse vectors. The main tool used in our construction is the list-decoding view of randomness condensers and extractors.
On upper bounds for parameters related to construction of special maximum matchings
Venue: arXiv cs.DM 2011
Year: 2011

For a graph $G$ let $L(G)$ and $l(G)$ denote the size of the largest and smallest maximum matching of a graph obtained from $G$ by removing a maximum matching of $G$. We show that $L(G)\leq 2l(G),$ and $L(G)\leq (3/2)l(G)$ provided that $G$ contains a perfect matching. We also characterize the class of graphs for which $L(G)=2l(G)$. Our characterization implies the existence of a polynomial algorithm for testing the property $L(G)=2l(G)$. Finally we show that it is $NP$-complete to test whether a graph $G$ containing a perfect matching satisfies $L(G)=(3/2)l(G)$.
Capacity Achieving Codes From Randomness Condensers
Venue: arXiv cs.IT 2011
Year: 2011

We establish a general framework for construction of small ensembles of capacity achieving linear codes for a wide range of (not necessarily memoryless) discrete symmetric channels, and in particular, the binary erasure and symmetric channels. The main tool used in our constructions is the notion of randomness extractors and lossless condensers that are regarded as central tools in theoretical computer science. Same as random codes, the resulting ensembles preserve their capacity achieving properties under any change of basis. Using known explicit constructions of condensers, we obtain specific ensembles whose size is as small as polynomial in the block length. By applying our construction to Justesen's concatenation scheme (Justesen, 1972) we obtain explicit capacity achieving codes for BEC (resp., BSC) with almost linear time encoding and almost linear time (resp., quadratic time) decoding and exponentially small error probability.
Invertible Extractors and Wiretap Protocols
Venue: arXiv cs.IT 2011
Year: 2011

A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. In this paper we study the notion of efficiently invertible extractors and show that a wiretap protocol can be constructed from such an extractor. We will then construct invertible extractors for symbol-fixing, affine, and general sources and apply them to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). We will then apply our results to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding, network coding, and intruders observing arbitrary boolean functions of the encoding. As a by-product of our constructions we obtain new explicit extractors for a restricted family of affine sources over large fields (that in particular generalizes the notion of symbol-fixing sources) which is of independent interest. These extractors are able to extract the entire source entropy with zero error. Keywords: Wiretap Channel, Extractors, Network Coding, Active Intrusion, Exposure Resilient Cryptography.
Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds
Venue: arXiv cs.IT 2011
Year: 2011

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by "unwrapping" the QC code.
AxialGen: A Research Prototype for Automatically Generating the Axial Map
Venue: arXiv cs.RO 2011
Year: 2011

AxialGen is a research prototype for automatically generating the axial map, which consists of the least number of the longest visibility lines (or axial lines) for representing individual linearly stretched parts of open space of an urban environment. Open space is the space between closed spaces such as buildings and street blocks. This paper aims to provide an accessible guide to software AxialGen, and the underlying concepts and ideas. We concentrate on the explanation and illustration of the key concept of bucket: its definition, formation and how it is used in generating the axial map. Keywords: Bucket, visibility, medial axes, axial lines, isovists, axial map
Dependency Pairs and Polynomial Path Orders
Venue: arXiv cs.LO 2011
Year: 2011

We show how polynomial path orders can be employed efficiently in conjunction with weak innermost dependency pairs to automatically certify polynomial runtime complexity of term rewrite systems and the polytime computability of the functions computed. The established techniques have been implemented and we provide ample experimental data to assess the new method.
Reengineering PDF-Based Documents Targeting Complex Software Specifications
Venue: arXiv cs.DL 2011
Year: 2011

This article aims at reengineering of PDF-based complex documents, where specifications of the Object Management Group (OMG) are our initial targets. Our motivation is that such specifications are dense and intricate to use, and tend to have complicated structures. Our objective is therefore to create an approach that allows us to reengineer PDF-based documents, and to illustrate how to make more usable versions of electronic documents (such as specifications, technical books, etc) so that end users to have a better experience with them. The first step was to extract the logical structure of the document in a meaningful XML format for subsequent processing. Our initial assumption was that, many key concepts of a document are expressed in this structure. In the next phase, we created a multilayer hypertext version of the document to facilitate browsing and navigating. Although we initially focused on OMG software specifications, we chose a general approach for different phases of our work including format conversions, logical structure extraction, text extraction, multilayer hypertext generation, and concept exploration. As a consequence, we can process other complex documents to achieve our goals.
Wireless Network Information Flow: A Deterministic Approach
Venue: arXiv cs.IT 2011
Year: 2011

In a wireless network with a single source and a single destination and an arbitrary number of relay nodes, what is the maximum rate of information flow achievable? We make progress on this long standing problem through a two-step approach. First we propose a deterministic channel model which captures the key wireless properties of signal strength, broadcast and superposition. We obtain an exact characterization of the capacity of a network with nodes connected by such deterministic channels. This result is a natural generalization of the celebrated max-flow min-cut theorem for wired networks. Second, we use the insights obtained from the deterministic analysis to design a new quantize-map-and-forward scheme for Gaussian networks. In this scheme, each relay quantizes the received signal at the noise level and maps it to a random Gaussian codeword for forwarding, and the final destination decodes the source's message based on the received signal. We show that, in contrast to existing schemes, this scheme can achieve the cut-set upper bound to within a gap which is independent of the channel parameters. In the case of the relay channel with a single relay as well as the two-relay Gaussian diamond network, the gap is 1 bit/s/Hz. Moreover, the scheme is universal in the sense that the relays need no knowledge of the values of the channel parameters to (approximately) achieve the rate supportable by the network. We also present extensions of the results to multicast networks, half-duplex networks and ergodic networks.
Bit Copying - The Ultimate Computational Simplicity
Venue: arXiv cs.PL 2011
Year: 2011

A computational abstract machine based on two operations: referencing and bit copying is presented. These operations are sufficient for carrying out any computation. They can be used as the primitives for a Turing-complete programming language. The interesting point is that the computation can be done without logic operations such as AND or OR. The compiler and emulator of this language with sample programs are available on the Internet.
Parallel Opportunistic Routing in Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

We study benefits of opportunistic routing in a large wireless ad hoc network by examining how the power, delay, and total throughput scale as the number of source- destination pairs increases up to the operating maximum. Our opportunistic routing is novel in a sense that it is massively parallel, i.e., it is performed by many nodes simultaneously to maximize the opportunistic gain while controlling the inter-user interference. The scaling behavior of conventional multi-hop transmission that does not employ opportunistic routing is also examined for comparison. Our results indicate that our opportunistic routing can exhibit a net improvement in overall power--delay trade-off over the conventional routing by providing up to a logarithmic boost in the scaling law. Such a gain is possible since the receivers can tolerate more interference due to the increased received signal power provided by the multi-user diversity gain, which means that having more simultaneous transmissions is possible.
Fountain Communication using Concatenated Codes
Venue: arXiv cs.IT 2011
Year: 2011

This paper extends linear-complexity concatenated coding schemes to fountain communication over the discrete-time memoryless channel. Achievable fountain error exponents for one-level and multi-level concatenated fountain codes are derived. It is also shown that concatenated coding schemes possess interesting properties in several multi-user fountain communication scenarios.
Why Did My Query Slow Down?
Venue: arXiv cs.DB 2011
Year: 2011

Many enterprise environments have databases running on network-attached server-storage infrastructure (referred to as Storage Area Networks or SANs). Both the database and the SAN are complex systems that need their own separate administrative teams. This paper puts forth the vision of an innovative management framework to simplify administrative tasks that require an in-depth understanding of both the database and the SAN. As a concrete instance, we consider the task of diagnosing the slowdown in performance of a database query that is executed multiple times (e.g., in a periodic report-generation setting). This task is very challenging because the space of possible causes includes problems specific to the database, problems specific to the SAN, and problems that arise due to interactions between the two systems. In addition, the monitoring data available from these systems can be noisy. We describe the design of DIADS which is an integrated diagnosis tool for database and SAN administrators. DIADS generates and uses a powerful abstraction called Annotated Plan Graphs (APGs) that ties together the execution path of queries in the database and the SAN. Using an innovative workflow that combines domain-specific knowledge with machine-learning techniques, DIADS was applied successfully to diagnose query slowdowns caused by complex combinations of events across a PostgreSQL database and a production SAN.
Prioritized Repairing and Consistent Query Answering in Relational Databases
Venue: arXiv cs.DB 2011
Year: 2011

A consistent query answer in an inconsistent database is an answer obtained in every (minimal) repair. The repairs are obtained by resolving all conflicts in all possible ways. Often, however, the user is able to provide a preference on how conflicts should be resolved. We investigate here the framework of preferred consistent query answers, in which user preferences are used to narrow down the set of repairs to a set of preferred repairs. We axiomatize desirable properties of preferred repairs. We present three different families of preferred repairs and study their mutual relationships. Finally, we investigate the complexity of preferred repairing and computing preferred consistent query answers.
A New Approach to Random Access: Reliable Communication and Reliable Collision Detection
Venue: arXiv cs.IT 2011
Year: 2011

This paper applies Information Theoretic analysis to packet-based random multiple access communication systems. A new channel coding approach is proposed for coding within each data packet with built-in support for bursty traffic properties, such as message underflow, and for random access properties, such as packet collision detection. The coding approach does not require joint communication rate determination either among the transmitters or between the transmitters and the receiver. Its performance limitation is characterized by an achievable region defined in terms of communication rates, such that reliable packet recovery is supported for all rates inside the region and reliable collision detection is supported for all rates outside the region. For random access communication over a discrete-time memoryless channel, it is shown that the achievable rate region of the introduced coding approach equals the Shannon information rate region without a convex hull operation. Further connections between the achievable rate region and the Shannon information rate region are developed and explained.
Construction of Additive Reed-Muller Codes
Venue: arXiv cs.IT 2011
Year: 2011

The well known Plotkin construction is, in the current paper, generalized and used to yield new families of Z2Z4-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of Z2Z4-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family.
The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems
Venue: arXiv cs.DM 2011
Year: 2011

We study the interplay between principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S_3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized.
Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control
Venue: arXiv cs.IT 2011
Year: 2011

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of network coding and seriously undermine both reliability and security of data. Hence error control for network coding is vital. Recently, constant-dimension codes (CDCs), especially Kötter-Kschischang (KK) codes, have been proposed for error control in random linear network coding. KK codes can also be constructed from Gabidulin codes, an important class of rank metric codes. Rank metric decoders have been recently proposed for both Gabidulin and KK codes, but they have high computational complexities. Furthermore, it is not clear whether such decoders are feasible and suitable for hardware implementations. In this paper, we reduce the complexities of rank metric decoders and propose novel decoder architectures for both codes. The synthesis results of our decoder architectures for Gabidulin and KK codes with limited error-correcting capabilities over small fields show that our architectures not only are affordable, but also achieve high throughput.
Bayesian Algorithmic Mechanism Design
Venue: arXiv cs.GT 2011
Year: 2011

The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. This field is motivated by the observation that the preeminent approach for designing incentive compatible mechanisms, namely that of Vickrey, Clarke, and Groves; and the central approach for circumventing computational obstacles, that of approximation algorithms, are fundamentally incompatible: natural applications of the VCG approach to an approximation algorithm fails to yield an incentive compatible mechanism. We consider relaxing the desideratum of (ex post) incentive compatibility (IC) to Bayesian incentive compatibility (BIC), where truthtelling is a Bayes-Nash equilibrium (the standard notion of incentive compatibility in economics). For welfare maximization in single-parameter agent settings, we give a general black-box reduction that turns any approximation algorithm into a Bayesian incentive compatible mechanism with essentially the same approximation factor.
A unifying approach to picture grammars
Venue: arXiv cs.FL 2011
Year: 2011

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using a tiling based approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling,named regional, and define the corresponding regional tile grammars. They include both Siromoney's (or Matz's) Kolam grammars and their generalization by Prusa, as well as Drewes's grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).