Probabilistic checking of proofs

DOI10.1145/273865.273901zbMath0903.68076DBLPjournals/jacm/AroraS98OpenAlexW2019578639WikidataQ55869216 ScholiaQ55869216MaRDI QIDQ3841041

Shmuel Safra

Publication date: 25 October 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1998-45/

zbMATH Keywords

error-correcting codescomplexity hierarchieshardness of approximations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

CLAP: A New Algorithm for Promise CSPs ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Interactive Proofs with Approximately Commuting Provers ⋮ Quantum Locally Testable Codes ⋮ Simple analysis of graph tests for linearity and PCP ⋮ Testing properties of directed graphs: acyclicity and connectivity* ⋮ Generalized XOR non-locality games with graph description on a square lattice ⋮ Interactive Oracle Proofs ⋮ A query efficient non-adaptive long code test with perfect completeness ⋮ On the Complexity of the Minimum Independent Set Partition Problem ⋮ Local Testing of Lattices ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Unnamed Item ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Unnamed Item ⋮ Ligero: lightweight sublinear arguments without a trusted setup ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Erasures versus errors in local decoding and property testing ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Testing membership for timed automata ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem ⋮ Unnamed Item ⋮ Succinct NP Proofs from an Extractability Assumption ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Justifying groups in multiwinner approval voting ⋮ Succinct arguments for RAM programs via projection codes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local-vs-global combinatorics ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Communication and information complexity ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Characterization of hard-to-cover CSPs ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Relaxed Locally Correctable Codes ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Linear-consistency testing. ⋮ No-signaling linear PCPs ⋮ Unnamed Item ⋮ Rigid matrices from rectangular PCPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ No-signaling linear PCPs ⋮ Polylogarithmic two-round argument systems ⋮ Product-state approximations to quantum states ⋮ The Complexity of Zero Knowledge ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Cube Attacks on Tweakable Black Box Polynomials ⋮ On the advantage over a random assignment ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ From Local to Robust Testing via Agreement Testing ⋮ Every Set in P Is Strongly Testable Under a Suitable Encoding ⋮ UG-hardness to NP-hardness by losing half ⋮ Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Self-correctors for Cryptographic Modules ⋮ Outlaw distributions and locally decodable codes ⋮ Unnamed Item ⋮ High-rate codes with sublinear-time decoding ⋮ A combination of testability and decodability by tensor products ⋮ Linear game non-contextuality and Bell inequalities—a graph-theoretic approach ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Formation Potential Field for Trajectory Tracking Control of Multi-Agents in Constrained Space ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ An Improved Dictatorship Test with Perfect Completeness ⋮ Computational Integrity with a Public Random String from Quasi-Linear PCPs ⋮ Direct Sum Testing ⋮ Subquadratic SNARGs in the random oracle model

This page was built for publication: Probabilistic checking of proofs