Document Open Access Logo

Improved NP-Inapproximability for 2-Variable Linear Equations

Authors Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, John Wright

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2015.341.pdf
  • Filesize: 0.55 MB
  • 20 pages

Document Identifiers

Subject Classification

Keywords
  • approximability
  • unique games
  • linear equation
  • gadget
  • linear programming

Metrics

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

Abstract

An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8).  The previous best result, standing for over 15 years, had 5/4 in place of 11/8.  Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2.

Our proof is by a modified gadget reduction from a pairwise-independent predicate.  We also show an inherent limitation to this type of gadget reduction.  In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

Cite As Get BibTex

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 341-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.341

Author Details

Johan Håstad
Sangxia Huang
Rajsekar Manokaran
Ryan O’Donnell
John Wright

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√log n) approximation algorithms for Min-Uncut, Min-2CNF-Deletion, and directed cut problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 573-581, 2005. Google Scholar
  2. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for Unique Games and related problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pages 563-572, 2010. Google Scholar
  3. Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 222-231, 2004. Google Scholar
  4. Per Austrin and Johan Håstad. On the usefulness of predicates. ACM Trans. Comput. Theory, 5(1):1:1-1:24, 2013. Google Scholar
  5. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and non-approximability - towards tight results. SIAM Journal of Computing, 27(3):804-915, 1998. Google Scholar
  6. Siu On Chan. Approximation resistance from pairwise independent subgroups. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 447-456, 2013. Google Scholar
  7. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for Unique Games. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 205-214, 2006. Google Scholar
  8. Miroslav Chlebík and Janka Chlebíková. On approximation hardness of the minimum 2SAT-DELETION problem. In Proceedings of the 29th Annual International Symposium on Mathematical Foundations of Computer Science, pages 263-273, 2004. Google Scholar
  9. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439-485, 2005. Google Scholar
  10. Uriel Feige and Daniel Reichman. On systems of linear equations with two variables per equation. In Proceedings of the 7th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 117-127, 2004. Google Scholar
  11. Michel Goemans and David Williamson. A 0.878 approximation algorithm for MAX-2SAT and MAX-CUT. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 422-431, 1994. Google Scholar
  12. Anupam Gupta, Kunal Talwar, and David Witmer. Sparsest Cut on bounded treewidth graphs: algorithms and hardness results. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 281-290, 2013. Google Scholar
  13. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  14. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 767-775, 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. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. Journal of the ACM, 57(5):29, 2010. Google Scholar
  17. Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics, 171(1):295-341, 2010. Google Scholar
  18. Ryan O'Donnell and John Wright. A new point of NP-hardness for Unique-Games. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 289-306, 2012. Google Scholar
  19. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal of Computing, 40(6):1871-1891, 2011. Google Scholar
  20. Luca Trevisan, Gregory Sorkin, Madhu Sudan, and David Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6):2074-2097, 2000. Google Scholar
  21. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357-365, 2005. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact