• Calendar

May 10, Tuesday
12:00 – 14:00

A distribution $X$ over binary strings of length $n$ is a $\delta$-source if every string has probability at most $2^{-\delta n}$. We give the following new explicit constructions (namely, poly(n)-time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate $\delta >0$. No previous explicit construction was known for either of these, for any $\delta<1/2$. The first two constitute major progress to very long-standing open problems.

1. (Bipartite Ramsey) $f_1: ({0,1}^n)2 \rightarrow {0,1}$, such that for any two independent $\delta$-sources $X_1, X_2$ we have $f_1(X_1,X_2) = {0,1}$. This implies a new explicit construction of $2N$-vertex bipartite graphs where no induced $N^{\delta}$ by $N^{\delta}$ subgraph is complete or empty.
2. (Multiple source extraction) $f_2: ({0,1}^n)3 \rightarrow {0,1}$, such that for any three independent $\delta$-sources $X_1,X_2,X_3$ we have that $f_2(X_1,X_2,X_3)$ is ($o(1)$-close to being) an unbiased random bit.
3. (Constant seed condenser) $f_3: {0,1}^n \rightarrow ({0,1}^m))^c$, such that for any $\delta$-source $X$, one of the $c$ output distributions $f_3(X)_i$, is a $0.9$-source over ${0,1}^m$. Here $c$ is a constant depending only on $\delta$.
4. (Subspace Ramsey) $f_4: {0,1}^n \rightarrow {0,1}$, such that for any affine subspace $X$ of dimension at least $\delta n$, $f_4(X)={0,1}$.

The constructions are quite involved and use as building blocks other new and known gadgets. But we can point out two important themes which recur in these constructions. One is that gadgets which were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The second is using the input to (introspectively) find high entropy regions within itself.

Joint work with Boaz Barak, Guy Kindler, Benny Sudakov and Avi Wigderson.

Bio:
My PhD is from Hebrew University, advisor: Avi Wigderson. The thesis is on "Explicit constructions of pseudorandom generators and extractors". During my PhD studies I stayed for two years at the IAS at Princeton. Following my PhD I did 3 years of Postdoc in the Weizmann Institute under Oded Goldreich and Moni Naor. I now have a faculty position at Haifa.