Derandomization via small sample spaces

Noga Alon

doi:10.1007/3-540-61422-2_115

Derandomization via small sample spaces

Noga Alon

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	American English
Title of host publication	Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Rolf Karlsson, Andrzej Lingas
Publisher	Springer Verlag
Pages	1-3
Number of pages	3
ISBN (Print)	3540614222, 9783540614227
DOIs	https://doi.org/10.1007/3-540-61422-2_115
State	Published - 1996
Externally published	Yes
Event	5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland Duration: Jul 3 1996 → Jul 5 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1097

Other

Other	5th Scandinavian Workshop on Algorithm Theory, SWAT 1996
Country/Territory	Iceland
City	Reykjavik
Period	7/3/96 → 7/5/96

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-61422-2_115

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

@inproceedings{fdfbc3181f154816a9da747624428d85,

title = "Derandomization via small sample spaces",

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.",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 ; Conference date: 03-07-1996 Through 05-07-1996",

year = "1996",

doi = "10.1007/3-540-61422-2\_115",

language = "American English",

isbn = "3540614222",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1--3",

editor = "Rolf Karlsson and Andrzej Lingas",

booktitle = "Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "Germany",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1097, Springer Verlag, pp. 1-3, 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996, Reykjavik, Iceland, 7/3/96. https://doi.org/10.1007/3-540-61422-2_115

Derandomization via small sample spaces. / Alon, Noga.
Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Rolf Karlsson; Andrzej Lingas. Springer Verlag, 1996. p. 1-3 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1097).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Derandomization via small sample spaces

AU - Alon, Noga

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84947926020

UR - https://www.scopus.com/pages/publications/84947926020#tab=citedBy

U2 - 10.1007/3-540-61422-2_115

DO - 10.1007/3-540-61422-2_115

M3 - Conference contribution

SN - 3540614222

SN - 9783540614227

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 3

BT - Algorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Karlsson, Rolf

A2 - Lingas, Andrzej

PB - Springer Verlag

T2 - 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

Y2 - 3 July 1996 through 5 July 1996

ER -

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

Derandomization via small sample spaces

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this