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 $(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.