Efficient probabilistically checkable proofs and applications to approximations

DOI10.1145/167088.167174zbMath1310.68083OpenAlexW2152221184MaRDI QIDQ5248498

Mihir Bellare, Alexander Russell, Carstent Lund

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (69)

Subquadratic SNARGs in the random oracle model ⋮ Annealed replication: A new heuristic for the maximum clique problem ⋮ Algebraic testing and weight distributions of codes. ⋮ Approximating multidimensional subset sum and Minkowski decomposition of polygons ⋮ The minimum feature set problem ⋮ Recent results in hardness of approximation ⋮ Some recent strong inapproximability results ⋮ A self-tester for linear functions over the integers with an elementary proof of correctness ⋮ A note on PCP vs. MIP ⋮ On proving that a graph has no large clique: A connection with Ramsey theory ⋮ Scheduling of conditional executed jobs on unrelated processors ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ Almost optimal set covers in finite VC-dimension ⋮ The complexity of approximating a nonlinear program ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ MNP: A class of NP optimization problems ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ The complexity of probabilistic lobbying ⋮ A computationally intractable problem on simplicial complexes ⋮ Low-degree test with polynomially small error ⋮ Fault detection tests for stuck-at faults on parity counter inputs ⋮ The facility location problem with maximum distance constraint ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Lower bound on SNARGs in the random oracle model ⋮ A toolbox for barriers on interactive oracle proofs ⋮ Approximating covering integer programs with multiplicity constraints ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Derandomized parallel repetition via structured PCPs ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ The approximation of maximum subgraph problems ⋮ Approximate solution of NP optimization problems ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm ⋮ Maximum agreement and compatible supertrees ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Maximizing Polynomials Subject to Assignment Constraints ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ MNP: A class of NP optimization problems ⋮ Approximating the tree and tour covers of a graph ⋮ A well-characterized approximation problem ⋮ Timetabling with passenger routing ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Composition of Low-Error 2-Query PCPs Using Decodable PCPs ⋮ Linear-consistency testing. ⋮ An approximation algorithm for MAX 3-SAT ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ On the domination search number ⋮ Short Locally Testable Codes and Proofs ⋮ Hardness of approximating the minimum solutions of linear Diophantine equations ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Zero knowledge and the chromatic number ⋮ Robust locally testable codes and products of codes ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ On Khot’s unique games conjecture ⋮ Interactive and probabilistic proof-checking ⋮ Bicriteria Network Design Problems ⋮ Testing algebraic geometric codes ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ On Dinur’s proof of the PCP theorem ⋮ The inapproximability of non-NP-hard optimization problems. ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Approximating cost-based abduction is NP-hard ⋮ Direct Sum Testing

This page was built for publication: Efficient probabilistically checkable proofs and applications to approximations