<p>There is a HUGE number of applications of error correcting codes in theoretical computer science.</p>

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

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

CC BY-SA 2.5
2010-10-09T23:35:12.563Z
I think the OP mentioned Trevisan's extractor construction in the question.
Suresh Venkat
CC BY-SA 2.5
2010-10-09T22:02:30.527Z
2010-10-09T22:02:30.527Z
Dana Moshkovitz
<p>Here's a straightforward application in communication complexity (which I see now is also described in a comment by Andy Drucker on his <a href="http://andysresearch.blogspot.com/2007/09/information-is-not-substance.html">blog</a>) outside the context of derandomization:</p>

<p>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&lt;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.</p>

CC BY-SA 2.5
2010-10-10T21:19:36.350Z
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).
Noam
CC BY-SA 2.5
2010-08-17T16:47:48.770Z
Very neat application!
ilyaraz
CC BY-SA 2.5
2010-08-17T18:40:19.770Z
But... Can not we just pad $x$ by sufficient amount of zeroes, and $y$ -- by ones?
ilyaraz
CC BY-SA 2.5
2010-08-17T21:25:22.130Z
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.
Andy Drucker
CC BY-SA 2.5
2010-08-17T21:35:34.190Z
But we want to distinguish two situations: small Hamming weight vs large Hamming weight. Why do we want to care about preserving equality?
ilyaraz
CC BY-SA 2.5
2010-08-17T21:59:27.397Z
Using error-correcting codes we can prove that it is hard to distinguish two following situations: strings are equal and Hamming distance is more than (1/2 - $epsilon$) n.
ilyaraz
CC BY-SA 2.5
2010-08-17T23:07:31.207Z
Hi Ilya--you can use the reduction you describe to argue that it's hard to *exactly* determine the Hamming distance, under the promise that it's within a certain range (the range is determined by the amount of padding).  However, this reduction doesn't say anything about the hardness of determining the *approximate* Hamming distance.  Using error-correcting codes, by contrast, tells you it's hard to estimate Hamming distance within a constant factor.
Andy Drucker
CC BY-SA 2.5
2010-08-17T23:07:51.923Z
(Note--as Arnab says, this is all about *deterministic* protocols.  The randomized case is much more interesting and subtle. See "Better Gap-Hamming Lower Bounds via Better Round Elimination" by Brody et al.)
Andy Drucker
CC BY-SA 2.5
2010-08-17T14:01:28.570Z
2010-08-17T14:01:28.570Z
arnab
<p>Here's a new application, hot off the presses ! <a href="http://eccc.hpi-web.de/report/2010/137/">A new ECCC report by Or Meir</a> has this as its abstract:</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

CC BY-SA 2.5
2010-08-30T16:27:04.807Z
I saw your comment, when I was intended to post the same one. Nice!
ilyaraz
CC BY-SA 2.5
2010-08-29T21:34:58.663Z
2010-08-29T21:34:58.663Z
Suresh Venkat
<p>There is a series of papers on steganography and covert computation (beginning <a href="http://www.cs.cmu.edu/~biglou/PSS.pdf" rel="nofollow">here</a>) that fundamentally require error-correcting codes. They model failed oracle calls to draw from an arbitrary distribution as noise in a channel.</p>

CC BY-SA 2.5
2010-08-17T14:09:07.473Z
2010-08-17T14:09:07.473Z
Daniel Apon
<p>Indeed, as Dana mentioned, there are many examples. </p>

<p>In fault-tolerance computation error-correcting codes are very important. I think the 1988 paper by Ben-Or Goldwasser and Wigderson  <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GBW88/GBW88.pdf" rel="nofollow">Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation</a>, 
while not explicitely citing error correcting codes results have ECC flavour.</p>

<p>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.<br>
(The <a href="http://en.wikipedia.org/wiki/Quantum_threshold_theorem" rel="nofollow">Wikipedia article</a> for the threshold theorem certainly needs work; But the <a href="http://en.wikipedia.org/wiki/Quantum_error_correction" rel="nofollow">article on quantum error-correction</a> is better.) </p>

