39
$\begingroup$

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of extractor and amplification of hardness of boolean function (by Sudan-Trevisan-Vadhan).

What are other 'serious' or 'recreational' applications of error-correcting codes?

UPD: one amusing application of list decoding of Reed-Solomon codes is a solution to particular variation of 20 questions game (and another, more straightforward, variation).

$\endgroup$
  • 1
    $\begingroup$ Maybe I'll be silly, but nobody speaked about the PCP Theorem $\endgroup$ – AntonioFa Jun 30 '11 at 13:09

13 Answers 13

23
$\begingroup$

Here's a straightforward application in communication complexity (which I see now is also described in a comment by Andy Drucker on his blog) outside the context of derandomization:

Suppose Alice and Bob are given strings $x$ and $y$ respectively, and they want to find out if the Hamming distance between $x$ and $y$ is at most $\epsilon n$ (where $\epsilon$ is some fixed constant). We want to prove a communication complexity lower bound for this problem. The observation is that any deterministic protocol for this problem yields a deterministic protocol with the same number of rounds for checking equality of two strings $a$ and $b$ of length $cn$ where $c<1$ is some constant depending on $\epsilon$. Why? To check equality of $a$ and $b$, Alice and Bob can run the protocol for the first problem on $C(a)$ and $C(b)$ where $C$ is an error correcting code with distance at least $\epsilon$. Since there is an easy linear lower bound for the equality problem, this also yields a deterministic linear lower bound for the first problem.

$\endgroup$
  • $\begingroup$ Very neat application! $\endgroup$ – ilyaraz Aug 17 '10 at 16:47
  • 1
    $\begingroup$ But... Can not we just pad $x$ by sufficient amount of zeroes, and $y$ -- by ones? $\endgroup$ – ilyaraz Aug 17 '10 at 18:40
  • $\begingroup$ ilyaraz--if we did that, then even if x, y were equal to start, they'd have large Hamming distance after padding. The point of using the map C() is to preserve equality while also 'amplifying' inequality. $\endgroup$ – Andy Drucker Aug 17 '10 at 21:25
  • $\begingroup$ But we want to distinguish two situations: small Hamming weight vs large Hamming weight. Why do we want to care about preserving equality? $\endgroup$ – ilyaraz Aug 17 '10 at 21:35
  • 3
    $\begingroup$ The most interesting use of this idea is actually to prove an upper bound on the randomized communication complexity of equality: just compare a random bit from C(a) and C(b). If a=b then you'll certainly get equality, otherwise you have probability epsilon to get inequality. This requires O(logn) bits (to choose the index of the compared bit), and if the parties hare common randomness then the complexity is just O(1). $\endgroup$ – Noam Oct 10 '10 at 21:19
17
$\begingroup$

There is a HUGE number of applications of error correcting codes in theoretical computer science.

