Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
From MaRDI portal
Publication:5757455
DOI10.1137/S0097539705446810zbMath1118.68071OpenAlexW2044199052MaRDI QIDQ5757455
Eli Ben-Sasson, Prahladh Harsha, Madhu Sudan, Oded Goldreich, Salil P. Vadhan
Publication date: 7 September 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539705446810
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Bounds on 2-query locally testable codes with affine tests, An adaptivity hierarchy theorem for property testing, Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, Succinct non-interactive arguments via linear interactive proofs, Quantum Locally Testable Codes, Arguments of Proximity, Proofs of proximity for context-free languages and read-once branching programs, ZK-PCPs from leakage-resilient secret sharing, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, A PCP theorem for interactive proofs and applications, Linear-size constant-query IOPs for delegating computation, On the (In)security of Kilian-based SNARGs, Low-degree test with polynomially small error, Unnamed Item, Bridging a Small Gap in the Gap Amplification of Assignment Testers, Erasures versus errors in local decoding and property testing, Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, Succinct arguments for RAM programs via projection codes, Unnamed Item, Unnamed Item, Unnamed Item, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, 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, Erasure-Resilient Property Testing, PCPs and the hardness of generating synthetic data, Derandomized parallel repetition via structured PCPs, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Relaxed Locally Correctable Codes, Proofs of Proximity for Distribution Testing, Combinatorial PCPs with efficient verifiers, An Exponential Separation Between MA and AM Proofs of Proximity, On uniformity and circuit lower bounds, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, Shorter arithmetization of nondeterministic computations, Composition of semi-LTCs by two-wise tensor products, An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, Non-interactive proofs of proximity, A PCP Characterization of AM, Towards lower bounds on locally testable codes via density arguments, Limitation on the Rate of Families of Locally Testable Codes, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Invariance in Property Testing, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Smooth and strong PCPs, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, Efficient Probabilistically Checkable Debates, \textsc{Fractal}: post-quantum and transparent recursive proofs from holography, Short Locally Testable Codes and Proofs, Bravely, Moderately: A Common Theme in Four Recent Works, A combinatorial characterization of smooth LTCs and applications, From Local to Robust Testing via Agreement Testing, Every Set in P Is Strongly Testable Under a Suitable Encoding, Improved bounds for quantified derandomization of constant-depth circuits and polynomials, 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, A combination of testability and decodability by tensor products, On hitting-set generators for polynomials that vanish rarely, Unnamed Item, Efficient Construction of Rigid Matrices Using an NP Oracle, Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity, Computational Integrity with a Public Random String from Quasi-Linear PCPs, A PCP of proximity for real algebraic polynomials, Combinatorial PCPs with short proofs
