Revision as of 20:17, 30 April 2015 edit Phil Boswell (talk \| contribs) Administrators 40,568 edits convert dodgy URL to ID using AWB ← Previous edit		Revision as of 08:29, 14 November 2016 edit undo Pintoch (talk \| contribs) Extended confirmed users 2,763 edits m →Limits: change \|id={{citeseerx}} to \|citeseerx= using AWB Next edit →
Line 17: == 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\|idciteseerx = ~~{{citeseerx\|~~10.1.1.110.2530}}}}</ref> # Polynomial arbitrarily close to linear; for any <math>\epsilon>0</math>, <math>n=k^{1+\epsilon}</math>.

Locally testable code: Difference between revisions