License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2340
URN: urn:nbn:de:0030-drops-23407
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2340/

Wigderson, Avi

Randomness extractors -- applications and constructions

pdf-format:
Dokument 1.pdf (118 KB)


Abstract

Randomness extractors are efficient algorithms which convert weak random sources into nearly perfect ones. While such purification of randomness was the original motivation for constructing extractors, these constructions turn out to have strong pseudorandom properties which found applications in diverse areas of computer science and combinatorics. We will highlight some of the applications, as well as recent constructions achieving near-optimal extraction.

BibTeX - Entry

@InProceedings{wigderson:LIPIcs:2009:2340,
  author =	{Avi Wigderson},
  title =	{{Randomness extractors -- applications and constructions}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{471--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2340},
  URN =		{urn:nbn:de:0030-drops-23407},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2340},
  annote =	{Keywords: Randomness extractors, weak random sources, purification of randomness}
}

Keywords: Randomness extractors, weak random sources, purification of randomness
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue date: 2009
Date of publication: 14.12.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI