Change search
ReferencesLink to record
Permanent link

Direct link
Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (extended abstract)
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, 325-337 p.Conference paper (Refereed)
Abstract [en]

Håstad established that any predicate P ⊆ {0,1} m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was mitigated by O'Donnell, Wu, and Huang under the d-to-1 Conjecture. They showed the threshold result that if a predicate contains parity of width at least three, then it is approximation resistant also for satisfiable instances. We extend modern hardness of approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove unconditionally the same approximation resistance result for predicates of width four.

Place, publisher, year, edition, pages
Springer-Verlag , 2012. 325-337 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7408 LNCS
Keyword [en]
Approximation hardness, Extended abstracts, Hardness of approximation, IS approximation, Combinatorial optimization, Approximation algorithms
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-104871DOI: 10.1007/978-3-642-32512-0_28ScopusID: 2-s2.0-84865286142ISBN: 978-364232511-3OAI: diva2:567834
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, 15 August 2012 through 17 August 2012, Cambridge, MA

QC 20121114

Available from: 2012-11-14 Created: 2012-11-14 Last updated: 2014-09-29Bibliographically approved
In thesis
1. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
Open this publication in new window or tab >>Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Etikettäckningsreduktioner för Obetingad Approximationssvårighet av Vilkorssatisfiering
Abstract [en]

Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). In these, one is given a collection of constraints on variables with the task of finding an assignment satisfying the greatest number of constraints. In particular, parity constraints dictate that an odd (alt. even) number of variables are assigned a certain value.Satisfiable collections of parity constraints are easy in the sense that they can be efficiently solved via Gaussian elimination. We prove the threshold phenomenon that when constraints accept even one more assignment besides parities, then it is hard to find approximate solutions which are essentially better than random assignments.We also investigate the uselessness of predicates. Uselessness is a stronger hardness property in the sense that even if one was permitted to choose the acceptance criteria for given constraints, it is NP-hard to find solutions beating random assignments. We provide the first examples of predicates which are useless even when all variables appear unnegated.Finally, in an Ordering CSP (OCSP), one receives a set of items to order and constraints specifying how the items should be ordered relative to one another. For example, in the problem Maximum Betweenness, we have constraints of the form "order x between y and z". Our contribution is to significantly improve the approximation hardness of various OCSPs and provide the first unconditional direct Probabilistically Checkable Proofs for OCSPs.Notably, all results were previously known assuming the Unique Games Conjecture and the d-to-1 Conjecture. Our unconditional analogues of the same theorems involve developments for dealing with various obstacles faced by conventional techniques.

Place, publisher, year, edition, pages
Stockholm: Numerical Analysis and Computer Science (NADA), Stockholm University, 2014. xii, 52 p.
Optimization, NP, Approximation, Approximability, Inapproximability, Constraint Satisfaction, CSP, Boolean Analysis, Satisfiability, SAT, Acyclic Subgraph, Betweenness, Unique Games
National Category
Computer Science
Research subject
Computer Science
urn:nbn:se:kth:diva-151402 (URN)
Public defence
2014-10-21, F3, Sing Sing, Lindstedtsvägen 26, KTH, Stockholm, 13:15 (English)
Approximation of NP-hard optimization problems
EU, European Research Council, 226203

QC 20140929

Available from: 2014-09-29 Created: 2014-09-19 Last updated: 2014-09-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Wenner, Cenny
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
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: 31 hits
ReferencesLink to record
Permanent link

Direct link