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$.



Balanced binary code that "resists" local decoding?
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.


