@comment{ generated by }
@PhDThesis{4767/THESES,
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.},
address = {Lausanne},
affiliation = {EPFL},
author = {Cheraghchi Bashi Astaneh, Mahdi},
details = {http://infoscience.epfl.ch/record/149074},
doctoral = {EDIC2005-2015},
documenturl = {https://infoscience.epfl.ch/record/149074/files/EPFL_TH4767.pdf},
doi = {10.5075/epfl-thesis-4767},
extra-id = {6064534},
institute = {IIF},
keywords = {derandomization theory; randomness extractors;
pseudorandomness; wiretap channels; group testing;
error-correcting codes; théorie de dérandomisation;
extracteurs d'aléa; pseudo-aléa; canaux à
jarretière; test en groupe; codes correcteurs
d'erreurs},
language = {eng},
oai-id = {oai:infoscience.epfl.ch:149074},
oai-set = {IC},
original-unit = {ALGO},
pagecount = {210},
production-date = 2010,
publisher = {EPFL},
school = {SB},
status = {PUBLISHED},
thesis-id = {4767},
title = {Applications of {D}erandomization {T}heory in {C}oding},
unit = {ALGO},
urn = {urn:nbn:ch:bel-epfl-thesis4767-7},
year = 2010
}