License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.305
URN: urn:nbn:de:0030-drops-53095
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5309/
Go to the corresponding LIPIcs Volume Portal

Guruswami, Venkatesan ; Lee, Euiwoong

Towards a Characterization of Approximation Resistance for Symmetric CSPs

pdf-format:
19.pdf (0.5 MB)

Abstract

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to 1 with some probability achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), where satisfaction of each constraint only depends on the number of true literals in its scope. Thus a SCSP of arity k can be described by a subset of allowed number of true literals.

For SCSPs without negation, we conjecture that a simple sufficient condition to be approximation resistant by Austrin and Hastad is indeed necessary. We show that this condition has a compact analytic representation in the case of symmetric CSPs (depending only on the gap between the largest and smallest numbers in S), and provide the rationale behind our conjecture. We prove two interesting special cases of the conjecture, (i) when S is an interval and (ii) when S is even. For SCSPs with negation, we prove that the analogous sufficient condition by Austrin and Mossel is necessary for the same two cases, though we do not pose an analogous conjecture in general.

BibTeX - Entry

@InProceedings{guruswami_et_al:LIPIcs:2015:5309,
  author =	{Venkatesan Guruswami and Euiwoong Lee},
  title =	{{Towards a Characterization of Approximation Resistance for Symmetric CSPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{305--322},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5309},
  URN =		{urn:nbn:de:0030-drops-53095},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.305},
  annote =	{Keywords: Constraint Satisfaction Problems, Approximation resistance}
}

Keywords: Constraint Satisfaction Problems, Approximation resistance
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI