On the approximation resistance of a random predicate

DOI10.1007/s00037-009-0262-8zbMath1213.68706OpenAlexW2162784288WikidataQ56958874 ScholiaQ56958874MaRDI QIDQ626662

Johan T. Håstad

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0262-8

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemapproximation resistance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (1)

A query efficient non-adaptive long code test with perfect completeness

This page was built for publication: On the approximation resistance of a random predicate