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 arepseudorandom 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.
1. Introduction 2. Extractor Theory 3. The Wiretap Channel Problem 4. Group Testing 5. Capacity Achieving Codes 6. Codes on the Gilbert-Varshamov Bound 7. Concluding Remarks A. A Primer on Coding Theory
1 Introduction 1 2 Extractor Theory 12 2.1 Probability Distributions . . . . . . . . . . . . . . . . . 13 2.1.1 Distributions and Distance . . . . . . . . . . . . . . . .13 2.1.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Extractors and Condensers . . . . . . . . . . . . . . . . . 18 2.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Almost-Injectivity of Lossless Condensers . . . . . . . . 22 2.3 Constructions . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1 The Leftover Hash Lemma . . . . . . . . . . . . . . . . . 26 2.3.2 Trevisan's Extractor . . . . . . . . . . . . . . . . . . .28 2.3.3 Guruswami-Umans-Vadhan's Condenser . . . . . . . . . . . .35 3 The Wiretap Channel Problem 40 3.1 The Formal Model . . . . . . . . . . . . . . . . . . . . . .42 3.2 Review of the Related Notions in Cryptography . . . . . . . 44 3.3 Symbol-Fixing and Affine Extractors . . . . . . . . . . . . 48 3.3.1 Symbol-Fixing Extractors from Linear Codes . . . . . . . .49 3.3.2 Restricted Affine Extractors from Rank-Metric Codes . . . 50 3.4 Inverting Extractors . . . . . . . . . . . . . . . . . . . .53 3.5 A Wiretap Protocol Based on Random Walks . . . . . . . . . .55 3.6 Invertible Affine Extractors . . . . . . . . . . . . . . . .59 3.7 Further Applications . . . . . . . . . . . . . . . . . . . .62 3.7.1 Noisy Channels and Active Intruders . . . . . . . . . . . 63 3.7.2 Network Coding . . . . . . . . . . . . . . . . . . . . . .64 3.7.3 Arbitrary Processing . . . . . . . . . . . . . . . . . . .67 3.A Some Technical Details . . . . . . . . . . . . . . . . . . .70 4 Group Testing 76 4.1 Measurement Designs and Disjunct Matrices . . . . . . . . . 78 4.1.1 Reconstruction . . . . . . . . . . . . . . . . . . . . . .81 4.1.2 Bounds on Disjunct Matrices . . . . . . . . . . . . . . . 82 4.1.2.1 Upper and Lower Bounds . . . . . . . . . . . . . . . . .82 4.1.2.2 The Fixed-Input Case . . . . . . . . . . . . . . . . . .83 4.1.2.3 Sparsity of the Measurements . . . . . . . . . . . .. . 85 4.2 Noise resilient schemes . . . . . . . . . . . . . . . . . . 86 4.2.1 Negative Results . . . . . . . . . . . . . . . . . . . . .87 4.2.2 A Noise-Resilient Construction . . . . . . . . . . . . . .91 4.2.2.1 Construction from Condensers . . . . . . . . . . . . . .91 4.2.2.2 Instantiations . . . . . . . . . . . . . . . . . . . . .95 4.2.2.3 Measurements Allowing Sublinear Time Reconstruction . . 99 4.2.2.4 Connection with List-Recoverability . . . . . . . . . .100 4.2.2.5 Connection with the Bit-Probe Model and Designs . . . .101 4.3 The Threshold Model . . . . . . . . . . . . . . . . . . . .103 4.3.1 Strongly Disjunct Matrices . . . . . . . . . . . . . . . 103 4.3.2 Strongly Disjunct Matrices from Codes . . . . . . . . . .106 4.3.3 Disjunct Matrices for Threshold Testing . . . . . . . . .111 4.3.3.1 The Definition and Properties . . . . . . . . . . . . .112 4.3.3.2 Constructions . . . . . . . . . . . . . . . . . . . . .115 4.3.3.3 The Case with Positive Gaps . . . . . . . . . . . . . .121 4.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . .123 4.A Some Technical Details . . . . . . . . . . . . . . . . . . 123 5 Capacity Achieving Codes 126 5.1 Discrete Communication Channels . . . . . . . . . . . . . .128 5.2 Codes for the Binary Erasure Channel . . . . . . . . . . . 132 5.3 Codes for the Binary Symmetric Channel . . . . . . . . . . 136 5.4 Explicit Capacity Achieving Codes . . . . . . . . . . . . .141 5.4.1 Justesen's Concatenation Scheme . . . . . . . . . . . . .142 5.4.2 The Analysis . . . . . . . . . . . . . . . . . . . . . . 143 5.4.3 Density of the Explicit Family . . . . . . . . . . . . . 145 5.5 Duality of Linear Affine Condensers . . . . . . . . . . . .146 6 Codes on the Gilbert-Varshamov Bound 150 6.1 Basic Notation . . . . . . . . . . . . . . . . . . . . . . 152 6.2 The Pseudorandom Generator . . . . . . . . . . . . . . . . 154 6.3 Derandomized Code Construction . . . . . . . . . . . . . . 159 7 Concluding Remarks 164 A A Primer on Coding Theory 170 A.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . 170 A.2 Bounds on codes . . . . . . . . . . . . . . . . . . . . . .173 A.3 Reed-Solomon codes . . . . . . . . . . . . . . . . . . . . 175 A.4 The Hadamard Code . . . . . . . . . . . . . . . . . . . . .175 A.5 Concatenated Codes . . . . . . . . . . . . . . . . . . . . 175Number of pages: 206
