Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
We consider the problem of approximately solving constraint satisfaction problems with arity k > 2 (kCSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of k-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed …