Siu On Chan
Skip Abstract Section
Abstract
We show optimal (up to a constant factor) NP-hardness for a maximum constraint satisfaction problem with k variables per constraint (Max-kCSP) whenever k is larger than the domain size. This follows from our main result concerning CSPs given by a predicate: A CSP is approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is analogous to Austrin and Mossel’s, bypassing their Unique-Games Conjecture assumption whenever the predicate is an abelian subgroup.
Our main ingredient is a new gap-amplification technique inspired by XOR lemmas. Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded-degree graphs, Almost-Coloring, Label-Cover, and various other problems.
- Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman. 1995. Derandomized graph products. Comput. Complex. 5, 1 (1995), 60--75. Google Scholar
Digital Library
- Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. 1997. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci. 54, 2 (April 1997), 317--331. Google ScholarDigital Library
- Sanjeev Arora, Boaz Barak, and David Steurer. 2010. Subexponential algorithms for unique games and related problems. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 563--572. Google ScholarDigital Library
- Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. 2005. On non-approximability for quadratic programs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 206--215. Google ScholarDigital Library
- Per Austrin and Johan Håstad. 2013. On the usefulness of predicates. ACM Trans. Comput. Theory 5, 1, Article 1 (May 2013), 1:1--1:24 pages. Google ScholarDigital Library
- Per Austrin, Subhash Khot, and Muli Safra. 2011. Inapproximability of vertex cover and independent set in bounded degree graphs. Theor. Comput. 7, 1 (2011), 27--43.Google ScholarCross Ref
- Per Austrin and Elchanan Mossel. 2009. Approximation resistant predicates from pairwise independence. Comput. Complex. 18, 2 (2009), 249--271.Google ScholarCross Ref
- Nikhil Bansal. 2015. Approximating independent sets in sparse graphs. In Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1--8. Google ScholarDigital Library
- Nikhil Bansal and Subhash Khot. 2009. Optimal long code test with one free bit. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 453--462. Google ScholarDigital Library
- Boaz Barak, Fernando Guadalupe dos Santos Lins Brandão, Aram Wettroth Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. 2012. Hypercontractivity, sum-of-squares proofs, and their applications. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 307--326. Google ScholarDigital Library
- Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. 2010. How to compress interactive communication. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 67--76. Google ScholarDigital Library
- Mihir Bellare, Oded Goldreich, and Madhu Sudan. 1998. Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput. 27, 3 (June 1998), 804--915. Google ScholarDigital Library
- Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. 2012. SDP gaps from pairwise independence. Theor. Comput. 8, 1 (2012), 269--289.Google ScholarCross Ref
- Eric Blais. 2009. Testing juntas nearly optimally. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 151--158. Google ScholarDigital Library
- Andrej Bogdanov and Emanuele Viola. 2010. Pseudorandom bits for polynomials. SIAM J. Comput. 39, 6 (Jan. 2010), 2464--2486.Google ScholarCross Ref
- Jop Briët, Harry Buhrman, Troy Lee, and Thomas Vidick. 2013. Multipartite entanglement in XOR games. Quant. Informat. Compu. 13, 3 & 4 (2013), 334--360. Google ScholarDigital Library
- Siu On Chan and Michael Molloy. 2013. A dichotomy theorem for the resolution complexity of random constraint satisfaction problems. SIAM J. Comput. 42, 1 (2013), 27--60.Google ScholarCross Ref
- Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 2009. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorith. 5, 3, Article 32 (July 2009), 14 pages. Google ScholarDigital Library
- Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay. 2008. Perfect parallel repetition theorem for quantum XOR proof systems. Comput. Complex. 17, 2 (2008), 282--299. Google ScholarDigital Library
- Irit Dinur and Prahladh Harsha. 2010. Composition of low-error 2-query PCPs using decodable PCPs. Property Testing (2010), 280--288.Google Scholar
- Irit Dinur, Subhash Khot, Will Perkins, and Muli Safra. 2010. Hardness of finding independent sets in almost 3-colorable graphs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 212--221. Google ScholarDigital Library
- Irit Dinur and Shmuel Safra. 2005. On the hardness of approximating minimum vertex cover. Ann. Math. 162, 1 (2005), 439--485.Google ScholarCross Ref
- Lars Engebretsen. 2004. The nonapproximability of non-boolean predicates. SIAM J. Discr. Math. 18, 1 (Jan. 2004), 114--129. Google ScholarDigital Library
- Lars Engebretsen and Venkatesan Guruswami. 2004. Is constraint satisfaction over two variables always easy? Random Struct. Algorith. 25, 2 (Sept. 2004), 150--178. Google ScholarDigital Library
- Lars Engebretsen and Jonas Holmerin. 2008. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct. Algorith. 33, 4 (Dec. 2008), 497--514. Google ScholarDigital Library
- Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2 (March 1996), 268--292. Google ScholarDigital Library
- Uriel Feige and Joe Kilian. 1998. Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57, 2 (Oct. 1998), 187--199. Google ScholarDigital Library
- Uriel Feige and Eran Ofek. 2006. Random 3 CNF formulas elude the Lovász theta function. arXiv CoRR abs/cs/0603084 (2006).Google Scholar
- Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. 2009. Agnostic learning of monomials by halfspaces is hard. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 385--394. Google ScholarDigital Library
- Michel Xavier Goemans and David P. Williamson. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6 (Nov. 1995), 1115--1145. Google ScholarDigital Library
- Oded Goldreich, Noam Nisan, and Avi Wigderson. 2011. On yao’s XOR-lemma. In Studies in Complexity and Cryptography. Lecture Notes in Computer Science, Vol. 6650. Springer, Berlin, 273--301.Google Scholar
- Dima Grigoriev. 2001. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259, 1--2 (May 2001), 613--622.Google ScholarCross Ref
- Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, and Luca Trevisan. 1998. A tight characterization of NP with 3 query PCPs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 8--17. Google ScholarDigital Library
- Venkatesan Guruswami and Prasad Raghavendra. 2008. Constraint satisfaction over a non-boolean domain: Approximation algorithms and unique-games hardness. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Springer, Berlin, 77--90. Google ScholarDigital Library
- Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu. 2012. Bypassing UGC from some optimal geometric inapproximability results. In Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 699--717. Google ScholarDigital Library
- Gustav Hast. 2005a. Approximating max kCSP—outperforming a random assignment with almost a linear factor. In International Colloquium Conference on Automata, Languages and Programming (ICALP). 956--968. Google ScholarDigital Library
- Gustav Hast. 2005b. Beating a Random Assignment. Ph.D. Dissertation. KTH, Stockholm.Google Scholar
- Johan Håstad. 1999. Clique is hard to approximate within n<sup>1 − ε</sup>. Acta Math. 182, 1 (March 1999), 105--142.Google ScholarCross Ref
- Johan Håstad. 2001. Some optimal inapproximability results. J. ACM 48, 4 (July 2001), 798--859. Google ScholarDigital Library
- Johan Håstad. 2008. Every 2-CSP allows nontrivial approximation. Comput. Complex. 17, 4 (2008), 549--566. Google ScholarDigital Library
- Johan Håstad. 2009. On the approximation resistance of a random predicate. Comput. Complex. 18, 3 (Oct. 2009), 413--434. Google ScholarDigital Library
- Johan Håstad. 2011. Satisfying degree-d equations over GF{2}<sup>n</sup>. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Springer-Verlag, Berlin, 242--253. Google ScholarDigital Library
- Johan Håstad and Avi Wigderson. 2003. Simple analysis of graph tests for linearity and PCP. Random Struct. Algorith. 22, 2 (March 2003), 139--160. Google ScholarDigital Library
- Edwin Hewitt and Kenneth Allen Ross. 1994. Abstract Harmonic Analysis: Volume 1: Structure of Topological Groups. Integration Theory. Group Representations (2nd ed.). Springer, Berlin.Google Scholar
- Thomas Holenstein. 2009. Parallel repetition: Simplification and the no-signaling case. Theor. Comput. 5, 1 (2009), 141--172.Google ScholarCross Ref
- Sangxia Huang. 2013. Improved hardness of approximating chromatic number. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Springer, Berlin, 233--243.Google ScholarCross Ref
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 4 (2001), 512--530. Google ScholarDigital Library
- Subhash Khot. 2001. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 600--609. Google ScholarDigital Library
- Subhash Khot. 2002a. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 23--32. Google ScholarDigital Library
- Subhash Khot. 2002b. On the power of unique 2-prover 1-round games. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 767--775. Google ScholarDigital Library
- Subhash Khot and Dana Moshkovitz. 2013. NP-hardness of approximately solving linear equations over reals. SIAM J. Comput. 42, 3 (2013), 752--791.Google ScholarCross Ref
- Subhash Khot and Muli Safra. 2013. A two-prover one-round game with strong soundness. Theor. Comput. 9, 28 (2013), 863--887.Google ScholarCross Ref
- Subhash Khot, Muli Safra, and Madhur Tulsiani. 2013. Towards an optimal query efficient PCP?. In Innovations in Theoretical Computer Science (ITCS). ACM, New York, NY, 173--186. Google ScholarDigital Library
- Subhash Khot and Rishi Saket. 2012. Hardness of finding independent sets in almost q-colorable graphs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Washington, DC, 380--389. Google ScholarDigital Library
- Bundit Laekhanukit. 2014. Parameters of two-prover-one-round game and the hardness of connectivity problems. In Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1626--1643. Google ScholarDigital Library
- Jean Bernard Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM J. Optimiz. 11, 3 (2001), 796--817. Google ScholarDigital Library
- Shachar Lovett. 2008. Lower bounds for adaptive linearity tests. In Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany, 515--526.Google Scholar
- Konstantin Makarychev and Yury Makarychev. 2014. Approximation algorithm for non-boolean max-k-CSP. Theor. Comput. 10, 13 (2014), 341--358. Extended abstract in APPROX 2012.Google ScholarCross Ref
- Dana Moshkovitz and Ran Raz. 2010. Two-query PCP with subconstant error. J. ACM 57, 5, Article 29 (June 2010), 29 pages. Google ScholarDigital Library
- Elchanan Mossel. 2010. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal. 19 (2010), 1713--1756.Google ScholarCross Ref
- Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. 2010. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 171, 1 (2010).Google Scholar
- Ryan O’Donnell and John Wright. 2012. A new point of NP-hardness for unique games. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 289--306. Google ScholarDigital Library
- Ryan O’Donnell and Yi Wu. 2009. Conditional hardness for satisfiable 3-CSPs. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 493--502. Google ScholarDigital Library
- Ryan O’Donnell and Yuan Zhou. 2013. Approximability and proof complexity. In Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 1537--1556. Google ScholarDigital Library
- Christos Harilaos Papadimitriou and Mihalis Yannakakis. 1991. Optimization, approximation, and complexity classes. J. Comput. System Sci. 43, 3 (1991), 425--440. Extended abstract in STOC 1988.Google ScholarCross Ref
- Pablo Parrilo. 2000. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. Dissertation. California Institute of Technology.Google Scholar
- Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Symposium on Theory of Computing (STOC). ACM, New York, NY, 245--254. Google ScholarDigital Library
- Anup Rao. 2011. Parallel repetition in projection games and a concentration bound. SIAM J. Comput. 40, 6 (Dec. 2011), 1871--1891. Google ScholarDigital Library
- Ran Raz. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3 (June 1998), 763--803. Google ScholarDigital Library
- Alex Samorodnitsky and Luca Trevisan. 2000. A PCP characterization of NP with optimal amortized query complexity. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 191--199. Google ScholarDigital Library
- Alex Samorodnitsky and Luca Trevisan. 2009. Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput. 39, 1 (2009), 323--360. Google ScholarDigital Library
- Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. 1995. Chernoff--hoeffding bounds for applications with limited independence. SIAM J. Discr. Math. 8, 2 (1995), 223--250. Google ScholarDigital Library
- Grant Schoenebeck. 2008. Linear level lasserre lower bounds for certain k-CSPs. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 593--602. Newer version available at the author’s homepage. Google ScholarDigital Library
- Alexander Alexandrovich Sherstov. 2012. The multiparty communication complexity of set disjointness. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 525--548. Google ScholarDigital Library
- Madhu Sudan and Luca Trevisan. 1998. Probabilistically checkable proofs with low amortized query complexity. In Symposium on Foundations of Computer Science (FOCS). IEEE, Los Alamitos, CA, 18--27. Google ScholarDigital Library
- Luca Trevisan. 1998. Recycling queries in PCPs and in linearity tests. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 299--308. Google ScholarDigital Library
- Luca Trevisan. 2001. Non-approximability results for optimization problems on bounded degree instances. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 453--461. Google ScholarDigital Library
- Madhur Tulsiani. 2009. CSP gaps and reductions in the lasserre hierarchy. In Symposium on Theory of Computing (STOC). ACM, New York, NY, 303--312. Google ScholarDigital Library
- Madhur Tulsiani and Pratik Worah. 2013. LS+ lower bounds from pairwise independence. In Conference on Computational Complexity (CCC). IEEE, Los Alamitos, CA. To appear.Google ScholarCross Ref
- Cenny Wenner. 2013. Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theor. Comput. 9, 23 (2013), 703--757.Google ScholarCross Ref
- David Zuckerman. 2007. Linear degree extractors and the inapproximability of max clique and chromatic number. Theor. Comput. 3, 1 (2007), 103--128.Google ScholarCross Ref
- Uri Zwick. 1998. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 201--210. Google ScholarDigital Library
Index Terms
- Approximation Resistance from Pairwise-Independent Subgroups
Index terms have been assigned to the content through auto-classification.
Recommendations
Approximation resistance from pairwise independent subgroups
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingWe show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain, whenever k is larger than the domain size. This follows from our main result concerning predicates over abelian groups. We show that a predicate is approximation ...
Languages with efficient zero-knowledge PCPs are in SZK
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of CryptographyA Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages ...
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard
CCC '08: Proceedings of the 2008 IEEE 23rd Annual Conference on Computational ComplexityWe prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. Our result answers a question of Alekhnovich and Razborov,...
Comments