Approximating constraint satisfaction problems on high-dimensional expanders

DOI10.1109/FOCS.2019.00021MaRDI QIDQ6944216zbMATH OpenFDO

Authors Fernando Granha Jeronimo, Vedat Levi Alev, Madhur Tulsiani

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00021

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(5)

• Sparse cuts in hypergraphs from random walks on simplicial complexes
• Explicit SoS lower bounds from high-dimensional expanders
• Garland's technique for posets and high-dimensional Grassmannian expanders
• Sparser abelian high-dimensional expanders
• Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT

This page was built for publication: Approximating constraint satisfaction problems on high-dimensional expanders

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