1 Search Results for "Syed, Ridwan"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.20
Proving Weak Approximability Without Algorithms

Authors: Ridwan Syed and Madhur Tulsiani

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
A boolean predicate is said to be strongly approximation resistant if, given a near-satisfiable instance of its maximum constraint satisfaction problem, it is hard to find an assignment such that the fraction of constraints satisfied deviates significantly from the expected fraction of constraints satisfied by a random assignment. A predicate which is not strongly approximation resistant is known as weakly approximable. We give a new method for proving the weak approximability of predicates, using a simple SDP relaxation, without designing and analyzing new rounding algorithms for each predicate. Instead, we use the recent characterization of strong approximation resistance by Khot et al. [STOC 2014], and show how to prove that for a given predicate, certain necessary conditions for strong resistance derived from their characterization, are violated. By their result, this implies the existence of a good rounding algorithm, proving weak approximability. We show how this method can be used to obtain simple proofs of (weak approximability analogues of) various known results on approximability, as well as new results on weak approximability of symmetric predicates.
Cite as

Ridwan Syed and Madhur Tulsiani. Proving Weak Approximability Without Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{syed_et_al:LIPIcs.APPROX-RANDOM.2016.20,
  author =	{Syed, Ridwan and Tulsiani, Madhur},
  title =	{{Proving Weak Approximability Without Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.20},
  URN =		{urn:nbn:de:0030-drops-66437},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.20},
  annote =	{Keywords: approximability, constraint satisfaction problems, approximation resistance, linear programming, semidefinite programming}
}
  • Refine by Author
  • 1 Syed, Ridwan
  • 1 Tulsiani, Madhur

  • Refine by Classification

  • Refine by Keyword
  • 1 approximability
  • 1 approximation resistance
  • 1 constraint satisfaction problems
  • 1 linear programming
  • 1 semidefinite programming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact