Home > Applications of Derandomization Theory in Coding > HTML MARC |

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