On the Bit Extraction Problem

Abstract:

Consider a coloring of the $n$-dimensional Boolean cube with $c^=^ 2
sup 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^>= theta sub c
^ = ^ (c/2 ^-^ 1)/(c ^-^ 1)$. This resolves the "bit extraction" or
"$t$-resilient functions" problem in many cases, such as $c^-^1^|^n$,
proving that XOR type colorings are optimal. We also study the problem
of finding almost equicolored colorings when $(k^-^ 1)/n^<^ theta sub
c$, and of classifying all optimal colorings.