Approximation resistance on satisfiable instances for predicates with few accepting inputs
2013 (English)In: Symposium on Theory of Computing Conference / [ed] Dan Boneh, Tim Roughgarden, Joan Feigenbaum, 2013, 457-466 p.Conference paper (Refereed)
For every integer k≥ 3, we prove that there is a predicate P on k Boolean variables with 2O(k1/3) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Hastad and Khot where the predicate has 2 O(k1/2) accepting assignments.
Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Chan . We also use techniques from Wenner  to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.
Place, publisher, year, edition, pages
2013. 457-466 p.
IdentifiersURN: urn:nbn:se:kth:diva-124328DOI: 10.1145/2488608.2488666ScopusID: 2-s2.0-84879803083ISBN: 978-1-4503-2029-0OAI: oai:DiVA.org:kth-124328DiVA: diva2:634074
Symposium on Theory of Computing Conference STOC '13, Palo Alto, CA, June, 1-4, 2013
FunderEU, European Research Council, 6853
QC 201307192013-06-282013-06-282013-07-19Bibliographically approved