Applications of Derandomization Theory in Coding

Randomized techniques play a fundamental role in theoretical computer science and discrete mathematics, in particular for the design of efficient algorithms and construction of combinatorial objects. The basic goal in derandomization theory is to eliminate or reduce the need for randomness in such randomized constructions. Towards this goal, numerous fundamental notions have been developed to provide a unified framework for approaching various derandomization problems and to improve our general understanding of the power of randomness in computation. Two important classes of such tools are pseudorandom generators and randomness extractors. Pseudorandom generators transform a short, purely random, sequence into a much longer sequence that looks random, while extractors transform a weak source of randomness into a perfectly random one (or one with much better qualities, in which case the transformation is called a randomness condenser). In this thesis, we explore some applications of the fundamental notions in derandomization theory to problems outside the core of theoretical computer science, and in particular, certain problems related to coding theory. First, we consider the wiretap channel problem which involves a communication system in which an intruder can eavesdrop a limited portion of the transmissions. We utilize randomness extractors to construct efficient and information-theoretically optimal communication protocols for this model. Then we consider the combinatorial group testing problem. In this classical problem, one aims to determine a set of defective items within a large population by asking a number of queries, where each query reveals whether a defective item is present within a specified group of items. We use randomness condensers to explicitly construct optimal, or nearly optimal, group testing schemes for a setting where the query outcomes can be highly unreliable, as well as the threshold model where a query returns positive if the number of defectives pass a certain threshold. Next, we use randomness condensers and extractors to design ensembles of error-correcting codes that achieve the information-theoretic capacity of a large class of communication channels, and then use the obtained ensembles for construction of explicit capacity achieving codes. Finally, we consider the problem of explicit construction of error-correcting codes on the Gilbert-Varshamov bound and extend the original idea of Nisan and Wigderson to obtain a small ensemble of codes, mostly achieving the bound, under suitable computational hardness assumptions.

Derandomization and Group Testing

Mahdi Cheraghchi Bashi Astaneh

The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of "positive" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using "randomness-conducting" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.

2010

Re-proving Channel Polarization Theorems

Mine Alsan

The general subject considered in this thesis is a recently discovered coding technique, polar coding, which is used to construct a class of error correction codes with unique properties. In his ground-breaking work, Arikan proved that this class of codes, called polar codes, achieve the symmetric capacity --- the mutual information evaluated at the uniform input distribution ---of any stationary binary discrete memoryless channel with low complexity encoders and decoders requiring in the order of

O(N\log N)

operations in the block-length

N

. This discovery settled the long standing open problem left by Shannon of finding low complexity codes achieving the channel capacity. Polar codes are not only appealing for being the first to 'close the deal'. In contrast to most of the existing coding schemes, polar codes admit an explicit low complexity construction. In addition, for symmetric channels, the polar code construction is deterministic; the theoretically beautiful but practically limited "average performance of an ensemble of codes is good, so there must exist one particular code in the ensemble at least as good as the average'' formalism of information theory is bypassed. Simulations are thus not necessary in principle for evaluating the error probability which is shown in a study by Telatar and Arikan to scale exponentially in the square root of the block-length. As such, at the time of this writing, polar codes are appealing for being the only class of codes proved, and proved with mathematical elegance, to possess all of these properties. Polar coding settled an open problem in information theory, yet opened plenty of challenging problems that need to be addressed. This novel coding scheme is a promising method from which, in addition to data transmission, problems such as data compression or compressed sensing, which includes all types of measurement processes like the MRI or ultrasound, could benefit in terms of efficiency. To make this technique fulfill its promise, the original theory has been, and should still be, extended in multiple directions. A significant part of this thesis is dedicated to advancing the knowledge about this technique in two directions. The first one provides a better understanding of polar coding by generalizing some of the existing results and discussing their implications, and the second one studies the robustness of the theory over communication models introducing various forms of uncertainty or variations into the probabilistic model of the channel. See the fulltext of the thesis for the complete abstract.

EPFL2015

Locally Testable Codes

Mahdi Cheraghchi Bashi Astaneh

Error correcting codes are combinatorial objects that allow reliable recovery of information in presence of errors by cleverly augmenting the original information with a certain amount of redundancy. The availability of efficient means of error detection is considered as a fundamental criterion for error correcting codes. Locally testable codes are families of error correcting codes that are highly robust against transmission errors and in addition provide super-efficient (sublinear time) probabilistic algorithms for error detection. In particular, the error detection algorithm probes the received sequence only at a small (or even constant) number of locations. There seems to be a trade-off between the amount of redundancy and the number of probes for the error detection procedure in locally testable codes. Even though currently best constructions allow reduction of redundancy to a nearly linear amount, it is not clear whether this can be further reduced to linear while preserving a constant number of probes. We study the formal notion of locally testable codes and survey several major results in this area. We also investigate closely related concepts, and in particular, polynomial low-degree tests and probabilistically checkable proofs.

2005

Re-proving Channel Polarization Theorems

Mine Alsan

O(N\log N)

operations in the block-length

N

EPFL2015