
On the Bit Extraction Problem
 Postscript version.
 Dvi version.
 PDF version.

Abstract:
Consider a coloring of the $n$dimensional Boolean cube with $c=2^s$ colors
in such a way that every $k$dimensional subcube
is equicolored,
i.e. each color occurs the same number of times.
We show that for such a coloring we necessarily have $(k1)/n \ge \theta_c
= (c/21)/(c1)$.
This resolves the ``bit extraction'' or ``$t$resilient functions'' problem
(also a special case of the ``privacy amplification'' problem)
in many cases, such as $c1n$, proving that XOR type colorings are
optimal, and always resolves this question to within $c/4$ in determining
the optimal value of $k$ (for any fixed $n$ and $c$).
We also study the problem of finding almost equicolored colorings when
$(k1)/n < \theta_c$, and of classifying all optimal colorings.
