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