Derandomization via small sample spaces

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many randomized algorithms run successfully even when the random choices they utilize are not fully independent. For the analysis some limited amount of independence, like k-wise independence for some fixed k, often suffices. In these cases, it is possible to replace the appropriate exponentially large sample spaces required to simulate all random choices of the algorithms by ones of polynomial size. This enables one to derandomize the algorithms, that is, convert them into deterministic ones, by searching the relatively small sample spaces deterministically. If a random variable attains a certain value with positive probability, then we can actually search and find a point in which it attains such a value.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, Andrzej Lingas
PublisherSpringer Verlag
Pages1-3
Number of pages3
ISBN (Print)3540614222, 9783540614227
DOIs
StatePublished - Jan 1 1996
Externally publishedYes
Event5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland
Duration: Jul 3 1996Jul 5 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1097
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th Scandinavian Workshop on Algorithm Theory, SWAT 1996
CountryIceland
CityReykjavik
Period7/3/967/5/96

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Derandomization via small sample spaces'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. (1996). Derandomization via small sample spaces. In R. Karlsson, & A. Lingas (Eds.), Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 1-3). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097). Springer Verlag. https://doi.org/10.1007/3-540-61422-2_115