Probabilistically checkable proofs and their consequences for approximation algorithms
type: Item
instance of: scholarly article
title: Probabilistically checkable proofs and their consequences for approximation algorithms
zbMATH Open document ID: 0824.68087
DOI: 10.1016/0012-365X(94)00112-V
author: Hans Jürgen Prömel
author: Stefan Hougardy
author: Angelika Steger
published in: Discrete Mathematics
publication date: 1995-11-06T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 722490
zbMATH Keywords: approximation algorithms
zbMATH Keywords: clique number
MaRDI profile type: Publication
cites work: Eigenvalues and expanders
cites work: Q4230322
cites work: Q4230321
cites work: Arithmetization: A new method in structural complexity theory
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: The complexity of theorem-proving procedures
cites work: Explicit constructions of linear-sized superconcentrators
cites work: The Complexity of Near-Optimal Graph Coloring
cites work: Q4198056
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: A still better performance guarantee for approximate graph coloring
cites work: The NP-completeness column: An ongoing guide
cites work: Q4142699
cites work: Q3210157
cites work: Algebraic methods for interactive proof systems
cites work: On the hardness of approximating minimization problems
cites work: Q4071451
cites work: Optimization, approximation, and complexity classes
cites work: Q4763385
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: IP = PSPACE
cites work: Q5625295
full work available at URL: 0012-365x(94)00112-v
OpenAlex ID: W2060401065
description: scientific article; zbMATH DE number 722490