Locally testable code
Encyclopedia
In theoretical computer science
, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm
. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few (e.g. a constant number of) positions of the message and can then determine with high probability whether the message is close to a codeword.
Locally testable codes have applications in average-case complexity
and the design of probabilistically checkable proofs.
Locally decodable codes are closely related to locally testable codes, in that they make it possible to decode single bits of the message by only looking at few positions of a possibly corrupted codeword.
T (the tester) that on input 1n and given oracle access to a string y ∈ {0, 1}n satisfies the following:
In theoretical computer science, one is typically interested in locally testable codes whose query complexity is constant or at most logarithmic.
. The Hadamard code is testable with 3 queries and soundness 1 - δ.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm
Property testing
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem...
. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few (e.g. a constant number of) positions of the message and can then determine with high probability whether the message is close to a codeword.
Locally testable codes have applications in average-case complexity
Average-case complexity
Average-case complexity is a subfield of computational complexity theory that studies the complexity of algorithms on random inputs.The study of average-case complexity has applications in the theory of cryptography....
and the design of probabilistically checkable proofs.
Locally decodable codes are closely related to locally testable codes, in that they make it possible to decode single bits of the message by only looking at few positions of a possibly corrupted codeword.
Definition
A family of error-correcting codes Cn ⊆ {0, 1}n is locally testable with soundness s(δ) (where s(δ) < 1 for every δ > 0), and query complexity q(n) if there exists a non-adaptive oracle algorithmOracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
T (the tester) that on input 1n and given oracle access to a string y ∈ {0, 1}n satisfies the following:
- Completeness: If y ∈ C, then Ty(1n) accepts with probability 1.
- Soundness: If the Hamming distanceHamming distanceIn information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
between y and C is δn, then Ty(1n) accepts with probability at most s(δ).
In theoretical computer science, one is typically interested in locally testable codes whose query complexity is constant or at most logarithmic.
Examples
An example of a locally testable code is the Hadamard codeHadamard code
The Hadamard code is an error-correcting code that is used for error detection and correction when transmitting messages over very noisy or unreliable channels....
. The Hadamard code is testable with 3 queries and soundness 1 - δ.