Document Open Access Logo

UG-Hardness to NP-Hardness by Losing Half

Authors Amey Bhangale, Subhash Khot

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.3.pdf
  • Filesize: 0.63 MB
  • 20 pages

Document Identifiers

Author Details

Amey Bhangale
  • Weizmann Institute of Science, Rehovot, Israel
Subhash Khot
  • Courant Institute of Mathematical Sciences, New York University, USA

Funding

  • Bhangale, Amey: Research supported by Irit Dinur’s ERC-CoG grant 772839.
  • Khot, Subhash: Research supported by NSF CCF-1813438, Simons Collaboration on Algorithms and Geometry, and Simons Investigator Award.

Acknowledgements

We would like to thank anonymous referees for helpful comments.

Cite As Get BibTex

Amey Bhangale and Subhash Khot. UG-Hardness to NP-Hardness by Losing Half. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.3

Abstract

The 2-to-2 Games Theorem of [Subhash Khot et al., 2017; Dinur et al., 2018; Dinur et al., 2018; Dinur et al., 2018] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least (1/2-epsilon) fraction of the constraints vs. no assignment satisfying more than epsilon fraction of the constraints, for every constant epsilon>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least (1/2-epsilon) fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied. 
We use this guarantee to convert the known UG-hardness results to NP-hardness. We show: 
1) Tight inapproximability of approximating independent sets in degree d graphs within a factor of Omega(d/(log^2 d)), where d is a constant. 
2) NP-hardness of approximate the Maximum Acyclic Subgraph problem within a factor of 2/3+epsilon, improving the previous ratio of 14/15+epsilon by Austrin et al. [Austrin et al., 2015]. 
3) For any predicate P^{-1}(1) subseteq [q]^k supporting a balanced pairwise independent distribution, given a P-CSP instance with value at least 1/2-epsilon, it is NP-hard to satisfy more than (|P^{-1}(1)|/(q^k))+epsilon fraction of constraints.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • NP-hardness
  • Inapproximability
  • Unique Games Conjecture

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, May 1998. (Preliminary version in 33rd FOCS, 1992). Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. jacm, 45(1):70-122, January 1998. (Preliminary version in 33rd FOCS, 1992). Google Scholar
  3. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Theory of Computing, 7(3):27-43, 2011. Google Scholar
  4. Per Austrin, Rajsekar Manokaran, and Cenny Wenner. On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems. Theory of Computing, 11(10):257-283, 2015. Google Scholar
  5. Per Austrin and Elchanan Mossel. Approximation Resistant Predicates from Pairwise Independence. computational complexity, 18(2):249-271, June 2009. Google Scholar
  6. N. Bansal, A. Gupta, and G. Guruganesh. On the Lovász Theta Function for Independent Sets in Sparse Graphs. SIAM Journal on Computing, 47(3):1039-1055, 2018. Google Scholar
  7. Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, pages 250-261, 2010. Google Scholar
  8. Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Bi-Covering: Covering Edges with Two Small Subsets of Vertices. SIAM J. Discrete Math., 31(4):2626-2646, 2017. Google Scholar
  9. Siu On Chan. Approximation resistance from pairwise-independent subgroups. Journal of the ACM (JACM), 63(3):27, 2016. Google Scholar
  10. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in Grassmann graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 940-951. ACM, 2018. Google Scholar
  11. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 376-389, 2018. Google Scholar
  12. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268-292, 1996. Google Scholar
  13. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 573-582. IEEE, 2008. Google Scholar
  14. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, STOC 2002, pages 767-775. ACM, 2002. Google Scholar
  15. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. Google Scholar
  16. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 576-589, 2017. Google Scholar
  17. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 592-601, 2018. Google Scholar
  18. Subhash Khot and Assaf Naor. Approximate kernel clustering. Mathematika, 55(1-2):129-165, 2009. Google Scholar
  19. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- ε. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  20. Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 634-643. ACM, 2014. Google Scholar
  21. Subhash A Khot and Nisheeth K Vishnoi. The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into 𝓁₁. Journal of the ACM (JACM), 62(1):8, 2015. Google Scholar
  22. Alantha Newman. The maximum acyclic subgraph problem and degree-3 graphs. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, pages 147-158. Springer, 2001. Google Scholar
  23. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245-254. ACM, 2008. Google Scholar
  24. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
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 About DROPS Imprint Privacy Contact