Semidefinite programming, dictatorship tests and invariance principle
- Semidefinite programs for CSP’s, rounding procedures
- Invariance principle
- 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 -valued functions on vertices, . Maximize
subject to conditions
Relaxation: The Goemans-Williamson SDP relaxation amounts to maximizing for vectors in subject to . This can be solved in polynomial time.
Rounding: Goemans-Williamson pick a random half-space . For every edge ,
A CSP is defined by a label set of size , a collection of predicates, i.e. -valued functions on .
An instance is given by a set of -valued variables and a probability distribution over predicates from applied to .
Example 1 For MAX CUT, , there is exactly one predicate for each pair ,
Example 2 For 3STAT, , there are 8 predicates for each triple of variables .
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 : if , otherwise. if , otherwise.
Introduce indicators of clause events . Let be a clause. Then set iff .
The objective we want to maximize is
Let us list constraints. Observe that and
i.e. is a probability distribution on .
Furthermore, for all , iff is assigned and is assigned . But
We convert the products into inner products, so we add constraints
To sum up, our SDP has variables and subject to constraints
It can be solved within additive error in time (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.
For all predicates which contains and , sampling in (in general, it would be ) according to distribution returns inner products
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 by the integrality gap, i.e. the ratio
Let be a graph embedded in the unit sphere of . Its SDP value is the averaged length of edges. Let be the union of and a rotated copy of , . Then , whereas . So hardness can only go up. So we can think of producing a hard instance by taking the union of “all” rotated copies of , making it very symmetric. This ideal graph, let us call it the “symmetric graph constructed from ”, , has vertex set the whole unit sphere and it determined by a distribution on , giving the weight to be put on all pairs of points on the sphere at a given distance between and .
Assume the problem of determining a maximum cut for the symmetric graph is solved. Pick a random rotation of , intersect it with , this provides us with a cut of . Then
In other words, on an instance with SDP value , the scheme outputs a cut of value .
There is a harmless computational issue : the cut 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, and on apriori grounds. Thus the integrality gap is , 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 embedded in the unit sphere, randomly project it to a -dimensional subspace, a constant related to the wanted precision for approximation (typically, ). Let denote the random projection operator, rescaled by .
Lemma 1 For two vectors , ,
It follows that for all but -fraction of edges of , the distances are -preserved by the projection (up to rescaling). Pick an -net on the -dimensional sphere (i.e. every point of is a distance of ). Moving projections of vertices of a little bit, we get a (weighted) graph structure on vertex set , denoted by , which may have much less vertices than had. And it may have multi-edges. Nevertheless, a cut of lifts to a cut of , showing that
On the other hand, is close to . Indeed, with a small fraction of errors, the inner products in are close to those in .
Since has bounded vertex size, one can solve for MAX CUT by brute force for it, and lift the optimal cut to . Again, this rounding procedure achieves the integrality gap.
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
for every triple of variables occurring in the same clause.
Suppose an input for the SDP is given (it is a collection of inner products), which is not feasible but -close to the feasibility region. Suppose that all triangle inequalities are satisfied within . Move the input towards the center of the feasible region, moving a distance . Then new input has -close to . Triangle inequalities help to show this. Indeed, the center is of the unform distribution over all integral (i.e. -valued) feasible inputs….