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

DOI10.4230/LIPIcs.ESA.2019.71OpenAlexW2979088439MaRDI QIDQ5075818

He Sun, Luca Zanetti, Hu-An Li

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1811.10909

zbMATH Keywords

spectral methodsunique gamesHermitian Laplaciansthe Max-2-Lin problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Angular synchronization by eigenvectors and semidefinite programming
• Spectral algorithms for unique games
• Eigenvalues and expanders
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p
• Near-optimal algorithms for unique games
• Authoritative sources in a hyperlinked environment
• Subexponential Algorithms for Unique Games and Related Problems
• On the power of unique 2-prover 1-round games
• Approximating unique games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max Cut and the Smallest Eigenvalue
• Reducibility among Combinatorial Problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Cheeger Inequality for the Graph Connection Laplacian
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Improved Cheeger's inequality
• Partitioning Well-Clustered Graphs: Spectral Clustering Works!
• Graph Sparsification by Effective Resistances
• Unnamed Item
• Unnamed Item
• Unnamed Item