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

DOI10.4230/LIPICS.ESA.2019.71MaRDI QIDQ5075818zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Max cut and the smallest eigenvalue
• Max CUT and the smallest eigenvalue
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Many sparse cuts via higher eigenvalues

Cites work

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• A new way of using semidefinite programming with applications to linear equations mod \(p\)
• Angular synchronization by eigenvectors and semidefinite programming
• Approximating unique games
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Authoritative sources in a hyperlinked environment
• Eigenvalues and expanders
• Fast SDP algorithms for constraint satisfaction problems
• Graph sparsification by effective resistances
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max cut and the smallest eigenvalue
• Near-optimal algorithms for unique games
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Partitioning well-clustered graphs: spectral clustering works!
• Reducibility among combinatorial problems
• Some optimal inapproximability results
• Spectral algorithms for unique games
• Subexponential algorithms for unique games and related problems
• Unique games on expanding constraint graphs are easy (extended abstract)

Cited in

(1)

• A Look at the Generalized Heron Problem through the Lens of Majorization-Minimization

This page was built for publication: Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075818)