Proving Weak Approximability Without Algorithms

Syed, Ridwan; Tulsiani, Madhur

doi:10.4230/LIPIcs.APPROX-RANDOM.2016.20

File

LIPIcs.APPROX-RANDOM.2016.20.pdf

Filesize: 0.53 MB
15 pages

Document Identifiers

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.20
URN: urn:nbn:de:0030-drops-66437

Author Details

Ridwan Syed

Madhur Tulsiani

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.20

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.

Keywords

approximability
constraint satisfaction problems
approximation resistance
linear programming
semidefinite programming

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. In Proceedings of the 23rd IEEE Conference on Computational Complexity, pages 249-258, Los Alamitos, CA, USA, 2008. IEEE Computer Society. URL: http://front.math.ucdavis.edu/0802.2300, URL: http://dx.doi.org/10.1109/CCC.2008.20.
Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 447-456, 2013. URL: http://dx.doi.org/10.1145/2488608.2488665.
Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, and Ola Svensson. Approximating linear threshold predicates. ACM Transactions on Computation Theory (TOCT), 4(1):2, 2012.
Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability Results for Equations over Finite Groups. Theor. Comput. Sci., 312(1):17-45, 2004. URL: http://dx.doi.org/10.1016/S0304-3975(03)00401-8.
M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, 1995. Preliminary version in Proc. of STOC'94.
Venkatesan Guruswami and Euiwoong Lee. Towards a characterization of approximation resistance for symmetric CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 305-322, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.305.
Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, and Luca Trevisan. A tight characterization of NP with 3 query PCPs. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pages 8-17, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743424.
Gustav Hast. Beating a Random Assignment. PhD thesis, Royal Institute of Technology, Sweden, 2005.
Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001.
Johan Håstad. Every 2-CSP Allows Nontrivial Approximation. Computational Complexity, 17(4):549-566, 2008.
Subhash Khot. Hardness Results for Coloring 3-Colorable 3-Uniform Hypergraphs. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pages 23-32, 2002. URL: http://dx.doi.org/10.1109/SFCS.2002.1181879.
Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th ACM Symposium on Theory of Computing, pages 767-775, 2002.
Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proceedings of the 46th ACM Symposium on Theory of Computing, pages 634-643. ACM, 2014.
Avner Magen, Siavosh Benabbas, and Per Austrin. On quadratic threshold CSPs. Discrete Mathematics &Theoretical Computer Science, 14, 2012.
Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th ACM Symposium on Theory of Computing, pages 245-254, 2008.
Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 191-199, 2000.
Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCPs. In Proceedings of the 38th ACM Symposium on Theory of Computing, pages 11-20, 2006.
Johan Håstad. On the Efficient Approximability of Constraint Satisfaction Problems. In Surveys in Combinatorics, volume 346, pages 201-222. Cambridge University Press, 2007.
Uri Zwick. Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 201-210, 1998.