Content deleted Content added
→Definition: Last edit unintendedly deleted previous two edits, edited them back |
→Limits: Once again reverted erroneous deletions, hopefully no mistake this time |
||
Line 28:
These have both been achieved, even with constant query complexity and a binary [[Alphabet (computer science)|alphabet]], such as with <math>n=k^{1+1/(\log k)^c}</math> for any <math>c\in (0,1)</math>.
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 2021 a preprint has reported<ref>{{Cite journal|last=Dinur|first=Irit|last2=Evra|first2=Shai|last3=Livne|first3=Ron|last4=Lubotzky|first4=Alexander|last5=Mozes|first5=Shahar|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>.
== Connection with probabilistically checkable proofs ==
| |||