CC BY-SA 2.5
2010-10-10T17:38:46.513Z
2010-10-11T15:00:08.883Z
2010-10-11T15:00:08.883Z
Gil Kalai
<p>Andy Drucker has already mentioned the survey by Trevisan [Tre04] in a comment to <a href="https://cstheory.stackexchange.com/questions/121/using-error-correcting-codes-in-theory/143#143">another answer</a>, but I think that it should be mentioned in a larger font!</p>

<p>[Tre04] Luca Trevisan.  Some applications of coding theory in computational complexity.  <em>Quaderni di Matematica</em>, 13:347–424, 2004.  <a href="http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf" rel="nofollow noreferrer">http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf</a></p>

CC BY-SA 2.5
2010-10-10T20:05:52.870Z
2010-10-10T20:05:52.870Z
2017-04-13T12:32:28.053Z
Tsuyoshi Ito
<p>Error correcting codes are used in cryptography to solve the problem of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7431&amp;rep=rep1&amp;type=pdf" rel="noreferrer">information reconciliation</a>: 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.</p>

<p>Recently, <a href="http://www.cs.bu.edu/~reyzin/fuzzysurvey.html" rel="noreferrer">fuzzy extractors</a> 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.</p>

CC BY-SA 2.5
2010-10-10T00:01:52.233Z
2010-10-10T00:01:52.233Z
Felipe Lacerda
<p>A few other examples:</p>

