DocumentCode :
2422214
Title :
Derandomization and group testing
Author :
Cheraghchi, Mahdi
Author_Institution :
Sch. of Comput. & Commun. Sci., EPFL, Lausanne, Switzerland
fYear :
2010
fDate :
Sept. 29 2010-Oct. 1 2010
Firstpage :
991
Lastpage :
997
Abstract :
The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of “positive” individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using “randomness-conducting” functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.
Keywords :
combinatorial mathematics; program testing; randomised algorithms; combinatorial group testing; derandomization theory; error-correcting group testing; initial intention; lossless condensers; nearly-optimal group testing; randomness extractor; randomness-conducting functions; rapid development; theoretical computer science; Atmospheric measurements; Coordinate measuring machines; Decoding; Graph theory; Loss measurement; Particle measurements; Testing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on
Conference_Location :
Allerton, IL
Print_ISBN :
978-1-4244-8215-3
Type :
conf
DOI :
10.1109/ALLERTON.2010.5707017
Filename :
5707017
Link To Document :
بازگشت