Document Open Access Logo

Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Authors Huan Li, He Sun, Luca Zanetti

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.71.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Huan Li
  • School of Computer Science, Fudan University, China
He Sun
  • School of Informatics, University of Edinburgh, United Kingdom
Luca Zanetti
  • Department of Computer Science and Technology, University of Cambridge, United Kingdom

Funding

  • Zanetti, Luca: Supported by the ERC Starting Grant "DYNAMIC MARCH".

Acknowledgements

We are very grateful to Mihai Cucuringu for valuable discussions on Hermitian Laplacian matrices and their applications. We would also like to thank Chris Heunen for some fruitful conversations on topics closely related to this paper.

Cite As Get BibTex

Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.71

Abstract

We study spectral approaches for the MAX-2-LIN(k) problem, in which we are given a system of m linear equations of the form x_i - x_j is equivalent to c_{ij} mod k, and required to find an assignment to the n variables {x_i} that maximises the total number of satisfied equations. 
We consider Hermitian Laplacians related to this problem, and prove a Cheeger inequality that relates the smallest eigenvalue of a Hermitian Laplacian to the maximum number of satisfied equations of a MAX-2-LIN(k) instance I. We develop an O~(kn^2) time algorithm that, for any (1-epsilon)-satisfiable instance, produces an assignment satisfying a (1 - O(k)sqrt{epsilon})-fraction of equations. We also present a subquadratic-time algorithm that, when the graph associated with I is an expander, produces an assignment satisfying a (1- O(k^2)epsilon)-fraction of the equations. Our Cheeger inequality and first algorithm can be seen as generalisations of the Cheeger inequality and algorithm for MAX-CUT developed by Trevisan.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Spectra of graphs
Keywords
  • Spectral methods
  • Hermitian Laplacians
  • the Max-2-Lin problem
  • Unique Games

Metrics

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

Related Versions

References

  1. Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  2. Gunnar Andersson, Lars Engebretsen, and Johan Håstad. A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p. Journal of Algorithms, 39(2):162-204, 2001. Google Scholar
  3. Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential Algorithms for Unique Games and Related Problems. Journal of the ACM, 62(5), 2015. Google Scholar
  4. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy. In 40th Annual ACM Symposium on Theory of Computing (STOC'08), pages 21-28, 2008. Google Scholar
  5. Afonso S. Bandeira, Amit Singer, and Daniel A. Spielman. A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl., 34(4):1611-1630, 2013. Google Scholar
  6. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for unique games. In 38th Annual ACM Symposium on Theory of Computing (STOC'06), pages 205-214, 2006. Google Scholar
  7. Fan R. K. Chung. Spectral Graph Theory. Regional Conference Series in Mathematics, American Mathematical Society, 92:1-212, 1997. Google Scholar
  8. Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems. In 24th Annual ACM Symposium on Theory of Computing (STOC'92), pages 733-744, 1992. Google Scholar
  9. Uriel Feige and Daniel Reichman. On systems of linear equations with two variables per equation. In 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'04), pages 117-127, 2004. Google Scholar
  10. Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6):1115-1145, 1995. Google Scholar
  11. Michel X. Goemans and David P. Williamson. Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming. Journal of Computer and System Sciences, 68(2):442-470, 2004. Google Scholar
  12. Anupam Gupta and Kunal Talwar. Approximating unique games. In 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pages 99-106, 2006. Google Scholar
  13. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  14. Richard M. Karp. Reducibility Among Combinatorial Problems. In a symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  15. Subhash Khot. On the power of unique 2-prover 1-round games. In 34th Annual ACM Symposium on Theory of Computing (STOC'02), pages 767-775, 2002. Google Scholar
  16. 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
  17. Jon M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 46(5):604-632, 1999. Google Scholar
  18. Alexandra Kolla. Spectral algorithms for unique games. Computational Complexity, 20(2):177-206, 2011. Google Scholar
  19. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. Improved Cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap. In 45th Annual ACM Symposium on Theory of Computing (STOC'13), pages 11-20, 2013. Google Scholar
  20. James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. Journal of the ACM, 61(6):37:1-37:30, 2014. Google Scholar
  21. Richard Peng, He Sun, and Luca Zanetti. Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM Journal on Computing, 46(2):710-743, 2017. Google Scholar
  22. Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000. Google Scholar
  23. Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and computational harmonic analysis, 30(1):20, 2011. Google Scholar
  24. Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. Google Scholar
  25. David Steurer. Fast SDP Algorithms for Constraint Satisfaction Problems. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10), pages 684-697, 2010. Google Scholar
  26. Luca Trevisan. Approximation algorithms for unique games. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 197-205, 2005. Google Scholar
  27. Luca Trevisan. Max Cut and the Smallest Eigenvalue. SIAM Journal on Computing, 41(6):1769-1786, 2012. 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