## CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Sivakanth Gopi

Microsoft Researcher

March 30, 2020

A theorist's dream is to show that hard instances/obstructions for an (optimal) algorithm can be used as gadgets to prove tight hardness reductions (which proves optimality of the algorithm). An example of such a result is that of Prasad Raghavendra who showed that for any constraint satisfaction problem (CSP), there is an SDP which achieves the best possible approximation factor assuming UGC. We show that a similar phenomenon occurs in CSPs with global modular constraints.