Proof verification and the hardness of approximation problems

DOI10.1145/278298.278306zbMath1065.68570DBLPjournals/jacm/AroraLMSS98OpenAlexW2148352980WikidataQ55872309 ScholiaQ55872309MaRDI QIDQ3158513

Carstent Lund

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 ⋮ Rigid matrices from rectangular PCPs ⋮ Unnamed Item ⋮ NP-hardness of approximating meta-complexity: a cryptographic approach ⋮ Commitments to quantum states ⋮ Quantum free games ⋮ Unnamed Item ⋮ No-signaling linear PCPs ⋮ Product-state approximations to quantum states ⋮ On the parameterized intractability of determinant maximization ⋮ The no-meet matroid ⋮ Beyond MPC-in-the-head: black-box constructions of short zero-knowledge proofs ⋮ Complexity barriers as independence ⋮ The Complexity of Zero Knowledge ⋮ Synchronous values of games ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation ⋮ Probabilistically checkable arguments for all NP ⋮ Zero-knowledge IOPs approaching witness length ⋮ STIR: Reed-Solomon proximity testing with fewer queries ⋮ 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 ⋮ Quantum de Finetti theorems under local measurements with applications ⋮ APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ Simultaneous Approximation of Constraint Satisfaction Problems

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