Short locally testable codes and proofs
From MaRDI portal
derandomizationerror-correcting codeslocally decodable codeslocally testable codeslow-degree testsprivate information retrievalprobabilistically checkable proofsself-correction
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Randomized algorithms (68W20) Other types of codes (94B60)
Recommendations
Cites work
- 3-query locally decodable codes of subexponential length
- A Parallel Repetition Theorem
- Algebraic methods for interactive proof systems
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Bounds on \(2\)-query codeword testing
- Breaking the -soundness bound of the linearity test over GF(2)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Combinatorial construction of locally testable codes
- Combinatorial PCPs with Efficient Verifiers
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Computational Complexity
- Computationally Sound Proofs
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Efficient probabilistically checkable proofs and applications to approximations
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Fast approximate PCPs
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Fully parallelized multi-prover protocols for NEXP-time
- scientific article; zbMATH DE number 5485460 (Why is no real title available?)
- scientific article; zbMATH DE number 1306876 (Why is no real title available?)
- scientific article; zbMATH DE number 1775406 (Why is no real title available?)
- scientific article; zbMATH DE number 1405671 (Why is no real title available?)
- scientific article; zbMATH DE number 3417337 (Why is no real title available?)
- Improved non-approximability results
- Interactive proofs and the hardness of approximating cliques
- Locally testable codes and PCPs of almost-linear length
- Locally Testable Codes Require Redundant Testers
- Lower bounds for linear locally decodable codes and private information retrieval
- Nearly-linear size holographic proofs
- Non-deterministic exponential time has two-prover interactive protocols
- On the efficiency of local decoding procedures for error-correcting codes
- On the power of multi-prover interactive protocols
- Private information retrieval
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Property testing of massively parametrized problems -- a survey
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Self-testing/correcting with applications to numerical problems
- Short locally testable codes and proofs
- Short PCPs with Polylog Query Complexity
- Small PCPs with low query complexity
- Some 3CNF properties are hard to test
- Some optimal inapproximability results
- The PCP theorem by gap amplification
- Upper bound on the communication complexity of private information retrieval
Cited in
(14)- Testing algebraic geometric codes
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- General constructions for information-theoretic private information retrieval
- Locally decodable codes for edit distance
- Short locally testable codes and proofs
- Locally testable codes and PCPs of almost-linear length
- Local Decoding and Testing for Homomorphisms
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- Limitation on the Rate of Families of Locally Testable Codes
- Short locally testable codes and proofs: a survey in two parts
- Composition of semi-LTCs by two-wise tensor products
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Good locally testable codes
This page was built for publication: Short locally testable codes and proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088191)
