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, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP