Discover and read the best of Twitter Threads about #goldreichtestablecodessurvey
Most recents (3)
#GoldreichTestableCodesSurvey-5
"Local testability
By local testability we mean that the object can be tested for the natural property (i.e., being a codeword or a valid proof) using a small (typically constant)[Footnote: In this part, we associate local testability with tests
>
"Local testability
By local testability we mean that the object can be tested for the natural property (i.e., being a codeword or a valid proof) using a small (typically constant)[Footnote: In this part, we associate local testability with tests
>
>that perform a constant number of probes.] number of probes, each recovering individual bits in a standard representation of the object. Thus, local testability allows for super-fast testing of the corresponding objects. The tests are probabilistic and hence the result
>
>
>is correct only with high probability.[Footnote: It is easy to see that deterministic tests will perform very poorly, and the same holds with respect to probabilistic tests that make no error.] Furthermore, correctness refers to a relaxed notion of deciding (which
>
>
#GoldreichTestableCodesSurvey-4
"Codes, proofs and their length
Codes are sets of strings (of equal length), typically, having a large pairwise distance. Equivalently, codes are viewed as mappings from short (𝑘-bit) strings to longer (𝑛-bit) strings, called codewords,
>
"Codes, proofs and their length
Codes are sets of strings (of equal length), typically, having a large pairwise distance. Equivalently, codes are viewed as mappings from short (𝑘-bit) strings to longer (𝑛-bit) strings, called codewords,
>
>such that the codewords are distant from one another. We will focus on codes with relative constant distance; that is, every two 𝑛-bit codewords are at distance Ω(𝑛) apart. The length of the code is measured in terms of the length of the pre-image (i.e., we are interested
>
>
>in the growth of 𝑛 as a function of 𝑘).
Turning to proofs, these are defined with respect to a verification procedure for assertions of a certain length, and their length is measured in terms of the length of the assertion. The verification procedure must satisfy the natural
>
Turning to proofs, these are defined with respect to a verification procedure for assertions of a certain length, and their length is measured in terms of the length of the assertion. The verification procedure must satisfy the natural
>
#GoldreichTestableCodesSurvey-2
"Abstract
We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small
>
"Abstract
We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small
>
>number of probes, each retrieving a single bit in the representation of the object.
This yields super-fast approximate #testing of the corresponding property (ie., be a codeword or a valid proof).
We also review the related concept of local decodable [recte 'locally decodable'
>
This yields super-fast approximate #testing of the corresponding property (ie., be a codeword or a valid proof).
We also review the related concept of local decodable [recte 'locally decodable'
>
>LG,I]
The survey consists of two independent (i.e., self-contained) parts that cover the same material at different levels of rigor and detail. Still, in spite of the repetitions, there may be a benefit in reading both parts.
Keywords
#ErrorCorrectingCodes
Probabilistically
>
The survey consists of two independent (i.e., self-contained) parts that cover the same material at different levels of rigor and detail. Still, in spite of the repetitions, there may be a benefit in reading both parts.
Keywords
#ErrorCorrectingCodes
Probabilistically
>
