TY - GEN

T1 - Derandomization via small sample spaces

AU - Alon, Noga

PY - 1996/1/1

Y1 - 1996/1/1

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 -