Approximating Constraint Satisfaction Problems on High-Dimensional Expanders

Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani

We consider the problem of approximately solving constraint satisfaction problems with arity $k>2$ ($k$-CSPs) on instances satisfying certain expansion properties, when viewed as…