Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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 Strictly Dominating Parity
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-1600-5290
2012 (English)Report (Other academic)
Abstract [en]

In this paper, we study the approximability of Max CSP(P) where P is a Boolean predicate. We prove that assuming Khot’s d-to-1 Conjecture, if the set of accepting inputs of P strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate MaxCSP(P) better than the simple random assignment algorithm even on satisfiable instances.This is a generalization of a work by O’Donnell and Wu which proved that it is NP-hard to approximate satisfiable instances of Max CSP(NTW) beyond 5/8 + epsilon for any epsilon > 0 based on Khot’s d-to-1 Conjecture, where NTW is the “Not Two” predicate of size 3.

Place, publisher, year, edition, pages
2012. , 21 p.
Series
Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092 ; 40
Keyword [en]
pcp, approximation, d-to-1, perfect completeness
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-108165OAI: oai:DiVA.org:kth-108165DiVA: diva2:579115
Funder
EU, European Research Council, 6853
Note

QC 20130109

Available from: 2013-01-09 Created: 2012-12-19 Last updated: 2013-01-09Bibliographically approved

Open Access in DiVA

tr12-040(837 kB)113 downloads
File information
File name FULLTEXT01.pdfFile size 837 kBChecksum SHA-512
486558e391ac4920e4bfe922b4e8831600e632012a9117727a3997af8e358dd171749d51b5523e568b4f6db7f73a56a0a351b5e8eb78874bdb6d974ede235fb1
Type fulltextMimetype application/pdf

Other links

http://eccc.hpi-web.de/report/2012/040

Search in DiVA

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

Search outside of DiVA

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

urn-nbn

Altmetric score

urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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