Short locally testable codes and proofs: a survey in two parts
From MaRDI portal
(Redirected from Publication:4933364)
derandomizationerror-correcting codeslocally decodable codeslocally testable codeslow-degree testsprivate information retrievalprobabilistically checkable proofsself-correction
Complexity of proofs (03F20) 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) Theory of error-correcting codes and error-detecting codes (94B99)
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 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
- 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
(10)- Non-interactive proofs of proximity
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Short locally testable codes and proofs
- Quantum locally testable codes
- Local testing of lattices
- On the power of relaxed local decoding algorithms
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- On axis-parallel tests for tensor product codes
- Good quantum LDPC codes with linear time decoders
- Towards local testability for quantum coding
This page was built for publication: Short locally testable codes and proofs: a survey in two parts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933364)
