13
$\begingroup$

The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one coordinate position in the encoding for each of the $2^k$ different binary functions on the input values. Instead, I want to consider a shorter but still doubly exponential code, with one coordinate position for each of the $\tbinom{k}{k/2}/2$ partitions of the $k$ values into two equal-sized subsets (assuming $k$ is even). Each partition can be thought of as corresponding to two different binary functions (the functions whose inverse images form the given partition) and we choose arbitrarily which one of these two functions to use.

The minimum distance of the code (and in fact the distance between all pairs of codewords) is $\tbinom{k-2}{(k-2)/2}$, smaller than the length of the code by only a factor of $\tfrac{k}{2k-1}>\tfrac{1}{2}$. For instance for $k=8$ we get a code of length 35 with minimum distance 20, which http://www.codetables.de/ tells me matches the Griesmer bound for binary linear codes of the same size (rank 3 or size 8).

I am interested in this for reasons only vaguely related to coding theory, but it seems likely to me that the coding theorists have already studied this code. Unfortunately, I don't know of a good way of looking up coding schemas by the formulas for their parameters. If it has been previously studied, what is it called? And what are some references to it?

(BTW, the property I actually care about, which is easy enough to prove using Sperner's theorem, is that this is the longest possible binary code in which each two positions are independent of each other, in the sense that all four possible combinations of symbols in the two positions are realized by codewords. There appears to be something in the literature called a Sperner code but it's transposed from this — each codeword has equally many zeros and ones, rather than the property of the code I'm looking at, where each bit position has equally many codewords for which that position is a 0 or 1.)

$\endgroup$
  • 1
    $\begingroup$ Ok, if it wasn't in the literature before, it is now. See section 6 of arxiv.org/abs/1303.1136 — this code gives the smallest set of vertices to delete from a hypercube graph in order to make all remaining hypercube subgraphs have at most 1/8 of the number of vertices of the original graph. $\endgroup$ – David Eppstein Nov 7 '13 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.