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
(68)- New direct-product testers and \(2\)-query PCPs
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Combinatorial PCPs with short proofs
- Local decoding and testing of polynomials over grids
- Towards lower bounds on locally testable codes via density arguments
- Testability and repair of hereditary hypergraph properties
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Bounds on 2-query locally testable codes with affine tests
- Combinatorial construction of locally testable codes (extended abstract)
- Non-interactive proofs of proximity
- Short locally testable codes and proofs: a survey in two parts
- On the power of relaxed local decoding algorithms
- Good cyclic codes and the uncertainty principle
- 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
- A combination of testability and decodability by tensor products
- New direct-product testers and 2-query PCPs
- Succinct non-interactive arguments via linear interactive proofs
- Earthmover Resilience and Testing in Ordered Structures
- A hierarchy theorem for interactive proofs of proximity
- Locally testable codes and Cayley graphs
- Simple analysis of graph tests for linearity and PCP
- Relaxed locally correctable codes
- Smooth and strong PCPs
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- Zero knowledge LTCs and their applications
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- Relaxed locally correctable codes
- scientific article; zbMATH DE number 7650135 (Why is no real title available?)
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
- Combinatorial construction of locally testable codes
- Short locally testable codes and proofs
- Tensor Products of Weakly Smooth Codes Are Robust
- Computational integrity with a public random string from quasi-linear PCPs
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Characterizations of locally testable linear- and affine-invariant families
- A combinatorial characterization of smooth LTCs and applications
- Symmetric LDPC codes and local testing
- Linear-size constant-query IOPs for delegating computation
- On axis-parallel tests for tensor product codes
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- 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)
- Constant-round interactive proofs for delegating computation
- Testing algebraic geometric codes
- Rigid matrices from rectangular PCPs
- Composition of semi-LTCs by two-wise tensor products
- Shorter arithmetization of nondeterministic computations
- Quantum locally testable codes
- Locally testable codes with constant rate, distance, and locality
- Sample-based high-dimensional convexity testing
- Bounds on locally testable codes with unique tests
- Short PCPs with Polylog Query Complexity
- On axis-parallel tests for tensor product codes
- Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Locally Testable Cyclic Codes
- Explicit strong LTCs with inverse poly-log rate and constant soundness
- Reoptimization of constraint satisfaction problems with approximation resistant predicates
- Probabilistically checkable proofs and codes
- Symmetric LDPC codes and local testing
- Stabilizer testing and magic entropy via quantum Fourier analysis
- Dense locally testable codes cannot have constant rate and distance
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)
