Short locally testable codes and proofs
From MaRDI portal
derandomizationlocally testable codeserror-correcting codeslocally decodable codesprivate information retrievalprobabilistically checkable proofsself-correctionlow-degree tests
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Specification and verification (program logics, model checking, etc.) (68Q60) Other types of codes (94B60)
Recommendations
Cites work
- 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?)
- 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 \(\epsilon\)-soundness bound of the linearity test over GF(2)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Combinatorial PCPs with Efficient Verifiers
- Combinatorial construction of locally testable codes
- 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
- Improved non-approximability results
- Interactive proofs and the hardness of approximating cliques
- Locally Testable Codes Require Redundant Testers
- Locally testable codes and PCPs of almost-linear length
- 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 PCPs with Polylog Query Complexity
- Short locally testable codes and proofs
- 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
(13)- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Locally decodable codes for edit distance
- Short locally testable codes and proofs: a survey in two parts
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- Local Decoding and Testing for Homomorphisms
- Short locally testable codes and proofs
- Testing algebraic geometric codes
- Composition of semi-LTCs by two-wise tensor products
- Locally testable codes and PCPs of almost-linear length
- General constructions for information-theoretic private information retrieval
- Limitation on the Rate of Families of 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)
