Bounds for dispersers, extractors, and depth-two superconcentrators

Abstract

We show that the size of the smallest depth-two $N$-superconcentrator is $$ \Theta(N\log^2 N/\log\log N). $$ Before this work, optimal bounds were known for all depths except two. For the upper bound, we build superconcentrators by putting together a small number of disperser graphs; these disperser graphs are obtained using a probabilistic argument. For obtaining lower bounds, we present two different methods. First, we show that superconcentrators contain several disjoint disperser graphs. When combined with the lower bound for disperser graphs of Kovari, Sós, and Turán, this gives an almost optimal lower bound of $\Omega( N (\log N/\log \log N)^2)$ on the size of $N$-superconcentrators. The second method, based on the work of Hansel, gives the optimal lower bound. The method of Kovari, Sós, and Turán can be extended to give tight lower bounds for extractors, in terms of both the number of truly random bits needed to extract one additional bit and the unavoidable entropy loss in the system. If the input is an $n$-bit source with min-entropy $k$ and the output is required to be within a distance of $\epsilon$ from uniform distribution, then to extract even one additional bit, one must invest at least $\log(n-k) + 2\log(1/\epsilon) - O(1)$ truly random bits; to obtain $m$ output bits one must invest at least $m-k+2\log(1/\epsilon)-O(1)$. Thus, there is a loss of $2\log(1/\epsilon)$ bits during the extraction. Interestingly, in the case of dispersers this loss in entropy is only about $\log\log (1/\epsilon)$.