A classic application [that I think wasn't mentioned above] is to the construction of randomness extractors / samplers; see, e.g., here: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

There are also many applications to cryptography, and I'm sure one of the informed readers would be happy to elaborate :)

$\endgroup$
  • $\begingroup$ I think the OP mentioned Trevisan's extractor construction in the question. $\endgroup$ – Suresh Venkat Oct 9 '10 at 23:35
14
$\begingroup$

Here's a new application, hot off the presses ! A new ECCC report by Or Meir has this as its abstract:

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The intuition that underlies the use of polynomials is commonly explained by the fact that polynomials constitute good error correcting codes. However, the known proofs seem tailored to the use of polynomials, and do not generalize to arbitrary error correcting codes.

In this work, we show that the IP theorem can be proved by using general error correcting codes. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.

$\endgroup$
  • $\begingroup$ I saw your comment, when I was intended to post the same one. Nice! $\endgroup$ – ilyaraz Aug 30 '10 at 16:27
8
$\begingroup$

There is a series of papers on steganography and covert computation (beginning here) that fundamentally require error-correcting codes. They model failed oracle calls to draw from an arbitrary distribution as noise in a channel.

$\endgroup$
7
$\begingroup$

A few other examples:

  • Construction of $\epsilon$-biased k-wise independent sample spaces (e.g., Naor-Naor, STOC'90). Actually, they use ECCs twice: first to construct $\epsilon$-biased sample spaces, and then to convert them to k-wise independent ones.

  • Improved fast randomized dimensionality reduction (Fast Johnson-Lindenstrauss Transform), in Ailon-Liberty, SODA'08.

$\endgroup$
  • $\begingroup$ Very nice answer! $\endgroup$ – ilyaraz Aug 25 '10 at 20:17
7
$\begingroup$

Error correcting codes are used in cryptography to solve the problem of information reconciliation: Alice and Bob want to agree on a key K starting from (correlated) strings X and Y, respectively. (An example of this situation is a protocol that relies on a noisy channel, with Alice sending X to Bob.) A solution is to make Alice send some error correcting information C to Bob so that he can reconstruct X. Of course, the problem is not so simple: since C leaks some information to the adversary Eve, we need to do privacy amplification in order to derive the secret key. This can be done with a 2-universal hash function, as guaranteed by the leftover hash lemma.

Recently, fuzzy extractors were introduced as a noise-tolerant variant of extractors: they extract a uniformly random string R from its input W and also produce a "fingerprint" P such that if the input changes to some similar string W', the random string R can be recovered from P and W'. The construction of fuzzy extractors also relies on error correcting codes.

$\endgroup$
6
$\begingroup$

Andy Drucker has already mentioned the survey by Trevisan [Tre04] in a comment to another answer, but I think that it should be mentioned in a larger font!

[Tre04] Luca Trevisan. Some applications of coding theory in computational complexity. Quaderni di Matematica, 13:347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

$\endgroup$
6
$\begingroup$

Indeed, as Dana mentioned, there are many examples.

In fault-tolerance computation error-correcting codes are very important. I think the 1988 paper by Ben-Or Goldwasser and Wigderson Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation, while not explicitely citing error correcting codes results have ECC flavour.

Of course, the "threshold theorem" allowing fault tolerant quantum computation relies in a crucial way on quantum error correcting codes which are quantum analogs of ordinary ECC.
(The Wikipedia article for the threshold theorem certainly needs work; But the article on quantum error-correction is better.)

$\endgroup$
5
$\begingroup$

Check out the list of ECCC papers tagged with "error-correcting codes".

Perusing that list, you'll see that there's a connection between error-correcting codes and PCPs (I don't know whether you'll consider this an application "beyond just error-correcting itself."), and also PAC learning.

$\endgroup$
  • 2
    $\begingroup$ Specifically, the codes known as 'locally testable codes' (LTCs) have close similarities with PCPs, and ideas used in building LTCs have also been useful in building PCPs. Also, I'm not sure if Trevisan's survey "Some Applications of Coding Theory in Computational Complexity" has been mentioned, but that's a good reference for your question. $\endgroup$ – Andy Drucker Aug 17 '10 at 21:30
4
$\begingroup$

For a very nice account of how error-correcting codes are used in a particular practical situation look at:

The Mathematics of the Compact Disc, by Jack H. Van Lint, in Mathematics Everywhere, M. Aigner and E. Behrends (editors), American Mathematical Society, 2010

(This book is a translation from the German original.)

$\endgroup$
3
$\begingroup$

Another application is in authentication codes. These are essentially encodings designed to detect any tampering with the message, and fundamentally rely on error correction. This is somewhat more than simple error correction, which tends to entail making assumptions about the structure of noise.

$\endgroup$
2
$\begingroup$

Error-correcting code have had applications in property testing:

(Sorry, this is a bit biased towards papers I have co-authored, mostly due to my familiarity with those.)

$\endgroup$
1
$\begingroup$

We believe code-based public-key cryptography to be post-quantum. In fact, code-base cryptography has the longest history record among post-quantum public-key schemes, but the key sizes seem impractically large, like 1MB in McBits.

We use error correcting codes in lattice-based public-key cryptography too, which employ a reconciliation phase like Felipe Lacerda mentioned. In fact, our current best bet for a post-quantum key exchange is the Module-LWE scheme Kyber (lattice-based).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.