Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.