Approximation resistance on satisfiable instances for predicates with few accepting inputs

DOI10.1145/2488608.2488666zbMath1294.68092OpenAlexW2081537403MaRDI QIDQ5495816

Sangxia Huang

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-124328

zbMATH Keywords

probabilistically checkable proofapproximation resistanceMax CSPsatisfiable instance

Mathematics Subject Classification ID

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

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Improved Dictatorship Test with Perfect Completeness

This page was built for publication: Approximation resistance on satisfiable instances for predicates with few accepting inputs