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

Report ID:

TR-357-91

Authors:

Friedman, Joel [1]

Date:

November 1991

Pages:

16

Download Formats:

[PDF [2]]

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.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/409

[2] ftp://ftp.cs.princeton.edu/techreports/1991/357.pdf