# Balanced binary code that "resists" local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the sense that, for some $k$, reading $k$ bits is never sufficient to decode (even were the channel noiseless).

In other words, for each subset of $k$ locations and each codeword $w$, there exists a codeword $w'$ that matches $w$ at those $k$ locations.

To make the question harder, I'm actually most interested in "balanced" binary codes -- every word has Hamming weight $\frac{n}{2}$. But it seems independently interesting to get an answer even without the balanced condition.

How large can $k$ be? Can it be $\Omega(n)$? (What is $k$ for the Hadamard code?)

Notes: We can restate this as a combinatorics problem (up to a constant factor or two), treating each codeword as a subset of $\{1,\dots,n\}$ indicating the coordinates equal to $1$: Come up with a set of subsets of $\{1,\dots,n\}$, each of size $n/2$, such that pairwise intersection is $O(n)$ (this is the distance requirement) and for each subset $S$ and each $X \subseteq S$ with $|X| \leq k$, there exists an $S'$ such that $X \subseteq S'$.

The problem of finding the largest $k$ seems too large for exhaustive search even over very small $n$.

Examples: For $n=4$, take all of the weight-$2$ words: $\{1100,1010,1001,0110,0101,0011\}$. Here $d=2$ and $k=1$ (we must read at least two locations to have a hope of uniquely identifying a codeword).

For $n=8$, I believe we can take the following weight-$4$ words: $\{11110000, 00001111, 11000011, 10100101, 10010110, 01101001, 01011010, 00111100\}$. Here $d=4$ and $k=2$.

• This seems to be related to secret sharing: distributing a secret to $n$ people so that at least $t$ shares are required to reconstruct it, or so that knowing any $t-1$ shares does not reveal any information. My knowledge on the topic ends about here; I don't know if binary codes have been used as in this problem. Dec 18 '14 at 8:10
• there is a discrepancy in the definition of $k$ vs examples; e.g. your 1st example corresponds to $k=1$, according to your definition. Dec 18 '14 at 8:33
• @JiK, thanks, I'll follow up on secret-sharing.
– usul
Dec 18 '14 at 8:54
• @DimaPasechnik, right, there is an off-by-one error that I'll fix.
– usul
Dec 18 '14 at 8:54
• After looking into secret-sharing a bit, I don't see a useful connection. There are too many components that differ strongly (use of randomness, the fact that $t-1$ shares reveals zero information, lack of notion of distance between words). But maybe one can put to use Shamir's basic idea (each share is a point on a polynomial of degree $t$).
– usul
Dec 19 '14 at 11:48

For each $k$ take $n=2^k$ and the hyperplanes of the $k$-dimensional affine space over $\mathbb{F}_2$. There are $n$ points and $2^{k+1}-2$ hyperplanes; the codewords are the indicator functions of the latter. Then $k-1$ bits never suffice, but $k$ bits always do give you unique codeword.
• So $k = \log(n)$, and what is the distance of the code? Thanks.
• the supports of the codewords either have empty intersection, or intersection of size $2^{k-2}$. So the Hamming distance between any two is $2^{k-1}$ or $2^k$. Thus the minimal distance is $2^{k-1}$. Dec 19 '14 at 14:09