#DinurEvraLivneLubotzkyMozes-3
"1 Introduction
A locally testable code (LTC) is an #ErrorCorrectingCode that has a property-tester. The tester reads 𝑞 bits (randomly - but not necessarily uniformly chosen) from a given word, and rejects words with probability proportional to
>
"1 Introduction
A locally testable code (LTC) is an #ErrorCorrectingCode that has a property-tester. The tester reads 𝑞 bits (randomly - but not necessarily uniformly chosen) from a given word, and rejects words with probability proportional to
>
>their distance from the code. The parameter 𝑞 is called the locality of the tester.
A random code has, with high probability, constant rate and distance, but locality that is proportional to the length. This is true even for random #LDPC codes [BHR05], and
>
A random code has, with high probability, constant rate and distance, but locality that is proportional to the length. This is true even for random #LDPC codes [BHR05], and
>
>a priori the mere existence of codes with constant locality is not obvious. The first LTCs appear implicitly in works on #ProgramChecking [BLR90] and on #ProbabilisticallyCheckableProofs (PCPs) [BFL91, LFKN92, BFLS91, AS98, ALM+98].
>
>
>A formal definition of an LTC appeared simultaneously in several places [BFLS91, RS96, FS13, Aro94] (see [Gol10] for a detailed history.
[I could be mistaken, but it seems to me that arXiv:2111.04808v2 doesn't cite Goldreich correctly. Neither the title nor pages. In detail,
>
[I could be mistaken, but it seems to me that arXiv:2111.04808v2 doesn't cite Goldreich correctly. Neither the title nor pages. In detail,
>
>the reference in arXiv:2111.04808v2 is:
[Gol10] Oded Goldreich. Short Locally Testable Codes and Proofs: A Survey in Two Parts. Property Testing: Current Research and Surveys. LNCS 6650, pages 65–104. Springer, Berlin, Heidelberg, 2010.
In the published version of LNCS 6650,>
[Gol10] Oded Goldreich. Short Locally Testable Codes and Proofs: A Survey in Two Parts. Property Testing: Current Research and Surveys. LNCS 6650, pages 65–104. Springer, Berlin, Heidelberg, 2010.
In the published version of LNCS 6650,>
>i.e., in ISBN 978-3-642-22669-4, there IS an article by Goldreich titled "Short Locally Testable Codes and Proofs", but
(1) the subtitle "A Survey in Two Parts" does NOT occur anywhere in ISBN 978-3-642-22669-4 (it does occur in a preprint version of Goldreich's survey though);>
(1) the subtitle "A Survey in Two Parts" does NOT occur anywhere in ISBN 978-3-642-22669-4 (it does occur in a preprint version of Goldreich's survey though);>
>
(2) in ISBN 978-3-642-22669-4, "Short Locally Testable Codes and Proofs" occurs on pages 333-372.
However, I now found the cause of the mismatch: Goldreich published this survey (with minor changes) twice, in similar books (see below). The ONLY #error in arXiv:2111.04808v2 is
>
(2) in ISBN 978-3-642-22669-4, "Short Locally Testable Codes and Proofs" occurs on pages 333-372.
However, I now found the cause of the mismatch: Goldreich published this survey (with minor changes) twice, in similar books (see below). The ONLY #error in arXiv:2111.04808v2 is
>
>that the wrong LNCS-number is given: the version of Goldreich's survey WITH a subtitle was published in LNCS 6390, not "6650". LG,I]
Spielman, in his PhD thesis [Spi96], discusses the possibility of having an #ErrorCorrecting code that is locally testable (he uses the term
>
Spielman, in his PhD thesis [Spi96], discusses the possibility of having an #ErrorCorrecting code that is locally testable (he uses the term
>
>‘checkable code’) and explains its potential applicability: [Spielman-quote]“A checker would be able to read only a constant number of bits of a received signal and then estimate the chance that a decoder will be able to correct the #errors, then the checker can instantly
>
>
>
request a retransmission of that block,
before the decoder has wasted its time
trying to decode the message. Unfortunately
all known codes with local-checkers [sic] have
rate approaching zero."[end Spielman-quote]
Goldreich and Sudan [J. of the ACM, 53(4):558–655, 2006]
>
request a retransmission of that block,
before the decoder has wasted its time
trying to decode the message. Unfortunately
all known codes with local-checkers [sic] have
rate approaching zero."[end Spielman-quote]
Goldreich and Sudan [J. of the ACM, 53(4):558–655, 2006]
>
• • •
Missing some Tweet in this thread? You can try to
force a refresh
