דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Derandomizing Algorithms on Product Distributions and Improved Implicit Probe Search using Same-source Extractors for very
event speaker icon
אבינתן חסידים (.M.I.T)
event date icon
יום ראשון, 28.12.2008, 12:00
event location icon
חדר 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
[בחזרה לאינדקס האירועים]