Locally testable codes and PCPs of almost-linear length
From MaRDI portal
Recommendations
- Tolerant Linearity Testing and Locally Testable Codes
- Combinatorial construction of locally testable codes (extended abstract)
- Locally testable codes with constant rate, distance, and locality
- Locally testable vs. locally decodable codes
- Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- Towards lower bounds on locally testable codes via density arguments
- Short locally testable codes and proofs
- Combinatorial construction of locally testable codes
- Bounds on locally testable codes with unique tests
Cited in
(70)- Testing algebraic geometric codes
- Good cyclic codes and the uncertainty principle
- Non-interactive proofs of proximity
- Smooth and strong PCPs
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Succinct non-interactive arguments via linear interactive proofs
- Linear-size constant-query IOPs for delegating computation
- Combinatorial PCPs with short proofs
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Bounds on 2-query locally testable codes with affine tests
- A combinatorial characterization of smooth LTCs and applications
- Bounds on locally testable codes with unique tests
- Zero knowledge LTCs and their applications
- Locally testable codes and Cayley graphs
- Testability and repair of hereditary hypergraph properties
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Dense locally testable codes cannot have constant rate and distance
- Short locally testable codes and proofs
- Probabilistically checkable proofs and codes
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Quantum locally testable codes
- Tensor Products of Weakly Smooth Codes Are Robust
- Locally Testable Cyclic Codes
- Combinatorial construction of locally testable codes (extended abstract)
- Combinatorial construction of locally testable codes
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Short PCPs with Polylog Query Complexity
- Reoptimization of constraint satisfaction problems with approximation resistant predicates
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- A hierarchy theorem for interactive proofs of proximity
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
- Simple analysis of graph tests for linearity and PCP
- New direct-product testers and 2-query PCPs
- Short locally testable codes and proofs: a survey in two parts
- Symmetric LDPC codes and local testing
- Shorter arithmetization of nondeterministic computations
- Composition of semi-LTCs by two-wise tensor products
- On the power of relaxed local decoding algorithms
- Local decoding and testing of polynomials over grids
- Relaxed locally correctable codes
- Constant-round interactive proofs for delegating computation
- Sample-based high-dimensional convexity testing
- On axis-parallel tests for tensor product codes
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Earthmover Resilience and Testing in Ordered Structures
- On axis-parallel tests for tensor product codes
- New direct-product testers and 2-query PCPs
- Symmetric LDPC codes and local testing
- A combination of testability and decodability by tensor products
- Computational integrity with a public random string from quasi-linear PCPs
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Relaxed locally correctable codes
- scientific article; zbMATH DE number 7650135 (Why is no real title available?)
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Locally testable codes with constant rate, distance, and locality
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Rigid matrices from rectangular PCPs
- Linear relaxed locally decodable and correctable codes do not need adaptivity and two-sided error
- On the relaxed LDC of BGHSV: a survey that corrects the record
- On the locally testable code of Dinur \textit{et al.} (2021)
- Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
- Towards lower bounds on locally testable codes via density arguments
- Stabilizer testing and magic entropy via quantum Fourier analysis
- Relaxed locally correctable codes with improved parameters
- Good locally testable codes
- Characterizations of locally testable linear- and affine-invariant families
This page was built for publication: Locally testable codes and PCPs of almost-linear length
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546312)
