1. Invariance principle
1.1. Some notation
The hypercube is . The Fourier-Walsh decomposition of a real function on the hypercube is
where . Parseval identity reads
The influence of the -th coordinate on a Boolean function is
where is uniformly distributed on the hypercube and has all entries but the -th.
Example 1 If is a dictator, , then , if .
If , then for all , .
For non Boolean functions, we define influence as
This has a nice Fourier expression
Lemma 1
Proof:
Equivalently, we shall consider multilinear polynomials on , i.e. functions of the form . We continue the same notation.
1.2. Central limit theorem
The invariant principle is a non linear generalization of the Central Limit Theorem. Here is a baby version.
Theorem 2 Let be independant identically distributed random variables admitting a -th moment. The distribution of their sum converges to a Gaussian distribution.
Here is our interpretation. Consider the multilinear polynomial . If we feed it with a uniform Boolean vector or a Gaussian vector , or any random vector with i.i.d. coordinates, admitting a -th moment, the resulting distributions are similar.
Our generalization replaces by an arbitrary degree multilinear polynomial. Note that the theorem cannot hold for dictators . So one must restrict to polynomials which are from dictators, namely, have uniformly low influences. We shall also need a more quantitative version, which generalizes the Berry-Esseen Theorem in the linear case.
1.3. A baby invariance principle
Reference: Ryan O’Donnell’s course on Analysis of Boolean functions.
Theorem 3 Let be a degree multilinear polynomial such that and for all , . Let be uniformly distributed on the hypercube, let be a Gaussian vector. Then the distributions of and are close in the following sense: For every function , ,
Proof: Hybridize: Replace one variable at a time. Denote by
It suffices to bound
Lemma 4
Summing up yields
Proof: of Lemma.
Write where and are multilinear polynomials not depending on . Then
where , are random variables which are independant from and . Use Taylor expansion
where remainders , . By independance and linearity, the expectations of all terms in the expansion are the same for and , since and have the same moments up to order . With , it follows that
The proof ends with the following hypercontractivity lemma. Indeed,
Lemma 5 (Bonami) For a degree multilinear polynomial ,
when inputs are independant variables, either Boolean or Gaussian.
Proof: By induction on . Write where and do not depend on . then
1.4. A more general invariance principle
We some more work, one can prove the following vector valued version of Theorem 3.
Theorem 6 Let be an -variable multilinear polynomial of degree . Let , be random variables. Assume that
- For all , . For all and , .
- For all , , ,
- For all , .
- .
For each , consider independant copies of . Denote by the random vector whose -th component is . Idem for the ‘s. Then for every smooth function ,
1.5. Smoothing
Let act on real functions on the hypercube as follows
where has independent components, each takes value with probability . In Fourier expansion,
It has a damping effect on high frequencies, this is why one can view it as a smoothing operator. Theorem 6 applies only to degree polynomials . A slight variant of it applies to for arbitrary .
2. Dictatorship tests
2.1. What it this good for ?
A dictatorship test is a gadget used in proving hardness of approximation results. It is used in reductions from Unique Games. Say we want to prove hardness of a Boolean CSP . The corresponding gadget is an instance of . So it takes variables in a hypercube , is the label size of the Unique Games instance to reduce from. An assignment to is a boolean function on the hypercube (it is huge). must distinguish dictator assignments from others, with the following guarantees.
- Completeness: Dictator assignments have value .
- Soundness: Assignments which are far from dictators (e.g. Boolean functions with low influences) have value .
From such a , one gets mechanically a UGC conditional hardness of approximation result for with threshold . See Guy Kindler’s course.
2.2. Construction of
We start from a hard instance of , and construct a corresponding instance . We shall see that completeness can be taken to be and soundness . From the SDP, we get a probability distribution on the hypercube for each predicate in . is a distribution on clauses, viewed as Boolean functions on the hypercube . It depends on a large parameter (this will be the label size of a Unique Games instance to reduce from). To sample a clause,
- Sample a clause of .
- Sample a random boolean function on the hypercube according to .
- Introduce -noise.
Example 2 For instance, for MAX CUT, instances are weighted graphs . There is one predicate per edge, so probability distributions on .
Let us continue with this example (MAX CUT). is a weighted graph with vertex set the hypercube. To sample an edge,
- Sample an edge of . Get a positive number from the SDP solution.
- Sample a random pair of points of the hypercube according to (under this distribution, the expected distance is .
- Introduce -noise.
2.3. Completeness analysis
Dictators are unaffected by noise. By symmetry, all dictators get the same value.
2.4. Soundness analysis
First ignore the noise. Let us continue with MAX CUT. The invariance principle tells that low influence cuts in the hypercube or in the sphere behave in the same way. In particular, the value of cuts in the graph are the same than in the symmetric graph in the sphere obtained by averaging rotated images of the SDP solution.
The role of the noise is to replace arbitrary degree boolean functions (cuts, in the case of MAX CUT) by , in order to apply the invariance principle.