Derandomization via small sample spaces

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


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
Number of pages3
ISBN (Print)3540614222, 9783540614227
StatePublished - 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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this