Answers are grounded in this paper and cite their sources.
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< theta /sub c/, and of classifying all optimal colorings.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
No takes yet. Share an insight, caveat, or question.
Joel Friedman (1992) studied this question.