Locally testable codes and PCPs of almost-linear length
From MaRDI portal
Publication:3546312
DOI10.1145/1162349.1162351zbMath1315.94144OpenAlexW2022381972WikidataQ56851227 ScholiaQ56851227MaRDI QIDQ3546312
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1162349.1162351
Linear codes (general theory) (94B05) Other types of codes (94B60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Bounds on 2-query locally testable codes with affine tests, Good cyclic codes and the uncertainty principle, Succinct non-interactive arguments via linear interactive proofs, Quantum Locally Testable Codes, A Hierarchy Theorem for Interactive Proofs of Proximity, Linear-size constant-query IOPs for delegating computation, Reoptimization of constraint satisfaction problems with approximation resistant predicates, Unnamed Item, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Unnamed Item, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, Unnamed Item, Unnamed Item, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Unnamed Item, The tensor product of two good codes is not necessarily robustly testable, On the rectangle method in proofs of robustness of tensor products, On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field, Tensor Products of Weakly Smooth Codes Are Robust, Relaxed Locally Correctable Codes, Sample-Based High-Dimensional Convexity Testing., Shorter arithmetization of nondeterministic computations, Composition of semi-LTCs by two-wise tensor products, Non-interactive proofs of proximity, Symmetric LDPC codes and local testing, Towards lower bounds on locally testable codes via density arguments, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Symmetric LDPC Codes and Local Testing, Testability and repair of hereditary hypergraph properties, Smooth and strong PCPs, Earthmover Resilience and Testing in Ordered Structures, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, 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, A combinatorial characterization of smooth LTCs and applications, Every Set in P Is Strongly Testable Under a Suitable Encoding, Characterizations of locally testable linear- and affine-invariant families, On the Power of Relaxed Local Decoding Algorithms, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, Testing algebraic geometric codes, A combination of testability and decodability by tensor products, Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Combinatorial PCPs with short proofs
