CSPs with Global Constraints. There have been several works which study specific instances of CSPs with global constraints. Of particular interest is the Max-Bisection problem which is Max-Cut with a global bisection constraint. The question of whether Max-Bisection is strictly harder than Max-Cut has been a tantalizingly open question that has been studied by several works [1]}[2]}[3]}[4]}, the current best known approximation factor being \(0.8776\)  by Austrin, Benabbas and Georgiou [5]}. Another well studied problem in the framework is the SmallSetExpansion problem, due to its connection to the SSEH [6]} and its consequences. In particular, Raghavendra, Steurer and Tetali [7]} gave an algorithm, which when a graph have a set of volume \(\delta \)  with expansion \(\epsilon \) , outputs a set of volume at most \(O(\delta )\)  with expansion at most \(O(\sqrt{\epsilon \log (1/\delta )})\) , which was later shown to be tight by Raghavendra, Steurer and Tulsiani [8]}. There have been several works which also give frameworks for approximating general CSPs with global constraints. Guruswami and Sinop [9]} gave Lasserre hierarchy based algorithms for the setting when underlying label extended graph has low threshold rank. Raghavendra and Tan [4]} also propose a Lasserre hierarchy based framework for general settings. More recently, [11]} also study such CSPs using Sticky Brownian Motion based rounding algorithms.
