Derandomization and group testing
File(s)1010.0433v1.pdf (148.7 KB)
Accepted version
Author(s)
Cheraghchi, M
Type
Conference Paper
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. ©2010 IEEE.
Date Issued
2010-12-01
Date Acceptance
2010-09-29
Citation
2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010, 2010, pp.991-997
ISBN
9781424482153
Publisher
IEEE
Start Page
991
End Page
997
Journal / Book Title
2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Copyright Statement
© 2010 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Source
Annual Allerton Conference on Communication, Control, and Computing
Subjects
cs.IT
math.IT
Publication Status
Published
Start Date
2010-09-29
Finish Date
2010-10-01
Coverage Spatial
Allerton, IL, USA
Date Publish Online
2011-02-04