On the bit extraction problem
Joel I. Friedman · 1992
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. The author shows that for such a coloring one necessarily has (k-1)/n>or= theta /sub 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). He also studies the problem of finding almost equicolored colorings when (k-1)/n>