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 - http://www.scopus.com/inward/record.url?scp=84947926020&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947926020&partnerID=8YFLogxK
U2 - 10.1007/3-540-61422-2_115
DO - 10.1007/3-540-61422-2_115
M3 - Conference contribution
AN - SCOPUS:84947926020
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 -