Applications of Derandomization Theory in Coding

Applications of Derandomization Theory in Coding. Cheraghchi, M. Ph.D. Thesis, EPFL, Lausanne, Switzerland, 2010.

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.

@phdthesis{ref:Che10:thesis,
  author =	 {Mahdi Cheraghchi},
  title =	 {Applications of Derandomization Theory in Coding},
  school =	 {EPFL},
  url_Link =	 {http://infoscience.epfl.ch/record/149074},
  url_Paper =	 {https://arxiv.org/abs/1107.4709},
  institution =	 {IIF},
  publisher =	 {EPFL},
  address =	 {Lausanne, Switzerland},
  pages =	 210,
  year =	 2010,
  abstract =	 {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.},
  url =		 {http://infoscience.epfl.ch/record/149074},
  doi =		 {10.5075/epfl-thesis-4767}
}

Downloads: 0