Locally testable codes and PCPs of almost-linear length
From MaRDI portal
Publication:3546312
DOI10.1145/1162349.1162351zbMath1315.94144WikidataQ56851227 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
94B05: Linear codes (general theory)
94B60: Other types of codes
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W20: Randomized algorithms
Related Items
A Hierarchy Theorem for Interactive Proofs of Proximity, Unnamed Item, Unnamed Item, Unnamed Item, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Symmetric LDPC Codes and Local Testing, On the Power of Relaxed Local Decoding Algorithms, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Relaxed Locally Correctable Codes, Sample-Based High-Dimensional Convexity Testing., Earthmover Resilience and Testing in Ordered Structures, Every Set in P Is Strongly Testable Under a Suitable Encoding, A combination of testability and decodability by tensor products, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Unnamed Item, Unnamed Item, Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity, Combinatorial PCPs with short proofs, Bounds on 2-query locally testable codes with affine tests, 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, On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field, Shorter arithmetization of nondeterministic computations, Composition of semi-LTCs by two-wise tensor products, Symmetric LDPC codes and local testing, Towards lower bounds on locally testable codes via density arguments, Characterizations of locally testable linear- and affine-invariant families, 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, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), A combinatorial characterization of smooth LTCs and applications, 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, Quantum Locally Testable Codes, Tensor Products of Weakly Smooth Codes Are Robust
