Limitation on the Rate of Families of Locally Testable Codes
From MaRDI portal
Publication:4933361
DOI10.1007/978-3-642-16367-8_3zbMath1308.68056OpenAlexW2133169151MaRDI QIDQ4933361
Publication date: 12 October 2010
Published in: Property Testing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_3
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Towards lower bounds on locally testable codes via density arguments, A combinatorial characterization of smooth LTCs and applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- Self-testing/correcting with applications to numerical problems
- A statistical theorem of set addition
- 2-transitivity is insufficient for local testability
- Improved low-degree testing and its applications
- Bounds on locally testable codes with unique tests
- Local list-decoding and testing of random linear codes from high error
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Short Locally Testable Codes and Proofs
- Expander codes
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Testing Polynomials over General Fields
- Testing Reed–Muller Codes
- Locally Testable Cyclic Codes
- Combinatorial Construction of Locally Testable Codes
- Two-query PCP with subconstant error
- Low Rate Is Insufficient for Local Testability
- Locally Testable vs. Locally Decodable Codes
- Succinct Representation of Codes with Applications to Testing
- Universal Arguments and their Applications
- Probabilistic checking of proofs
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Computationally Sound Proofs
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Locally Testable Codes Require Redundant Testers
- On 2-Query Codeword Testing with Near-Perfect Completeness
- Some Applications of Coding Theory in Computational Complexity
- Robust locally testable codes and products of codes
- Some 3CNF Properties Are Hard to Test
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Sound 3-Query PCPPs Are Long
- The PCP theorem by gap amplification
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
