Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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
Identifiers
URN: urn:nbn:se:kth:diva-124328DOI: 10.1145/2488608.2488666Scopus ID: 2-s2.0-84879803083ISBN: 978-1-4503-2029-0 (print)OAI: oai:DiVA.org:kth-124328DiVA: diva2:634074
Conference
Symposium on Theory of Computing Conference STOC '13, Palo Alto, CA, June, 1-4, 2013
Funder
EU, European Research Council, 6853
Note

QC 20130719

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

Open Access in DiVA

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

Other links

Publisher's full textScopusConference website

Authority records BETA

Huang, Sangxia

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 56 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 64 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf