On the Bit Extraction Problem

Joel Friedman^{∗}

Department of Computer Science Princeton University Princeton, NJ 08544

Abstract

Consider a coloring of the n-dimensional Boolean cube with c = 2^{s} colors in such a way that every kdimensional 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 ≥ θ_{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). We also study the problem of finding almost equicolored colorings when (k − 1)/n < θ_{c}, and of classifying all optimal colorings.

1 Introduction

The bit extraction problem of [Vaz85], aka tresilient functions problem (see [CFG^{+}85]), aka a special case of the privacy amplification problem (see [BBR88],[Bra89]) is equivalent to the following coloring problem. The vertices of the Boolean cube, B^{n} = {−1, 1}^{n} are to be colored with c = 2^{s} colors such that every k-dimensional subcube is equicolored. Given n and c, what is the smallest value of k for which this possible? Here, by a k-dimensional subcube we mean a subset of B^{n} determined by fixing the values of some n − k coordinates on B^{n}; we denote the set of all such subcubes by H_{k}. By equicolored we mean that every color appears the same number of times in the subcube, i.e. 2^{k}/c times.

To fix ideas, we refer to such a coloring as a (c; n, k)- coloring and write κ(c, n) for the smallest value of k achievable for a given n and c. In this paper we are primarily interested in viewing c as small or fixed, studying κ as a function of n. We will study this problem and the problem of constructing colorings which are approximately equicolorable.

To elaborate on the context in which the problem arises, consider n boolean variables, X = {x_{1}, …, x_{n}}, whose values are set by the following process. An adversary fixes some subset of the variables, T ⊂ X, to specific values, neither the values nor T being knowing to us; then the remaining variables are randomly set to boolean values, independently and uniformly. Knowing only the size of T, t = |T |, we wish to extract s unbiased bits from X for s as large as possible; i.e. we wish to find a function f: B^{n} → B^{s} such that for any setting of any t of the variables of X in the above process, our f takes on each value in B^{s} with probability 1/2^{s}. For example, to extract one unbiased bit for any T of size ≤ n−1, we can take f = x_{1} ⊕⋯⊕x_{n}, where ⊕ denotes the XOR (exclusive-OR); as long as there is one bit which is not set by the adversary, this f will be unbiased. While the obvious lower bound s ≤ n − t is achieved in extracting s = 1 bit, one cannot in general attain s = n − t. In [CFG^{+}85] it proven that to extract s = 2 bits requires t < 2n/3 (we assume 3|n for simplicity); one can achieve this taking f = (f_{1}, f_{2}), with f_{1} the XOR of the first 2n/3 of the variables, and f_{2} that of the last 2n/3 of them. The bit extraction problem is equivalent to our coloring problem since constructing an f as above gives a (2^{s}; n, k) coloring with k = n − t, and vice versa (and thus the name “t-resilent function”).

This coloring problem also arises in a cryptographic context (as in [BBR88],[Bra89]): player A communicates to player B via a channel of n bits, x_{1}, …, x_{n}, but there is a spy who is able to see some t of the n bits, A and B not knowing which bits the spy can see. A and B would like the spy to obtain no information about the true message, say a message of s < n bits. In other words, A must takes a message of s bits, encode this to a message of n bits, using some source of randomness, send this through the channel to B, who then applies a decoding function to obtain the original s bit message; we require a scheme in which the spy obtains no information about the s bit message. For example, to communicate one bit, y ∈ B, A can pick x_{1}, …, x_{n−1} at random and then set x_{n} to be the XOR of y and x_{1}, …, x_{n−1}, which B will decode by computing the XOR of x_{1}, …, x_{n}. Constructing such an encoding and decoding for general s turns out to be equivalent to the coloring problem, again with c = 2^{s} and k = n − t.

∗The author also wishes to acknowledge the National Science Foundation for supporting this research in part under a PYI grant, CCR–8858788.

Returning to the coloring problem, consider the colorings by f: B^{n} → B^{s}, identifying B^{s} with the set of colors, for those f’s formed by XOR’s of the variables, i.e. f = (f_{1}, …, f_{s}) with each f_{i} being an XOR of a subset of the variables; we call such a coloring an XOR coloring. Let κ_{XOR}(c, n) denote the smallest value of k that an XOR coloring can achieve given c, n. It has been conjectured (e.g. [Vaz85]) that κ_{XOR}(c, n) = κ(c, n) for all c, n, i.e. that that XOR colorings can always achieve the optimal k; as mentioned before, this was proven for all n with c = 4 in [CFG^{+}85] (and is clear for c = 2).

It is easy to determine κ_{XOR}(c, n) to within O(c). For example, for n divisible by c − 1, it is easy to see that κ_{XOR}(c, n) = nθ_{c}+1, where θ_{c} = (c/2−1)/(c−1). It follows that κ_{XOR}(c, n) is always within (c − 2)/2 of nθ_{c} + 1.

Here we prove:

Theorem 1.1 For any (c; n, k) coloring we have (k − 1)/n ≥ θ_{c}, i.e. κ(c, n) ≥ nθ_{c} + 1.

Corollary 1.2 For c − 1|n, n > 0, XOR colorings are optimal. For any n, c, XOR colorings are within (c − 2)/2 of optimal.

It is a non-trivial problem to determine κ_{XOR}(c, n) exactly for general n, but one can do so in certain cases to obtain other bounds as a corollary. For example, one gets:

Proposition 1.3 For n ≥ 2 and ≡ −2, −1, 0, 1, c/2− 1, c/2, c/2 + 1 (mod c − 1), we have κ_{XOR}(c, n) = 1 + ⌈nθ_{c}⌉ and hence = κ(c, n). For n > 2 and ≡ 2 (mod c − 1) with c ≥ 8, κ_{XOR}(c, n) = 2 + ⌈nθ_{c}⌉, and hence κ_{XOR}(c, n) is at worst within 1 of κ(c, n). For c = 8 the former and latter congruences hold according to whether n ≢ 2 (mod 7) or not. For any n, c, κ_{XOR}(c, n) is within c/4 of κ(c, n).

In particular, n ≡ 2 (mod 7) is the simplest case in which we don’t know if XOR colorings are optimal.

We are also interested in two related problems:

Problem 1.4 For k < κ(c, n), how close (in various metrics involving H_{k}) to equicolorable can be achieved by a c-coloring of B^{n}?

Problem 1.5 Classify all optimal colorings, at least for c − 1|n. Are there optimal colorings not obtainable as XOR type colorings?

The author knows of no optimal colorings other than XOR colorings. Of course, if one views n and k as fixed and asks for the optimal c, then there exist optimal colorings which are not XOR colorings (e.g. k = (n/3) − 1 with 3|n and n large, so that c = 1 is the optimal c).

In this paper we study problem 1.4 for the metric L^{2}(H_{k}) (defined in section 3). We give a lower bound on the distance to “equicolor” one can achieve for k < κ(c, n). One remarkable fact is:

Theorem 1.6 For c − 1|n, the optimal XOR coloring is closest to equicolorable in L^{2}(H_{k}) for any k.

Both this theorem and theorem 1.1 are proven using the eigenvalues and eigenspaces of the adjacency matrix of the B^{n}. Such methods can yield other inequalities expressable in terms of the distance distribution (see section 3) of a subset of B^{n}. For example, the fact that the average influence of a variable on a boolean function which is 1 on half of the values is at least 1/n (see [KKL88]) follows immediately from the fact that the sum of the influences is just ((n − A)χ_{c}, χ_{c}) = 2^{n} ∑_{r>0} 2rμ_{r} ≥ 2^{n} ∑_{r>0} 2μ_{r} = 2^{n}, using the notation of section 2, where C is the subset of B^{n} where the function takes the value 1.

In general, XOR colorings are not closest to equicolor for many important metrics, such as the RP(H_{k}) metric defined in section 3 (already for the case n = c = 4, k = 2). Roughly speaking, the problem is that for k one less than what can be achieved by the best XOR coloring for fixed c, n, the best XOR colorings are equicolored on almost all HH_{k}, but on the other H’s they avoid half the colors! It would be interesting to know about the closest to equicolor colorings for various sup-type norms, such as RP(H_{k}) or L^{∞}(H_{k}), and to give an explicit constructions.

In the proof that XOR colorings are optimal for c = 4 of [CFG^{+}85], one produces from an optimal coloring f_{1}, f_{2} two subsets of variables X_{1}, X_{2} whose XOR’s yield an optimal coloring (any X_{1}, X_{2} with the Fourier coefficient of f_{1}, f_{2}, f_{1} + f_{2} non-vanishing at, respectively, X_{1}, X_{2}, X_{1} + X_{2} will do). This proof does not directly generalize because of the possibility of cancellation of Fourier coefficients in computing a convolution, and theorem 1.1 somehow precludes very bad cancellation. It would be nice to find a generalization of the method in [CFG^{+}85], understanding precisely how much cancellation can occur in such convolutions. In our paper there is no explicit reference to Fourier coefficients of the f_{i}’s. They occur only implicitly, in that the eigenspace of the adjacency matrix of B^{n} corresponding to the eigenvalue n − 2r is precisely the (R-linear) span of the collection of all XOR’s of r variables.

In section 2 we give a short proof of theorem 1.1 and prove some facts about the optimal XOR colorings, proving proposition 1.3. In section 3 study the approximate equicoloring problem for L^{2}. To do so we study, for a subset C ⊂ B^{n}, its distance distribution. It seems that studying “higher-order” distance distributions may shed light on approximate equicolorings in other norms; for this and other intriguing relations between the distance distribution and the bit extraction problem, the reader is referred to the full version of the paper, [Fri91]. In section 4 we make some remarks about problem 1.5, giving a simple geometric characterization of all XOR colorings.

The author wishes to thank Kai Li, Bernard Chazelle, and Avi Wigderson for useful comments and discussions.

2 The Bit Extraction Problem

We begin by proving theorem 1.1. We do this via a somewhat stronger statement. We say that a subset C ⊂ B^{n} is 1/c dense in H_{k} if

\frac{|C ∩ H|}{|H|} = \frac{1}{c} ∀H ∈ H_{k}.

Theorem 2.1 If there exists a 1/c dense in H_{k} subset of B^{n}, then (k − 1)/n ≥ θ_{c}.

Theorem 1.1 follows by taking C to be the set of vertices of any fixed color of a (c; n, k) coloring. Proof Consider the adjacency matrix, A of the Boolean cube, and χ_{C}, the characteristic function of C in B^{n}. Clearly (Aχ_{C}, χ_{C}) ≥ 0. On the other hand, the eigenvalues of A are n−2r with r = 0, 1, … n, and the corresponding eigenspaces, E_{r}, are just the spans of all XOR’s of r variables, viewing B as {−1, +1}. It follows that if v_{r} is the projection of χ_{C} onto E_{r}, then the assumption that C is 1/c dense in H_{k} implies that v_{1} = ⋯ = v_{n−k} = 0 (and conversely^{1}). Setting μ_{r} = |v_{r}|^{2}/|χ_{c}|^{2}, we have

∑_{r=0}^{n} μ_{r} = \frac{∑ |v_{r}|^{2}}{|χ_{C}|^{2}} = 1

and

(Aχ_{C}, χ_{C}) = ∑_{r=0}^{n}(n − 2r)|v_{r}|^{2} = |χ_{C}|^{2} ∑_{r=0}^{n}(n − 2r)μ_{r}.

Also, E_{0} corresponds to the trivial eigenvector, (1, …, 1), and so μ_{0} = |C|/n = 1/c; this and μ_{1} = ⋯ = μ_{n−k} = 0 give

0 ≤ nμ_{0} + ∑_{r=n−k+1}^{n}(n − 2r)μ_{r} ≤

nμ_{0}+(2k−2−n) ∑_{r=n−k+1}^{n} μ_{r} = n\frac{1}{c} +(2k−2−n)\frac{c − 1}{c},

and so

2(k − 1)\frac{c − 1}{c} ≥ n\frac{c − 2}{c},

which is the desired result.

□

We will now evaluate κ_{XOR}(c, n) for some special values of n to deduce corollary 1.2 and proposition 1.3. First recall that in general f_{1}, …, f_{s} yield an H_{k} equicolored coloring iff all XOR’s of a subsets of {f_{1}, …, f_{s}} yields a function which is half 1, half -1 on every H ∈ H_{k} (see, for example, [CFG^{+}85]; this is just to say that the standard 2^{s} × 2^{s} Hadamard matrix is invertible). So for a subset T ⊂ S = {1, …, s}, consider the XOR of the f_{i} with i ∈ T, which we denote f_{T}. If the f_{i} are XOR’s of a subsets the variables X = {x_{1}, …, x_{n}}, then so is each f_{T}. Furthermore, an XOR of the variables is half 1, half -1 on H_{k} iff it is the XOR of at least n − k + 1 variables. This reduces the analysis of optimal XOR colorings to a question about the possible Venn diagrams of s subsets, X_{1}, …, X_{s}, of X, X_{i} being the subset of variables of which f_{i} is an XOR (which is equivalent to a question about error correcting codes, as in [CFG^{+}85]).

Namely, for a non-empty T ⊂ S, consider the size of the corresponding component of the Venn diagram on the X_{i}’s,

I_{T} = | (∩_{i∈T} X_{i}) ∩ (∩_{i∉T} \overline{X}_{i}) |,

where \overline{X}_{i} is the complement of X_{i} in X. The X_{i}’s correspond to an H_{k} equicolored coloring iff for all U ⊂ S,

∑_{|T ∩U|≡1 (mod 2)} I_{T} ≥ n − (k − 1).  (2.1)

Furthermore if there exist non-negative, integral I_{T} satisfying the above equation with n ≥ k, then clearly there exists a (c; n, k) XOR coloring.

1“Conversely” follows from the invertibility of the standard 2^{n} × 2^{n} Hadamard matrix. In modern lingo, all the weight 1 thru n−k Fourier coefficients vanish for the function taking the value 1 on C and 0 elsewhere, as in [CFG^{+}85], section 5.1.

Summing the above over all U shows that

κ_{XOR}(c, n) ≥ 1 + nθ_{c},  (2.2)

and if equality holds then each of the inequalities of equation 2.1 holds with equality; the invertibiliy of the standard Hadamard matrix implies that equality holding in all the above inequalities necessitates I_{T} = n/(c − 1). So for c − 1|n, any choice of X_{i} with I_{T} = n/(c − 1) for all T yields an optimal coloring, and any optimal coloring occurs in this way. For c−1|n we use the term balanced XOR coloring for any optimal XOR coloring, to emphasise the fact that all I_{T} ’s are equal. Furthermore we have

Proposition 2.2 For n ≥ 2 and ≡ −2, −1, 0, 1, c/2− 1, c/2, c/2 + 1 (mod c − 1), κ_{XOR}(c, n) = 1 + ⌈nθ_{c}⌉, and thus optimal colorings can be achieved by XOR colorings in these cases.

Proof All cases follow easily from the case n = c/2 and the trivial case n = c − 1. For n = c/2 we take the “odd coloring,” namely I_{T} is = 1, 0 according to whether or not |T | is odd. It is easy to see than any U has |T ∩ U| odd for at least half the T with |T | odd, and so κ_{XOR}(c, c/2) ≤ c/4+1. Rest of details omitted.

□

For general n the problem of determining κ_{XOR}(c, n) is more difficult. However, for fixed c it suffices to check the cases n = 1, 2, ⋯, O(c^{2}) to determine κ_{XOR}(c, n) for all n. Indeed, for a fixed r ∈ [0, c − 2] let K = K(r) be the smallest integer such that for all m sufficiently large there exists a (c; (c − 1)m + r, (c/2 − 1)m + K + 1) XOR coloring.

Lemma 2.3 An XOR coloring with I_{T} = 0 for some T has (k−1)/n ≥ 1/2. For any r there exists a unique m_{0} = m_{0}(r) ≤ 2K(r) − r such that there exist (c; (c − 1)m + r, (c/2 − 1)m + K + 1) for all m ≥ m_{0}.

Proof The first statement follows from summing over all U with |T ∩ U| ≡ 1 (mod 2). For the second part, m_{0} obviously exists, and the coloring at n = (c − 1)m_{0} + r must have at least one I_{T} equal zero, or else we could subtract 1 from all the I_{T} ’s to get a coloring as above with m = m_{0} − 1. So the first statement applies to yield m_{0} ≤ 2K(r) − r.

□

In particular, checking κ_{XOR}(c, n) for n = 1, 2, …, O(c^{2}), we can determine all K(r)’s, and therefore all κ_{XOR}(c, n) with n ≥ m_{0}(r)(c − 1) + r = O(c^{2}) by the above. Another consequence of the above is:

Proposition 2.4 K(2) = 2 for c ≥ 8, and for n > 2 and ≡ 2 (mod c−1) we have κ_{XOR}(c, n) = 2+⌈nθ_{c}⌉.

Proof K(1) = 1 implies that either K(2) is 1 or 2. The lemma implies that to rule out K(2) being 1 it suffices to check the case m_{0} = 0, i.e. n = 2, where there is nothing to check (since 2^{n} < c). Hence K(2) = 2, and then clearly m_{0}(2) = 1, i.e. for n = c+1 we can achieve κ_{XOR}(c, n) = 2 + ⌈nθ_{c}⌉.

□

Proposition 1.3 is a consequence of the above.

3 Almost Equicolored Colorings and Profiles

For a c-coloring, γ: B^{n} → B^{s}, we define its L^{p}(H_{k}) distance from equicolor via

∥γ∥_{L^{p}(H_{k})}^{p} = ∑_{v∈B_{s}} ∥γ^{−1}(v)∥_{L^{p}(H_{k})}^{p},

where for a C ⊂ B^{n} (and a fixed c = |C|/n in mind) we define the summand via

∥C∥_{L^{p}(H_{k})}^{p} = ∑_{H∈H_{k}}| |C ∩ H| − |H|/c |^{p}.

This is one sense in which we can measure how close to being equicolored a coloring is. In this section we study the case p = 2. There are other important metrics suggested by the applications, and we mention

∥γ∥_{RP(H_{k})} = max_{H∈H_{k},G⊂B^{s},|G|=2^{s−1}} |γ^{−1}(G) − 2^{k−1}| ;

this measures how well the bits γ extracts work as a random source to an RP algorithm, G being interpreted as the set of witnesses.

We study ∥C∥_{L^{2}(H_{k})} for a C ⊂ B^{n} via C’s distance distribution in the following sense:

Definition 3.1 The distance distribution of a C ⊂ B^{n} is the collection of numbers, N_{i}, defined to be the number of pairs (c_{1}, c_{2}) ∈ C × C of points in C of distance i (i.e. in the B^{n} or Hamming distance), for i = 0, …, n.

The N_{i} is essentially the weight enumerator of coding theory (see [CS88] or [vL82]).

Consider, for a C ⊂ B^{n} with |C| = n/c,

E_{j}(C) ≡ ∑_{H∈H_{j}} |C ∩ H|^{2}.

Since

∥C∥_{L^{2}(H_{j})}^{2} = ∑_{H∈H_{j}}(|C∩H|−|H|/c)^{2} = E_{j}(C)−\frac{2^{n+j}}{c^{2}} \binom{n}{j},

E_{j}(C) can be used to measure how close C is to being equicolored with respect to H_{j}. Routine calculations demonstrate that one can calculate E_{j} knowing the μ_{i}’s of section 2 (see [Fri91] for details):

Lemma 3.2

N_{i} = (q_{i}(A)χ_{C}, χ_{C}) = ∑_{r=0}^{n} q_{i}(n − 2r)|C|μ_{r}

where q_{i} is a polynomial of degree i given by q_{0} = 1, q_{1}(x) = x, and

