Locally testable code: Difference between revisions

Revision as of 22:42, 2 February 2022

Revision as of 09:22, 27 September 2023

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/>

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 ==

Line 71:

== 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]]