The Taub Faculty of Computer Science Events and Talks

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