An Error Correcting Code From The Book
But can we find the pages it is on?
Atri Rudra is a coding theorist who helped organize the recent workshop in Ann Arbor on Coding, Complexity, and Sparsity. He has strong coding theory ancestors:
- Venkatesan Guruswami
- Madhu Sudan
- Leonhard Euler
- Jacob Bernoulli
Jacob was a member of the great Bernoulli family. They together did remarkable work in many aspects of mathematics, but Jacob is the one who invented the Bernoulli distribution that is used throughout coding theory. Recall this is the distribution that takes on with probability and with probability , in each of multiple independent trials. It is such a simple idea, but someone had to invent it, and Jacob did.
Atri himself, with his advisor Venkat Guruswami, began making some breakthrough contributions to coding theory several years ago, including this STOC 2006 paper, which was also referenced in a popular article by Bernard Chazelle for the magazine Science. Yet the following simple problem remains. Atri told me about it a few months ago, and it seems too basic to be open. But it is. The problem concerns possibly the simplest good linear code.
Jørn Justesen in his seminal 1972 paper “A class of constructive asymptotically good algebraic codes” gave the first example of a strongly explicit binary codes with constant rate and linear distance. This had been a Holy Grail for years in coding theory, open since its beginning. Before 1972 it was known via randomized constructions that such codes existed, but there were no explicit constructions. His codes, now known as Justesen Codes, were constructive, and so solved the open problem, but they were not very simple.
A linear code is a -dimensional vector subspace given by a generator matrix. Its rate is , and its minimum distance equals the minimum number of non-zero entries in a non-zero codeword, which is called the codeword’s weight. A good code has and both . This means the code can detect many errors without excessively extending the length- plaintext words that are given to it.
There is a simple linear code that is attributed to John Wozencraft by Justesen, and this code is known to be good. The problem is that the code, which we will denote by , depends on a parameter . If this parameter is selected randomly, then the code is terrific: its rate in fact lies on the famous Gilbert-Varshamov Bound. This bound is due to Edgar Gilbert and Rom Varshamov who independently discovered it—again that phenomenon of dual discovery.
The main open question with this code is how to de-randomize it: Is there a way to explicitly construct for each length an that works? This has been open going on close to fifty years.
The code operates over the finite field . The code consists of the words of the form:
where is viewed as being in the finite field and the product is the finite field multiplication. Clearly this is a simple code: to encode one only needs to do one field operation. Pretty impressive.
I will not give the full proof of why this code has such a good distance for selected randomly, but will give the intuition behind it. The question reduces to what is the least weight of a non-zero code word.
Let be a non-zero code word with the lowest possible weight. Clearly, must be non-zero and of low weight. If its weight is large, then it does not matter what the rest of the code word is. Therefore we can assume that has low weight. But was selected randomly, and since is non-zero, the word is a random code word. Thus we need only note that such a word is exponentially unlikely to be of low weight. A union-bound argument then applies because there are many fewer low-weight words than possible .
The full proof is mainly a careful analysis of the probability of a word having a low weight. It and more including links to Atri’s own notes can be found here*—the “*” is a footnote. A pretty neat result, a pretty cool code, and a very hard open problem. How can we select deterministically? The proof shows that almost all work, but finding one explicitly seems to be beyond our current abilities.
Complexity Theory Connections
The simplicity of this code suggest some connection to de-randomization problems of complexity theory. The rough idea is this:
- Show that is computed by some low level complexity class.
- Then show that there is a method to de-randomize this class.
The reason I think that this is a possible approach is the very nature of the code. The code only does one finite field operation, which suggests to me that there could be some hope in solving this problem.
A more general question notes that the only property used in building this code is that is an invertible operation. This means that for any non-zero, the values of are uniformly distributed, if is. Perhaps there is another operation that has this property that will still make the code work, but is easier to de-randomize?
Can you see how to de-randomize this code? Can you relate this problem to other open de-randomization problems from complexity theory?
The footnote*: Ken fixed typos “Wonzen—” to “Wozen—” in the Wikipedia article on , but the typo persists in the article’s title and hence its URL. This is what the typo-fixed link will be. Is there a good way to automate correcting this kind of link error on the Net? Can error-correcting codes applied to URLs be relevant here?