On the usefulness of predicates

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

  • Per Austrin
  • Johan Håstad

Research units

  • Royal Institute of Technology

Abstract

Motivated by the pervasiveness of strong in approximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate P being \emph{useful} for a (real-valued) objective Q: given an almost satisfiable Max-P instance, there is an algorithm that beats a random assignment on the corresponding Max-Q instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate P is exactly the same as saying that P is useful for P itself. We say that P is useless if it is not useful for any Q. Under the Unique Games Conjecture, we can give a complete and simple characterization of useless Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pair wise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.

Details

Original languageEnglish
Title of host publicationProceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012
Publication statusPublished - 2012
MoE publication typeA4 Article in a conference publication
EventIEEE Computer Society Technical Committee on Mathematical Foundations of Computing - Porto, Portugal
Duration: 26 Jun 201229 Jun 2012

Publication series

NameIEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Conference

ConferenceIEEE Computer Society Technical Committee on Mathematical Foundations of Computing
CountryPortugal
CityPorto
Period26/06/201229/06/2012

ID: 17001890