000149074 001__ 149074
000149074 005__ 20190717172520.0
000149074 0247_ $$2doi$$a10.5075/epfl-thesis-4767
000149074 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis4767-7
000149074 02471 $$2nebis$$a6064534
000149074 037__ $$aTHESIS
000149074 041__ $$aeng
000149074 088__ $$a4767
000149074 245__ $$aApplications of Derandomization Theory in Coding
000149074 269__ $$a2010
000149074 260__ $$bEPFL$$c2010$$aLausanne
000149074 300__ $$a210
000149074 336__ $$aTheses
000149074 520__ $$aRandomized 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.
000149074 6531_ $$aderandomization theory
000149074 6531_ $$arandomness extractors
000149074 6531_ $$apseudorandomness
000149074 6531_ $$awiretap channels
000149074 6531_ $$agroup testing
000149074 6531_ $$aerror-correcting codes
000149074 6531_ $$athéorie de dérandomisation
000149074 6531_ $$aextracteurs d'aléa
000149074 6531_ $$apseudo-aléa
000149074 6531_ $$acanaux à jarretière
000149074 6531_ $$atest en groupe
000149074 6531_ $$acodes correcteurs d'erreurs
000149074 700__ $$0243422$$g166246$$aCheraghchi Bashi Astaneh, Mahdi
000149074 720_2 $$aShokrollahi, Mohammad Amin$$edir.$$g156849$$0241952
000149074 8564_ $$zTexte intégral / Full text$$yTexte intégral / Full text$$uhttps://infoscience.epfl.ch/record/149074/files/EPFL_TH4767.pdf$$s2108830
000149074 909C0 $$xU10735$$pALGO$$0252198
000149074 909CO $$pthesis-bn2018$$pthesis-public$$pDOI$$pIC$$ooai:infoscience.tind.io:149074$$qDOI2$$qGLOBAL_SET$$pthesis
000149074 918__ $$dEDIC2005-2015$$cIIF$$aSB
000149074 919__ $$aALGO
000149074 920__ $$b2010
000149074 970__ $$a4767/THESES
000149074 973__ $$sPUBLISHED$$aEPFL
000149074 980__ $$aTHESIS