  This work is concerned with approximating constraint satisfaction problems
(CSPs) with an additional global cardinality constraints. For example, \maxcut
is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find
a cut $S \cup \bar S = V$ that maximizes the numberof crossing edges,
$|E(S,\bar S)|$. The \maxbisection problem is a variant of \maxcut with an
additional global constraint that each side of the cut has exactly half the
vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like
\minbisection and approximating Graph Expansion can be formulated as CSPs with
global constraints.
  In this work, we formulate a general approach towards approximating CSPs with
global constraints using SDP hierarchies. To demonstrate the approach we
present the following results:
  Using the Lasserre hierarchy, we present an algorithm that runs in time
$O(n^{poly(1/\epsilon)})$ that given an instance of \maxbisection with value
$1-\epsilon$, finds a bisection with value $1-O(\sqrt{\epsilon})$. This
approximation is near-optimal (up to constant factors in $O()$) under the
Unique Games Conjecture.
  By a computer-assisted proof, we show that the same algorithm also achieves a
0.85-approximation for \maxbisection, improving on the previous bound of 0.70
(note that it is \uniquegames hard to approximate better than a 0.878 factor).
The same algorithm also yields a 0.92-approximation for \maxtwosat with
cardinality constraints.
  For every CSP with a global cardinality constraints, we present a generic
conversion from integrality gap instances for the Lasserre hierarchy to a {\it
dictatorship test} whose soundness is at most integrality gap. Dictatorship
testing gadgets are central to hardness results for CSPs, and a generic
conversion of the above nature lies at the core of the tight Unique Games based
hardness result for CSPs. \cite{Raghavendra08}
