On the Bit Extraction Problem
• Postscript version.
• Dvi version.
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 $(k-1)/n \ge \theta_c = (c/2-1)/(c-1)$. This resolves the bit extraction'' or $t$-resilient functions'' problem (also a special case of the privacy amplification'' problem) in many cases, such as $c-1|n$, 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 $(k-1)/n < \theta_c$, and of classifying all optimal colorings.