Paper Info
Title
Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction
Abstract
Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithm/protocol is given multiple inputs sampled independently from an arbitrary unknown distribution. We show that in this case a strong and generic derandomization result can be obtained by a simple argument. Our method relies on extracting randomness from "same-source" product distributions, which are distributions generated from multiple independent samples from the same source. The extraction process succeeds even for arbitrarily low min-entropy, and is based on the order of the values and not on the values themselves (this may be seen as a generalization of the classical method of Von-Neumann (26) extended by Elias (8) for extracting randomness from a biased coin.) The tools developed in the paper are generic, and can be used in several other problems. We present applica- tions to streaming algorithms, and to implicit probe search (9). We also refine our method to handle product distributions, where the i'th sample comes from one of several arbitrary unknown distributions. This requires creating a new set of tools, which may also be of independent interest.
Year
Venue
Keywords
2010
I4CS
extractors,derandomization,product distribution,communication protocol,streaming algorithm
Field
DocType
Citations 
Streaming algorithm,Computer science,Algorithm,Theoretical computer science,Communications protocol,Randomness
Conference
0
PageRank 
References 
Authors
0.34
25
2
Name
Order
Citations
PageRank
Ariel Gabizon115613.97
Avinatan Hassidim247550.17