Notes of Prasad Raghavendra’s lecture nr 1

Semidefinite programming, dictatorship tests and invariance principle

1. Plan

1. Semidefinite programs for CSP’s, rounding procedures
2. Invariance principle
3. Using hard instances for SDP to construct dictatorship tests

The story started with Goemans-Williamson’s SDP for MAX CUT. I will develop it into a unification of SDP and CSP. Based on the invariance principle, one can show that constructing reductions from Unique Games becomes mechanical. I will not have time to do it in full, I will merely introduce the dictatorship tests involved in the reduction.

2. Semidefinite programs for CSP’s

2.1. The case of MAX CUT

Input: a graph. Output: a cut, i.e. a partition of vertices into two parts. Maximize the number of edges crossing the cut.

Arithmetization: look for ${\{\pm 1\}}$-valued functions on vertices, ${x:i\rightarrow x_i}$. Maximize

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{ij}|x_i -x_j|^2 =\frac{1}{4n^2}\sum_{i,j}|x_i -x_j|^2 \end{array}$

subject to conditions

$\displaystyle \begin{array}{rcl} x_i^2 =1. \end{array}$

Relaxation: The Goemans-Williamson SDP relaxation amounts to maximizing ${\mathop{\mathbb E}_{ij}|v_i -v_j|^2 }$ for vectors in ${{\mathbb R}^n}$ subject to ${|v_i|^2 =1}$. This can be solved in polynomial time.

Rounding: Goemans-Williamson pick a random half-space ${H}$. For every edge ${ij}$,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_H (ij \textrm{ is cut})\geq 0.878...|v_i -v_j|^2 \end{array}$

so

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{ij,H}(\textrm{number of edges cut})\geq 0.878...SDP\geq 0.878...OPT. \end{array}$

2.2. CSP’s

A CSP ${\Lambda}$ is defined by a label set ${[q]}$ of size ${q}$, a collection of predicates, i.e. ${\{\pm 1\}}$-valued functions ${P_i}$ on ${[q]^k}$.

An instance is given by a set ${V}$ of ${[q]}$-valued variables and a probability distribution over predicates from ${\Lambda}$ applied to ${V}$.

Example 1 For MAX CUT, ${q=2}$, there is exactly one predicate for each pair ${ab}$, ${NOTEQUAL(a,b)}$

Example 2 For 3STAT, ${q=2}$, there are 8 predicates for each triple of variables ${abc}$.

2.3. SDP relaxation for CSP’s

I describe the simplest possible relaxation for CSP’s, on the example of 3SAT.

Introduce indicators of variable events ${b_{i,a}}$: ${b_{i,0}=1}$ if ${v_i =0}$, ${b_{i,0}=0}$ otherwise. ${b_{i,1}=0}$ if ${v_i =0}$, ${b_{i,1}=1}$ otherwise.

Introduce indicators of clause events ${\mu_{P,abc}}$. Let ${P=v_i \vee v_j \vee v_k}$ be a clause. Then set ${\mu_{P,abc}=1}$ iff ${(v_i ,v_j ,v_k)=(a,b,c)}$.

The objective we want to maximize is

$\displaystyle \begin{array}{rcl} \sum_{\mathrm{clauses }\,P}\sum_{abc\in\{ 0,1 \}^3}P(a,b,c)\mu_{P,abc}. \end{array}$

Let us list constraints. Observe that ${0\leq \mu_{P,abc}\leq 1}$ and

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{abc}\mu_{P,abc}=1, \end{array}$

i.e. ${\mu_{P}}$ is a probability distribution on ${\{ 0,1 \}^3}$.

Furthermore, for all ${ab}$, ${b_{i,a}b_{j,c}=1}$ iff ${v_i}$ is assigned ${a}$ and ${v_j}$ is assigned ${c}$. But

$\displaystyle \begin{array}{rcl} b_{i,a}b_{j,c}=\mu_{P,ac0}+\mu_{P,ac1}. \end{array}$

We convert the products into inner products, so we add constraints

$\displaystyle \begin{array}{rcl} \forall i,\,j,\,a,\,c,\,P,\quad b_{i,a}\cdot b_{j,c}=\mu_{P,ac0}+\mu_{P,ac1}. \end{array}$

To sum up, our SDP has variables ${\mu_{P,abc}}$ and ${b_{i,a}}$ subject to constraints

$\displaystyle \begin{array}{rcl} \forall i,\,j,\,a,\,c,\,P,\quad b_{i,a}\cdot b_{j,c}=\mu_{P,ac0}+\mu_{P,ac1}. \end{array}$

and objective

$\displaystyle \begin{array}{rcl} \sum_{\mathrm{clauses }\,P}\sum_{abc\in\{ 0,1 \}^3}P(a,b,c)\mu_{P,abc}. \end{array}$

It can be solved within ${\epsilon}$ additive error in time ${O(q^k m\,polylog(m)polylog(1/\epsilon))}$ (Arora and Kale proved it for MAX CUT, this can be easily generalized). So one can add a rather large (subexponential) number of constraints without changing the integrality gap.

2.4. Rounding

For all predicates ${P}$ which contains ${i}$ and ${j}$, sampling in ${\{ 0,1 \}^3}$ (in general, it would be ${[q]^k}$) according to distribution ${\mu_P}$ returns inner products

