Probabilistically checkable proofs and their consequences for approximation algorithms

DOI10.1016/0012-365X(94)00112-VMaRDI QIDQ1344618zbMATH OpenOpenAlexFDO

Authors Hans Jürgen Prömel, Stefan Hougardy, Angelika Steger

Publication date 6 November 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)00112-v

zbMATH Keywords

approximation algorithmsclique number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1256636
• Probabilistic checking of proofs
• scientific article; zbMATH DE number 2212170
• scientific article; zbMATH DE number 1256635
• Proof verification and the hardness of approximation problems

Cites work

• A still better performance guarantee for approximate graph coloring
• Algebraic methods for interactive proof systems
• Approximating maximum independent sets by excluding subgraphs
• Arithmetization: A new method in structural complexity theory
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 742944 (Why is no real title available?)
• scientific article; zbMATH DE number 3349977 (Why is no real title available?)
• IP = PSPACE
• Non-deterministic exponential time has two-prover interactive protocols
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes
• The Complexity of Near-Optimal Graph Coloring
• The complexity of theorem-proving procedures
• The Knowledge Complexity of Interactive Proof Systems
• The NP-completeness column: An ongoing guide

Cited in

(16)

• Efficient rational proofs with strong utility-gap guarantees
• Efficient checking of polynomials and proofs and the hardness of approximation problems
• Optimal Proximity Proofs Revisited
• Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
• On the possibilities and limitations of pseudodeterministic algorithms
• scientific article; zbMATH DE number 5999718 (Why is no real title available?)
• Proof verification and the hardness of approximation problems
• A Randomized Algorithm for BBCSPs in the Prover-Verifier Model
• Probabilistic checking of proofs
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• scientific article; zbMATH DE number 1789920 (Why is no real title available?)
• Verified Approximation Algorithms
• On the concrete efficiency of probabilistically-checkable proofs
• A probabilistic algorithm to test local algebraic observability in polynomial time

This page was built for publication: Probabilistically checkable proofs and their consequences for approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344618)