Constraint Satisfaction Problems (CSPs) are a class of extensively studied combinatorial optimization problems in theoretical computer science. Typically, an instantiation of an \(r\) -CSP \(\Psi (V,E,[R],\lbrace \Pi _e\rbrace _{e \in E})\)  is characterized by an underlying \(r\) -ary hypergraph \(\Psi = (V,E)\)  with label set \([R]\) , and a constraint \(\Pi _e \subset [R]^r\)  for every edge \(e \in E\) . The objective is to find a labeling \(\sigma :V \rightarrow [R]\)  that satisfies the maximum fraction of constraints – here, the labeling \(\sigma \)  satisfies a hyperedge \(e= (v_1,\ldots ,v_r)\)  if \((\sigma (v_1),\sigma (v_2),\ldots ,\sigma (v_r)) \in \Pi _e\) . The expressive power of CSPs is evident from the long list of fundamental and well-studied combinatorial optimization problems that can be expressed as a CSP: Max-Cut [1]}, [2]}, Coloring [3]}, [4]}, Unique Games [5]}, [6]} are all examples of CSPs, each of which has been studied extensively by themselves (see [7]} for a comprehensive overview). The tight interplay between CSPs and Probabilistically Checkable Proofs (PCPs) has led to a line of works spanning decades resulting in substantial progress in the theory of approximation of CSPs, eventually leading to landmark results such as tight upper and lower bounds for every CSP assuming the Unique Games Conjecture [8]}.