$\displaystyle \begin{array}{rcl} b_{i,a}\cdot b_{j,c}=\mathop{\mathbb P}_{\mu_{P}}(x_i =a \textrm{ and }x_j =c). \end{array}$

Here is some intuitive thinking that will lead us to our rounding scheme. Our current CSP is MAXCUT.

Let us measure the hardness of an instance ${G}$ by the integrality gap, i.e. the ratio

$\displaystyle \begin{array}{rcl} \frac{OPT(G)}{SDP(G)}. \end{array}$

Let ${G}$ be a graph embedded in the unit sphere of ${{\mathbb R}^n}$. Its SDP value is the averaged length of edges. Let ${G'=G\cup G}$ be the union of ${G}$ and a rotated copy of ${G}$, . Then ${SDP(G')=SDP(G)}$, whereas ${OPT(G')\geq OPT(G)}$. So hardness can only go up. So we can think of producing a hard instance by taking the union of “all” rotated copies of ${G}$, making it very symmetric. This ideal graph, let us call it the “symmetric graph constructed from ${G}$”, ${H_G}$, has vertex set the whole unit sphere and it determined by a distribution on ${[0,2]}$, giving the weight to be put on all pairs of points on the sphere at a given distance between ${0}$ and ${2}$.

Assume the problem of determining a maximum cut ${S}$ for the symmetric graph ${H_G}$ is solved. Pick a random rotation of ${G}$, intersect it with ${S}$, this provides us with a cut of ${G}$. Then

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}(\textrm{fraction of edges cut})=OPT(H_G). \end{array}$

In other words, on an instance ${G}$ with SDP value ${SDP(G)}$, the scheme outputs a cut of value ${OPT(H_G)}$.

There is a harmless computational issue : the cut ${S}$ might have a complicated description. An approximate description (in terms of spherical harmonics, for instance) is good enough.

2.5. Integrality gap

Claim: This rounding procedure achieves the integrality gap of the chosen SDP.

Indeed, by construction, ${SDP(H_G)=SDP(G)}$ and ${OPT(H_G)\geq OPT(G)}$ on apriori grounds. Thus the integrality gap is ${\leq \frac{OPT(H_G)}{OPT(G)}}$, which is achieved by the rounding procedure.

2.6. Rounding procedure (2)

There is a simpler way to perform this whole process. Given an graph ${G}$ embedded in the unit sphere, randomly project it to a ${d}$-dimensional subspace, ${d}$ a constant related to the wanted precision ${\delta}$ for approximation (typically, ${d=polylog(1/\delta)}$). Let ${\Phi}$ denote the random projection operator, rescaled by ${\sqrt{n/d}}$.

Lemma 1 For two vectors ${v_1}$, ${v_2 \in{\mathbb R}^n}$,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(|\Phi(v_1)\cdot v_2 - v_1 \cdot v_2|>\frac{t}{\sqrt{d}})\leq \frac{1}{t^2}. \end{array}$

Proof: Concentration. $\Box$

It follows that for all but ${\epsilon}$-fraction of edges of ${G}$, the distances are ${\epsilon}$-preserved by the projection (up to rescaling). Pick an ${\epsilon}$-net ${N}$ on the ${d-1}$-dimensional sphere (i.e. every point of ${S^{d-1}}$ is a distance ${<\epsilon}$ of ${N}$). Moving projections of vertices of ${G}$ a little bit, we get a (weighted) graph structure on vertex set ${N}$, denoted by ${G/\Phi}$, which may have much less vertices than ${G}$ had. And it may have multi-edges. Nevertheless, a cut of ${G/\Phi}$ lifts to a cut of ${G}$, showing that

$\displaystyle \begin{array}{rcl} OPT(G/\Phi)\leq OPT(G). \end{array}$

On the other hand, ${SDP(G/\Phi)}$ is close to ${SDP(G)}$. Indeed, with a small fraction of errors, the inner products in ${G/\Phi}$ are close to those in ${G}$.

Since ${G/\Phi}$ has bounded vertex size, one can solve for MAX CUT by brute force for it, and lift the optimal cut to ${G}$. Again, this rounding procedure achieves the integrality gap.

2.7. Generalization

What did we use that was special to MAX CUT ? For a more general SDP, in the projection space, the constraints are only approximately satisfied. This is a technical point, we solve it by modifying the SDP relaxation: we add more constraints, like one triangle inequality constraint

$\displaystyle \begin{array}{rcl} |v_i -v_j|^{2}+|v_j -v_k|^{2}\geq |v_i -v_k|^{2}, \end{array}$

for every triple of variables occurring in the same clause.

Suppose an input ${I}$ for the SDP is given (it is a collection of inner products), which is not feasible but ${\epsilon}$-close to the feasibility region. Suppose that all triangle inequalities are satisfied within ${\epsilon}$. Move the input towards the center of the feasible region, moving a distance ${O(\epsilon)}$. Then new input ${I'}$ has ${SDP(I')}$ ${\epsilon}$-close to ${SDP(I)}$. Triangle inequalities help to show this. Indeed, the center is ${\mathop{\mathbb E}}$ of the unform distribution over all integral (i.e. ${\{\pm 1\}}$-valued) feasible inputs….