<ul>
<li><p>Construction of $\epsilon$-biased k-wise independent sample spaces (e.g., <em>Naor-Naor, STOC'90</em>). Actually, they use ECCs twice: first to construct $\epsilon$-biased sample spaces, and then to convert them to k-wise independent ones. </p></li>
<li><p>Improved fast randomized dimensionality reduction (Fast Johnson-Lindenstrauss Transform), in <em>Ailon-Liberty, SODA'08</em>.</p></li>
</ul>

CC BY-SA 2.5
2010-08-25T20:17:40.683Z
Very nice answer!
ilyaraz
CC BY-SA 2.5
2010-08-25T20:04:20.737Z
2010-08-25T20:04:20.737Z
Piotr
<p>Check out <a href="http://eccc.hpi-web.de/keyword/13579/" rel="nofollow">the list of ECCC papers tagged with "error-correcting codes"</a>.</p>

<p>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 <a href="http://eccc.hpi-web.de/report/1997/028" rel="nofollow">PAC learning</a>.</p>

CC BY-SA 2.5
2010-08-17T21:30:01.197Z
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.
Andy Drucker
CC BY-SA 2.5
2010-08-17T13:49:26.007Z
2010-08-17T13:49:26.007Z
Joshua Grochow
<p>For a very nice account of how error-correcting codes are used in a particular practical situation look at:</p>

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

<p>(This book is a translation from the German original.)</p>

CC BY-SA 2.5
2010-10-11T14:58:09.553Z
2010-10-11T14:58:09.553Z
Joseph Malkevitch
<p>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.</p>

CC BY-SA 2.5
2010-08-17T16:56:12.583Z
2010-08-17T16:56:12.583Z
Joe Fitzsimons
<p>Error-correcting code have had applications in property testing:</p>

<ul>
<li><p>Functional property testing:</p>

<ul>
<li>Showing tolerant testing can be quite hard: <em><a href="http://theoryofcomputing.org/articles/v002a009/" rel="nofollow noreferrer">Tolerant Versus Intolerant Testing for Boolean Properties</a></em>, by Fischer and Fortnow</li>
<li>Proving lower bounds via communication complexity:
<em><a href="https://link.springer.com/article/10.1007/s00037-012-0040-x" rel="nofollow noreferrer">Property Testing Lower Bounds via Communication Complexity</a></em>, by Blais, Brody, and Matulef (basically, ECCC's are a big step of the reduction, allowing to get the promise gap in property testing). See also <a href="http://www.wisdom.weizmann.ac.il/~oded/p_ccpt.html" rel="nofollow noreferrer">Oded Goldreich's take on this</a>.</li>
<li>Showing hierachy theorems in property testing:</li>
<li>with regard to <em>adaptivity</em>: <em><a href="http://drops.dagstuhl.de/opus/volltexte/2017/7516/" rel="nofollow noreferrer">An Adaptivity Hierarchy Theorem for Property Testing</a></em>, by Canonne and Gur. ECCC's (actually, LTC+LDC's) are used to "lift" query model hierarchy to property testing.</li>
</ul></li>
<li><p>Distribution testing:
The analogue of the [BBM] lower bound methodology mentioned above also uses error-correcting codes as a key component: <em><a href="http://drops.dagstuhl.de/opus/volltexte/2017/7536/" rel="nofollow noreferrer">Distribution Testing Lower Bounds via Reductions from Communication Complexity</a></em>, by Blais, Canonne, and Gur.</p></li>
</ul>

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

CC BY-SA 3.0
2017-09-08T13:07:29.393Z
2017-09-08T13:07:29.393Z
Clement C.
<p>We believe <a href="https://pqcrypto.org/code.html" rel="nofollow noreferrer">code-based public-key cryptography</a> 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, <a href="https://binary.cr.yp.to/mcbits.html" rel="nofollow noreferrer">like 1MB in McBits</a>.</p>

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

CC BY-SA 3.0
2017-09-08T01:16:53.833Z
2017-09-08T01:16:53.833Z
Jeff Burdges
<p>What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: <a href="http://en.wikipedia.org/wiki/Hard-core_predicate">Goldreich-Levin theorem</a> about hard core bit, <a href="http://www.cs.berkeley.edu/~luca/pubs/#extract">Trevisan's construction of extractor</a> and <a href="http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps">amplification of hardness of boolean function</a> (by Sudan-Trevisan-Vadhan).</p>

<p>What are other 'serious' or 'recreational' applications of error-correcting codes?</p>

<p>UPD: <a href="http://people.cs.uchicago.edu/~razborov/files/secrets.ps">one amusing application</a> of list decoding of Reed-Solomon codes is a solution to particular variation of 20 questions game (and <a href="http://www.math.dartmouth.edu/~pw/papers/3thresh.ps">another</a>, more straightforward, variation).</p>

CC BY-SA 3.0
2011-06-30T13:09:10.220Z
Maybe I'll be silly, but nobody speaked about the PCP Theorem
AntonioFa
<co.combinatorics><big-list><coding-theory>
Using error-correcting codes in theory
ilyaraz
# Using error-correcting codes in theory

(Asked by: username_0 on 2010-08-17)

What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: [Goldreich-Levin theorem](http://en.wikipedia.org/wiki/Hard-core_predicate) about hard core bit, [Trevisan's construction of extractor](http://www.cs.berkeley.edu/~luca/pubs/#extract) and [amplification of hardness of boolean function](http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps) (by Sudan-Trevisan-Vadhan).

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

UPD: [one amusing application](http://people.cs.uchicago.edu/~razborov/files/secrets.ps) of list decoding of Reed-Solomon codes is a solution to particular variation of 20 questions game (and [another](http://www.math.dartmouth.edu/~pw/papers/3thresh.ps), more straightforward, variation).

**Tags:** co.combinatorics, big-list, coding-theory

> **Comments:**
> **username_1**: Maybe I'll be silly, but nobody speaked about the PCP Theorem  

---

## 13 answers

### Answer by username_4 on 2010-08-17. Score: 24

Here's a straightforward application in communication complexity (which I see now is also described in a comment by username_6 on his [blog](http://andysresearch.blogspot.com/2007/09/information-is-not-substance.html)) 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.

> **Comments:**
> **username_0**: Very neat application!  
> **username_0**: But... Can not we just pad $x$ by sufficient amount of zeroes, and $y$ -- by ones?  
> **username_6**: username_0--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.  
> **username_0**: But we want to distinguish two situations: small Hamming weight vs large Hamming weight. Why do we want to care about preserving equality?  
> **username_0**: Using error-correcting codes we can prove that it is hard to distinguish two following situations: strings are equal and Hamming distance is more than (1/2 - $epsilon$) n.  
> **username_6**: Hi Ilya--you can use the reduction you describe to argue that it's hard to *exactly* determine the Hamming distance, under the promise that it's within a certain range (the range is determined by the amount of padding).  However, this reduction doesn't say anything about the hardness of determining the *approximate* Hamming distance.  Using error-correcting codes, by contrast, tells you it's hard to estimate Hamming distance within a constant factor.  
> **username_6**: (Note--as Arnab says, this is all about *deterministic* protocols.  The randomized case is much more interesting and subtle. See "Better Gap-Hamming Lower Bounds via Better Round Elimination" by Brody et al.)  
> **username_5**: 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).  

---

### Answer by username_2 on 2010-10-09. Score: 17

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

> **Comments:**
> **username_3**: I think the OP mentioned Trevisan's extractor construction in the question.  

---

### Answer by username_3 on 2010-08-29. Score: 14

Here's a new application, hot off the presses ! [A new ECCC report by Or Meir](http://eccc.hpi-web.de/report/2010/137/) 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.

> **Comments:**
> **username_0**: I saw your comment, when I was intended to post the same one. Nice!  

---

### Answer by username_7 on 2010-08-17. Score: 8

There is a series of papers on steganography and covert computation (beginning [here](http://www.cs.cmu.edu/~biglou/PSS.pdf)) that fundamentally require error-correcting codes. They model failed oracle calls to draw from an arbitrary distribution as noise in a channel.


---

### Answer by username_10 on 2010-10-10. Score: 7

Error correcting codes are used in cryptography to solve the problem of [information reconciliation](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.7431&rep=rep1&type=pdf): 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](http://www.cs.bu.edu/~reyzin/fuzzysurvey.html) 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.


---

### Answer by username_11 on 2010-08-25. Score: 7

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

> **Comments:**
> **username_0**: Very nice answer!  

---

### Answer by username_8 on 2010-10-10. Score: 6

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](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GBW88/GBW88.pdf),
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](http://en.wikipedia.org/wiki/Quantum_threshold_theorem) for the threshold theorem certainly needs work; But the [article on quantum error-correction](http://en.wikipedia.org/wiki/Quantum_error_correction) is better.)


---

### Answer by username_9 on 2010-10-10. Score: 6

username_6 has already mentioned the survey by Trevisan [Tre04] in a comment to [another answer](https://cstheory.stackexchange.com/questions/121/using-error-correcting-codes-in-theory/143#143), 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>


---

### Answer by username_12 on 2010-08-17. Score: 5

Check out [the list of ECCC papers tagged with "error-correcting codes"](http://eccc.hpi-web.de/keyword/13579/).

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](http://eccc.hpi-web.de/report/1997/028).

> **Comments:**
> **username_6**: 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.  

---

### Answer by username_13 on 2010-10-11. Score: 4

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


---

### Answer by username_14 on 2010-08-17. Score: 3

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.


---

### Answer by username_15 on 2017-09-08. Score: 2

Error-correcting code have had applications in property testing:

* Functional property testing:

  + Showing tolerant testing can be quite hard: *[Tolerant Versus Intolerant Testing for Boolean Properties](http://theoryofcomputing.org/articles/v002a009/)*, by Fischer and Fortnow
  + Proving lower bounds via communication complexity:
    *[Property Testing Lower Bounds via Communication Complexity](https://link.springer.com/article/10.1007/s00037-012-0040-x)*, by Blais, Brody, and Matulef (basically, ECCC's are a big step of the reduction, allowing to get the promise gap in property testing). See also [Oded Goldreich's take on this](http://www.wisdom.weizmann.ac.il/~oded/p_ccpt.html).
  + Showing hierachy theorems in property testing:
  + with regard to *adaptivity*: *[An Adaptivity Hierarchy Theorem for Property Testing](http://drops.dagstuhl.de/opus/volltexte/2017/7516/)*, by Canonne and Gur. ECCC's (actually, LTC+LDC's) are used to "lift" query model hierarchy to property testing.
* Distribution testing:
  The analogue of the [BBM] lower bound methodology mentioned above also uses error-correcting codes as a key component: *[Distribution Testing Lower Bounds via Reductions from Communication Complexity](http://drops.dagstuhl.de/opus/volltexte/2017/7536/)*, by Blais, Canonne, and Gur.

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


---

### Answer by username_16 on 2017-09-08. Score: 1

We believe [code-based public-key cryptography](https://pqcrypto.org/code.html) 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](https://binary.cr.yp.to/mcbits.html).

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


---

