Locally testable code - Revision history

The Anome: Adding short description: "Type of error-correcting code"

2024-01-09T23:25:08Z

Adding short description: "Type of error-correcting code"

← Previous revision		Revision as of 23:25, 9 January 2024
Line 1:		Line 1:
			{{Short description\|Type of error-correcting code}}
	A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word (communication)\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.		A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word (communication)\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.

David Eppstein: Tali Kaufman

2023-11-17T22:29:14Z

Tali Kaufman

← Previous revision		Revision as of 22:29, 17 November 2023
Line 1:		Line 1:
	A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word (communication)\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.		A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word (communication)\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.

	In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine\|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web\|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/\|title=Locally Testable vs. Locally Decodable Codes\|first1=Tali\|last1=Kaufman\|first2=Michael\|last2=Viderman}}</ref>		In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine\|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web\|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/\|title=Locally Testable vs. Locally Decodable Codes\|first1=Tali\|last1=Kaufman\|author1-link=Tali Kaufman\|first2=Michael\|last2=Viderman}}</ref>

	Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy.		Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy.

Onel5969: Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist.

2023-10-24T01:40:48Z

Disambiguating links to Code word (link changed to Code word (communication)) using DisamAssist.

← Previous revision		Revision as of 01:40, 24 October 2023
Line 1:		Line 1:
	A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.		A '''locally testable code''' is a type of [[error-correcting code]] for which it can be determined if a [[String (computer science)\|string]] is a [[Code word (communication)\|word]] in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly.

	In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine\|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web\|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/\|title=Locally Testable vs. Locally Decodable Codes\|first1=Tali\|last1=Kaufman\|first2=Michael\|last2=Viderman}}</ref>		In contrast, [[locally decodable code]]s use a small number of bits of the codeword to [[Probabilistic Turing Machine\|probabilistically]] recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable.<ref name=decNotTest>{{cite web\|url=http://eccc.hpi-web.de/report/2010/130/revision/1/download/\|title=Locally Testable vs. Locally Decodable Codes\|first1=Tali\|last1=Kaufman\|first2=Michael\|last2=Viderman}}</ref>

Citation bot: Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2023-09-27T09:22:04Z

Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 09:22, 27 September 2023
Line 30:		Line 30:
	The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>		The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

	In November 2021 two preprints have reported<ref>{{cite arXiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arXiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/~~\|url-status=live~~\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2022-01-06\|title=Qubits Can Be as Safe as Bits, Researchers Show\|url=https://www.quantamagazine.org/qubits-can-be-as-safe-as-bits-researchers-show-20220106/\|access-date=2022-02-02\|website=Quanta Magazine\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.		In November 2021 two preprints have reported<ref>{{cite arXiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arXiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2022-01-06\|title=Qubits Can Be as Safe as Bits, Researchers Show\|url=https://www.quantamagazine.org/qubits-can-be-as-safe-as-bits-researchers-show-20220106/\|access-date=2022-02-02\|website=Quanta Magazine\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

	== Connection with probabilistically checkable proofs ==		== Connection with probabilistically checkable proofs ==
Line 71:		Line 71:
	== External links ==		== External links ==

	*{{Cite web\|date=6 October 2021\|title=Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality {{!}} Simons Institute for the Theory of Computing\|url=https://simons.berkeley.edu/events/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality~~\|url-status=live~~\|access-date=\|website=simons.berkeley.edu}}		*{{Cite web\|date=6 October 2021\|title=Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality {{!}} Simons Institute for the Theory of Computing\|url=https://simons.berkeley.edu/events/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality\|access-date=\|website=simons.berkeley.edu}}

	[[Category:Error detection and correction]]		[[Category:Error detection and correction]]

Dabed: /* Limits */ Added a second Quanta Magazine article on the topic this time with focus on the preprint of Pavel Panteleev and Gleb Kalachev.

2022-02-02T22:42:26Z

Limits: Added a second Quanta Magazine article on the topic this time with focus on the preprint of Pavel Panteleev and Gleb Kalachev.

← Previous revision		Revision as of 22:42, 2 February 2022
Line 30:		Line 30:
	The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>		The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

	In November 2021 two preprints have reported<ref>{{cite arXiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arXiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.		In November 2021 two preprints have reported<ref>{{cite arXiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arXiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2022-01-06\|title=Qubits Can Be as Safe as Bits, Researchers Show\|url=https://www.quantamagazine.org/qubits-can-be-as-safe-as-bits-researchers-show-20220106/\|access-date=2022-02-02\|website=Quanta Magazine\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

	== Connection with probabilistically checkable proofs ==		== Connection with probabilistically checkable proofs ==

Citation bot: Alter: template type. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 38/1682

2022-01-30T01:31:40Z

Alter: template type. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 38/1682

← Previous revision		Revision as of 01:31, 30 January 2022
Line 30:		Line 30:
	The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>		The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

	In November 2021 two preprints have reported<ref>{{cite ~~arxiv~~\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite ~~arxiv~~\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.		In November 2021 two preprints have reported<ref>{{cite arXiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arXiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

	== Connection with probabilistically checkable proofs ==		== Connection with probabilistically checkable proofs ==

2A01:E34:ECB2:7C0:9623:F5A8:ACBC:30F3: /* Definition */

2021-12-10T08:16:29Z

Definition

← Previous revision		Revision as of 08:16, 10 December 2021
Line 12:		Line 12:
	Relative distances are computed as a fraction of the number of bits		Relative distances are computed as a fraction of the number of bits
	:<math>\delta(x,y)=\Delta(x,y)/n \text{ and } \delta(w,C)=\Delta(w,C)/n</math>		:<math>\delta(x,y)=\Delta(x,y)/n \text{ and } \delta(w,C)=\Delta(w,C)/n</math>
	A code <math>C:\{0,1\}^k\to{0,1}^n</math> is called <math>q</math>-local <math>\delta</math>-testable if there exists a Turing machine M given [[random access]] to an input <math>w</math> that makes at most <math>q</math> non-adaptive queries of <math>w</math> and satisfies the following:<ref name=robustLTC>{{cite web\|url=http://people.csail.mit.edu/madhu/papers/2004/rltc-conf.pdf\|title=Robust Locally Testable Codes and Products of Codes\|first1=Eli\|last1=Ben-Sasson\|first2=Madhu\|last2=Sudan}}</ref>		A code <math>C:\{0,1\}^k\to\{0,1\}^n</math> is called <math>q</math>-local <math>\delta</math>-testable if there exists a Turing machine M given [[random access]] to an input <math>w</math> that makes at most <math>q</math> non-adaptive queries of <math>w</math> and satisfies the following:<ref name=robustLTC>{{cite web\|url=http://people.csail.mit.edu/madhu/papers/2004/rltc-conf.pdf\|title=Robust Locally Testable Codes and Products of Codes\|first1=Eli\|last1=Ben-Sasson\|first2=Madhu\|last2=Sudan}}</ref>
	:* For any <math>x\in\{0,1\}^k</math> and <math>w=C(x)</math>, <math>Pr[M^w(1^k)=1]=1</math>. In other words, M accepts given access to any codeword of C.		:* For any <math>x\in\{0,1\}^k</math> and <math>w=C(x)</math>, <math>Pr[M^w(1^k)=1]=1</math>. In other words, M accepts given access to any codeword of C.
	:* For <math>w\in\{0,1\}^n</math> such that <math>\delta(w,C)>\delta</math>, <math>Pr[M^w(1^k)=1]\leq1/2</math>. M must reject strings <math>\delta</math>-far from C at least half the time.		:* For <math>w\in\{0,1\}^n</math> such that <math>\delta(w,C)>\delta</math>, <math>Pr[M^w(1^k)=1]\leq1/2</math>. M must reject strings <math>\delta</math>-far from C at least half the time.

Citation bot: Add: eprint, class, year, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 18/33

2021-12-05T22:33:20Z

Add: eprint, class, year, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 18/33

← Previous revision		Revision as of 22:33, 5 December 2021
Line 19:		Line 19:

	== Limits ==		== Limits ==
	It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web\|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html\|title=Short Locally Testable Codes and Proofs (Survey)\|first=Oded\|last=Goldreich\|citeseerx = 10.1.1.110.2530}}</ref>		It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web\|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html\|title=Short Locally Testable Codes and Proofs (Survey)\|first=Oded\|last=Goldreich\|year=2005\|citeseerx = 10.1.1.110.2530}}</ref>

	# Polynomial arbitrarily close to linear; for any <math>\epsilon>0</math>, <math>n=k^{1+\epsilon}</math>.		# Polynomial arbitrarily close to linear; for any <math>\epsilon>0</math>, <math>n=k^{1+\epsilon}</math>.
Line 30:		Line 30:
	The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>		The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

	In November 2021 two preprints have reported<ref>{{cite arxiv\|~~last~~=Panteleev\|~~first~~=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|~~arxiv~~=2111.03654}}</ref><ref>{{cite arxiv\|~~last~~=Dinur\|~~first~~=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|~~arxiv~~=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.		In November 2021 two preprints have reported<ref>{{cite arxiv\|last1=Panteleev\|first1=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|class=cs.IT\|eprint=2111.03654}}</ref><ref>{{cite arxiv\|last1=Dinur\|first1=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|class=cs.IT\|eprint=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.

	== Connection with probabilistically checkable proofs ==		== Connection with probabilistically checkable proofs ==

Headbomb: Various citation & identifier cleanup, plus WP:GENFIXES [Citation bot to follow]]

2021-12-05T22:06:08Z

Various citation & identifier cleanup, plus WP:GENFIXES [Citation bot to follow]]

← Previous revision		Revision as of 22:06, 5 December 2021
Line 17:		Line 17:
	Also the rate of a code is the ratio between its message length and codeword length		Also the rate of a code is the ratio between its message length and codeword length
	:<math>r=\frac{\|x\|}{\|C(x)\|}</math>		:<math>r=\frac{\|x\|}{\|C(x)\|}</math>

	== Limits ==		== Limits ==
	It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web\|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html\|title=Short Locally Testable Codes and Proofs (Survey)\|first=Oded\|last=Goldreich\|citeseerx = 10.1.1.110.2530}}</ref>		It remains an open question whether there are any locally testable codes of linear size, but there are several constructions that are considered "nearly linear":<ref name=shortLTC>{{cite web\|url=http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html\|title=Short Locally Testable Codes and Proofs (Survey)\|first=Oded\|last=Goldreich\|citeseerx = 10.1.1.110.2530}}</ref>
Line 29:		Line 30:
	The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>		The next nearly linear goal is linear up to a [[polylogarithmic]] factor; <math>n=\text{poly}(\log k)*k</math>. Nobody has yet to come up with a linearly testable code that satisfies this constraint.<ref name=shortLTC/>

	In November 2021 two preprints have reported<ref>{{~~Cite~~ ~~journal~~\|last=Panteleev\|first=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|~~url=http://~~arxiv~~.org/abs/2111.03654\|journal~~=~~arXiv:~~2111.03654 ~~[quant-ph]~~}}</ref><ref>{{~~Cite~~ ~~journal~~\|last=Dinur\|first=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|~~url=http://~~arxiv~~.org/abs/2111.04808\|journal~~=~~arXiv:~~2111.04808 ~~[cs, math]~~}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.		In November 2021 two preprints have reported<ref>{{cite arxiv\|last=Panteleev\|first=Pavel\|last2=Kalachev\|first2=Gleb\|date=2021-11-05\|title=Asymptotically Good Quantum and Locally Testable Classical LDPC Codes\|arxiv=2111.03654}}</ref><ref>{{cite arxiv\|last=Dinur\|first=Irit\|author-link=Irit Dinur\|last2=Evra\|first2=Shai\|author-link2=Shai Evra\|last3=Livne\|first3=Ron\|last4=Lubotzky\|first4=Alexander\|author-link4=Alexander Lubotzky\|last5=Mozes\|first5=Shahar\|author-link5=Shahar Mozes\|date=2021-11-08\|title=Locally Testable Codes with constant rate, distance, and locality\|arxiv=2111.04808}}</ref><ref>{{Cite web\|last=Rorvig\|first=Mordechai\|date=2021-11-24\|title=Researchers Defeat Randomness to Create Ideal Code\|url=https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/\|url-status=live\|access-date=2021-11-24\|website=[[Quanta Magazine]]\|language=en}}</ref> the first polynomial-time construction of "<math>c^3</math>-LTCs" namely locally testable codes with constant rate <math>r</math>, constant distance <math>\delta</math> and constant locality <math>q</math>.


	== Connection with probabilistically checkable proofs ==		== Connection with probabilistically checkable proofs ==

Dabed: Added a "External links" section with a previous talk by Irit Dinur given on 6 October 2021

2021-11-27T14:54:03Z

Added a "External links" section with a previous talk by Irit Dinur given on 6 October 2021

← Previous revision		Revision as of 14:54, 27 November 2021
Line 68:		Line 68:
	== References ==		== References ==
	{{reflist}}		{{reflist}}

			== External links ==

			*{{Cite web\|date=6 October 2021\|title=Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality {{!}} Simons Institute for the Theory of Computing\|url=https://simons.berkeley.edu/events/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality\|url-status=live\|access-date=\|website=simons.berkeley.edu}}

	[[Category:Error detection and correction]]		[[Category:Error detection and correction]]