Change search
ReferencesLink to record
Permanent link

Direct link
Approximation resistance on satisfiable instances for predicates with few accepting inputs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1600-5290
2013 (English)In: Symposium on Theory of Computing Conference / [ed] Dan Boneh, Tim Roughgarden, Joan Feigenbaum, 2013, 457-466 p.Conference paper (Refereed)
Abstract [en]

 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 [5]. We also use techniques from Wenner [32] to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.

Place, publisher, year, edition, pages
2013. 457-466 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-124328DOI: 10.1145/2488608.2488666ScopusID: 2-s2.0-84879803083ISBN: 978-1-4503-2029-0OAI: diva2:634074
Symposium on Theory of Computing Conference STOC '13, Palo Alto, CA, June, 1-4, 2013
EU, European Research Council, 6853

QC 20130719

Available from: 2013-06-28 Created: 2013-06-28 Last updated: 2013-07-19Bibliographically approved

Open Access in DiVA

stoc13(352 kB)45 downloads
File information
File name FULLTEXT01.pdfFile size 352 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusConference website

Search in DiVA

By author/editor
Huang, Sangxia
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 45 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 51 hits
ReferencesLink to record
Permanent link

Direct link