REVIEW 3 cited by
Some Applications of Coding Theory in Computational Complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
Error-correcting codes and related combinatorial constructs play an important role in several recent (and old) results in computational complexity theory. In this paper we survey results on locally-testable and locally-decodable error-correcting codes, and their applications to complexity theory and to cryptography. Locally decodable codes are error-correcting codes with sub-linear time error-correcting algorithms. They are related to private information retrieval (a type of cryptographic protocol), and they are used in average-case complexity and to construct ``hard-core predicates'' for one-way permutations. Locally testable codes are error-correcting codes with sub-linear time error-detection algorithms, and they are the combinatorial core of probabilistically checkable proofs.
Forward citations
Cited by 3 Pith papers
-
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
For every odd q ≥ 3, any q-query binary locally decodable code with constant distance satisfies k ≤ O~(n^(1-2/q)), the first bound of this form for q ≥ 5.
-
A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
For every constant odd number of queries q, any q-query locally decodable code has length at least (k/(log k))^(q/(q-2)) up to constants.
-
Adaptive Quantum Computers: decoding and state preparation
Adaptive quantum computers, mixing quantum circuits with classical parity processing, provably separate from classical shallow circuits on Hadamard list decoding and also prepare standard quantum states more efficiently.
Discussion (0). Continue with ORCID to comment.