Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Derandomizing Algorithms on Product Distributions and Improved Implicit Probe Search using Same-source Extractors for very
event speaker icon
Avinatan Hassidim (M.I.T.)
event date icon
Sunday, 28.12.2008, 12:00
event location icon
Taub 601
An important goal in algorithms and communication protocols is getting the deterministic time complexity, respectively communication complexity, closer to the best known randomized complexity. In this work, we investigate the case where instead of one input, the algorithm \ protocol is given multiple \emph{independent} samples from an \emph{arbitrary unknown} distribution. We show that in this case a strong derandomization result can be obtained by a simple argument. Our method involved extracting randomness from `same-source'-distributions - distributions that consist of multiple independent samples from the same source - that have very low min-entropy. Such extractors enable us to get new non-trivial \emph{implicit probe schemes} \cite{FiaNao93}. Using a slightly more complicated argument we get similar results for product distributions consisting of several different distributions.

Joint work with Ariel Gabizon