On the Bit Extraction Problem

Report ID: TR-357-91

---

Author: Friedman, Joel

---

Date: 1991-12-00

---

Pages: 16

---

Download Formats: |PDF|

---

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.