q_{i+1}(x) = (\frac{x}{i + 1}) q_{i}(x)−(\frac{n − i + 1}{i + 1}) q_{i−1}(x) (3.1)

for i ≥ 1. Furthermore,

E_{j} = ∑_{l=0}^{j} \binom{n − l}{j − l}N_{l} = (s_{j}(A)χ_{C}, χ_{C}) =

∑_{r=0}^{n} s_{i}(n − 2r)|C|μ_{r},

where s_{j} is a polynomial of degree j with leading coefficient (n(n − 1) ⋯ (n − j + 1))^{−1}, given generally as

s_{j}(x) = ∑_{l=0}^{j} \binom{n − l}{j − l}q_{i}(A).  (3.2)

The key point in the proof of theorem 1.6 is to understand the polynomials s_{j}; they are determined by the following proposition. The author admits to having discovered this proposition by example with computer-aided calculations, which once known is easy to prove (yet the author knows no direct combinatorial proof using only equations 3.2 and 3.1).

Proposition 3.3 s_{j} has −n, −n + 2, …, −n + 2j − 2 as its j roots; i.e.

s_{j}(x) = \frac{(x + n)(x + n − 2) ⋯ (x + n − 2j + 2)}{n(n − 1) ⋯ (n − j + 1)} =

2^{j}\binom{(x + n)/2}{j}.

Proof It is clear from the definition of the s_{j}’s that they are polynomials of degree j satisfying

(s_{j}(A)f, f) = ∑_{H∈H_{j}} (∑_{x∈H} f(x))^{2} ,

for any f ∈ L^{2}(B^{n}). The right-hand-side of the above clearly vanishes if f is the XOR of r variables with r ≥ n−j+1. Since such an f has eigenvalue n−2r, we conclude that s_{j} has a root n−2r for any r ≥ n−j +1.

□

From this proposition we see that s_{j}(x) restricted to x = −n, −n + 2, …, n is a convex function, as is its restriction to [−n + 2j − 2, +∞), and we easily obtain the following stronger version of theorem 1.6:

Theorem 3.4 For c − 1|n and j ≤ 1 + θ_{c}n, the balanced XOR coloring is closest in L^{2}(H_{j}) to equicolor, and any coloring as close must have the same distance distribution as that of the balanced XOR coloring. In other words,

\frac{(s_{j}(A)χ_{C}, χ_{C})}{(χ_{C}, χ_{C})} ≥ \frac{1}{c}s_{j}(n) + \frac{c − 1}{c}s_{j}(−n/(c − 1)),

equality holding iff c−1|n and all μ_{i}’s vanish except for μ_{0} = 1/c and μ_{n(1−θ_{c})} = (c−1)/c. For c−1 |̸n, setting −n/(c − 1) = t + α with t an integer and α ∈ (0, 1), we have the sharper bound

\frac{(s_{j}(A)χ_{C}, χ_{C})}{(χ_{C}, χ_{C})} ≥ \frac{1}{c}s_{j}(n)+\frac{c − 1}{c}((1−α)s_{j}(t)+αs_{j}(t+1)),

with equality iff μ_{t} = (1 − α)(c − 1)/c, μ_{t+1} = α(c − 1)/c.

4 Locally Symmetric Colorings and Concluding Remarks

We consider the problem of classifying for c − 1|n all optimal colorings, i.e. with k = 1 + nθ_{c}. We call a coloring, γ: B^{n} → B^{s} locally symmetric if there is an η such that for all v ∈ B_{n}, exactly nη of v’s neighbors are colored γ(v), and every other color occurs among v’s neighbors exactly n(1−η)/(c−1) times. In addition we say that the coloring is sparse if η = 0; the balanced coloring is an example.

It is easy to see that locally symmetric colorings are also symmetric in their “distance i neighborhoods” for all i, and that each color has the same distance distribution which is uniquely determined by η. In particular, a locally symmetric coloring which is optimal for c − 1|n must be sparse.

These considerations, and theorems such as theorem 3.4 suggest dividing problem 1.5 into two parts:

