Publication:3002760
From MaRDI portal
DOI10.4086/toc.2005.v001a007zbMath1213.68331MaRDI QIDQ3002760
Subhash A. Khot, Johan T. Håstad
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2005.v001a007
computational complexity; approximation algorithms; inapproximability; PCP; perfect completeness; amortized query bits; probablistically checkable proofs
68Q25: Analysis of algorithms and problem complexity
68Q60: Specification and verification (program logics, model checking, etc.)
Related Items
Query-Efficient Dictatorship Testing with Perfect Completeness, Unnamed Item, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, New tools and connections for exponential-time approximation, Strong Inapproximability of the Shortest Reset Word, Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete, A query efficient non-adaptive long code test with perfect completeness, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP