Proof verification and the hardness of approximation problems

DOI10.1145/278298.278306zbMath1065.68570OpenAlexW2148352980WikidataQ55872309 ScholiaQ55872309MaRDI QIDQ3158513

Sanjeev Arora, Madhu Sudan, Mario Szegedy, Carstent Lund, Rajeev Motwani

Publication date: 25 January 2005

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

Full work available at URL: https://doi.org/10.1145/278298.278306

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) 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 ⋮ Generalized XOR non-locality games with graph description on a square lattice ⋮ 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 ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Parallelizable delegation from LWE ⋮ \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem ⋮ Unnamed Item ⋮ \(\mathrm{C}^\ast\)-algebras. Abstracts from the workshop held August 7--13, 2022 ⋮ 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 ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Scalable and transparent proofs over all large fields, via elliptic curves. ECFFT. II ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses ⋮ Local-vs-global combinatorics ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Communication and information complexity ⋮ The complexity of spanning tree problems involving graphical indices ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Characterization of hard-to-cover CSPs ⋮ When polynomial approximation meets exact computation ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Relaxed Locally Correctable Codes ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM ⋮ When polynomial approximation meets exact computation ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ No-signaling linear PCPs ⋮ 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 ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ On the advantage over a random assignment ⋮ Alignment distance of regular tree languages ⋮ Alignment distance of regular tree languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ 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 ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Hardness of Rainbow Coloring Hypergraphs ⋮ Reed-Muller Codes ⋮ 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 ⋮ Algebraic testing and weight distributions of codes. ⋮ Towards optimal lower bounds for clique and chromatic number. ⋮ On regularity of Max-CSPs and Min-CSPs ⋮ Bayesian agency: linear versus tractable contracts ⋮ On the approximability of clique and related maximization problems ⋮ Bounds on 2-query locally testable codes with affine tests ⋮ Fast approximate probabilistically checkable proofs ⋮ Model independent approach to probabilistic models ⋮ Inapproximability results for equations over finite groups ⋮ A natural family of optimization problems with arbitrarily small approximation thresholds ⋮ Bottleneck bichromatic full Steiner trees ⋮ Quantum information and the PCP theorem ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This page was built for publication: Proof verification and the hardness of approximation problems