Problem 4.1 Are all optimal colorings, i.e. with k = κ(c, n), necessarily locally symmetric, at least if c − 1|n?

Problem 4.2 Are all locally symmetric sparse colorings necessarily XOR colorings?

Regarding the latter question, and XOR colorings in general, one can make the following observation. Consider a general cycle of length 4 in B_{n}, (v_{0}, v_{1}, v_{2}, v_{3}, v_{0}). XOR colorings satisfy the following two conditions:

1. γ(v_{3}) depends only on γ(v_{0}), γ(v_{1}), γ(v_{2}), not on the particular cycle,

2. γ(v_{0}) = γ(v_{2}) implies γ(v_{1}) = γ(v_{3}).

Proposition 4.3 Any locally symmetric coloring satisfying the above two conditions is an XOR coloring.

Proof Fix any coloring, γ, of B^{n}, and a vertex, v ∈ B_{n}. We define a group law on the colors as follows. We can assume η < 1, or else there is nothing to prove. So for any γ_{1} ≠ γ_{2} neither equal γ(v), there exist neighbors v_{1}, v_{2} of v with γ(v_{i}) = γ_{i}. There exists a unique v_{3} making v, v_{1}, v_{3}, v_{2} a simple cycle of length 4; define γ_{1} + γ_{2} to be γ(v_{3}). If γ_{1} = γ_{2} define their sum to be γ(v), and if one of γ_{1}, γ_{2} is γ(v) define their sum to be the other γ_{i}. That this defines defines a commuatative, associative group law, with identity γ(v), and every other element of order 2, is an easy consequence of the above conditions; for example, commutativity follows from the fact that if v_{0}, v_{1}, v_{2}, v_{3} is a simple cycle then so is v_{0}, v_{3}, v_{2}, v_{1}; associativity follows from the fact that the sum of three colors is the antipodal point to v_{0} in a subcube of B^{n} isomorphic to B^{3}. This sets up an isomorphism between the colors and B^{s}. One can similarly show that for every cycle (v_{0}, v_{1}, v_{2}, v_{3}, v_{0}) we have the sum of the colors vanishing (i.e. = γ(v)). Setting coordinates on B^{n} so that v is the origin, the coloring of the neighbors of v determine XOR’s, f_{1}, …, f_{s} such that the f_{i}’s induce the given coloring on v and its neighbors. The conditions on the coloring imply, by induction on k, that for any w ∈ B^{n} of distance k to v, the coloring determined by the f_{1}, …, f_{s} agrees with the original coloring.

□

Of course, in the above proposition, one can replace the local symmetry condition by the condition that, say, each v ∈ B^{n} has all colors appearing among its neighbors except for, possibly, its own color. Call such a coloring connected. We can restate the problems as:

Problem 4.4 Is any optimal coloring necessarily connected and does it necessarily satisfy the above two conditions?

References

[BBR88] C.H. Bennett, G. Brassard, and J.-M. Robert. Privacy amplification by public discussion. SIAM J. on Computing, 17(2):210–229, 1988.

[Bra89] G. Brassard. Cryptology— Column 1. SIGACT News, 20(3):15–19, Summer 1989.

[CFG^{+}85] B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, and R. Smolensky. The bit extraction problem or t-Resilient functions. In 26th Annual Symposium on Foundations of Computer Science, pages 396–407, 1985.

[CS88] J.H. Conway and N.J.A. Sloan. Sphere Packings, Lattices, and Groups. Springer-Verlag, 1988.

[Fri91] J. Friedman. On the bit extraction problem. Technical report, Princeton University, December 1991.

[KKL88] J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In 29th Annual Symposium on Foundations of Computer Science, pages 68–80, 1988.

[Vaz85] U. Vazirani. Towards a strong communication complexity theory, or generating quasi-random sequences from two communcating slightly-random sources. In Proc. of 17th ACM Symposium on Theory of Computing, pages 366–378, 1985.

[vL82] J.H. van Lint. Intorduction to Coding Theory. Springer-Verlag, 1982.