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

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

13 Answers 13

Reset to default
24
$\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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Very neat application! $\endgroup$
    – ilyaraz
    Aug 17, 2010 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, 2010 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, 2010 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, 2010 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, 2010 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 :)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think the OP mentioned Trevisan's extractor construction in the question. $\endgroup$
    – Suresh Venkat
    Oct 9, 2010 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I saw your comment, when I was intended to post the same one. Nice! $\endgroup$
    – ilyaraz
    Aug 30, 2010 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very nice answer! $\endgroup$
    – ilyaraz
    Aug 25, 2010 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.

Improve this answer
$\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

Improve this answer
$\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.)

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • 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, 2010 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.)

Improve this answer
$\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.

Improve this answer
$\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.)

Improve this answer
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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