Here are Prasad Raghavendra‘s notes on one of two guest lectures he gave for CSE 599S. Prasad will be a faculty member at Georgia Tech after he finishes his postdoc at MSR New England.
In yet another excursion in to applications of discrete harmonic analysis, we will now see an application of the invariance principle, to hardness of approximation. We will complement this discussion with the proof of the invariance principle in the next lecture.
1. Invariance Principle
In its simplest form, the central limit theorem asserts the following: “As increases, the sum of independent bernoulli random variables ( random variables) has approximately the same distribution as the sum of independent normal (Gaussian with mean and variance ) random variables”
Alternatively, as increases, the value of the polynomial has approximately the same distribution whether the random variables are i.i.d Bernoulli random variables or i.i.d normal random variables. More generally, the distribution of is the approximately the same as long as the random variables are independent with mean , variance and satisfy certain mild regularity assumptions.
A phenomenon of this nature where the distribution of a function of random variables, depends solely on a small number of their moments is referred to as invariance.
A natural approach to generalize of the above stated central limit theorem, is to replace the “sum” () by other multivariate polynomials. As we will see in the next lecture, the invariance principle indeed holds for low degree multilinear polynomials that are not influenced heavily by any single coordinate. Formally, define the influence of a coordinate on a polynomial as follows:
Definition 1 For a multilinear polynomial define the influence of the coordinate as follows:
Here denotes the variance of over random choice of .
The invariance principle for low degree polynomials was first shown by Rotar in 1979. More recently, invariance principles for low degree polynomials were shown in different settings in the work of Mossel-O’Donnell-Olekszciewicz and Chatterjee. The former of the two works also showed the Majority is Stablest conjecture, and has been influential in introducing the powerful tool of invariance to hardness of approximation.
Here we state a special case of the invariance principle tailored to the application at hand. To this end, let us first define a rounding function as follows:
Theorem 2 (Invariance Principle [Mossel-ODonnell-Oleszkiewicz]) Let and be sets of Bernoulli and Gaussian random variables respectively. Furthermore, let
and . Let denote independent copies of the random variables and .
Let be a multilinear polynomial given by , and let . If for all , then the following statements hold:
- For every function which is thrice differentiable with all its partial derivatives up to order bounded uniformly by ,
- Define the function as Then, we have
2. Dictatorship Testing
A boolean function on bits is a dictator or a long code if for some . Given the truth table of a function , a dictatorship test is a randomized procedure that queries a few locations (say ) in the truth table of , and tests a predicate on the values it queried. If the queried values satisfy the predicate , the test outputs ACCEPT else it outputs REJECT. The goal of the test is to determine if is a dictator or is far from being a dictator. The main parameters of interest in a dictatorship test are :
- Completeness Every dictator function is accepted with probability at least .
- Soundness Any function which is far from every dictator is accepted with probability at most .
- Number of queries made, and the predicate used by the test.
2.1. Motivation
The motivation for the problem of dictatorship testing arises from hardness of approximation and PCP constructions. To show that an optimization problem is -hard to approximate, one constructs a reduction from a well-known -hard problem such as Label Cover to . Given an instance of the Label Cover problem, a hardness reduction produces an instance of the problem . The instance has a large optimum value if and only if has a high optimum. Dictatorship tests serve as “gadgets” that encode solutions to the Label Cover, as solutions to the problem . In fact, constructing an appropriate dictatorship test almost always translates in to a corresponding hardness result based on the Unique Games Conjecture.
Dictatorship tests or long code tests as they are also referred to, were originally conceived purely from the insight of error correcting codes. Let us suppose we are to encode a message that could take one of different values . The long code encoding of the message is a bit string of length , consisting of the truth table of the function . This encoding is maximally redundant in that any binary encoding with more than bits would contain bits that are identical for all messages. Intuitively, greater the redundancy in the encoding, the easier it is to perform the reduction.
While long code tests/dictatorship tests were originally conceived from a coding theoretic perspective, somewhat surprisingly these objects are intimately connected to semidefinite programs. This connection between semidefinite programs and dictatorship tests is the subject of today’s lecture. In particular, we will see a black-box reduction from SDP integrality gaps for Max Cut to dictatorship tests that can be used to show hardness of approximating Max Cut.
2.2. The case of Max Cut
The nature of dictatorship test needed for a hardness reduction varies with the specific problem one is trying to show is hard. To keep things concrete and simple, we will restrict our attention to the Max Cut problem.
A dictatorship test for the Max Cut problem consists of a graph on the set of vertices . By convention, the graph is a weighted graph where the edge weights form a probability distribution (sum up to ). We will write to denote an edge sampled from the graph (here ).
A cut of the graph can be thought of as a boolean function . For a boolean function , let denote the value of the cut. The value of a cut is given by
It is useful to define , for non-boolean functions that take values in the interval . To this end, we will interpret a value as a random variable that takes values. Specifically, we think of a number as the following random variable
$ latex a = -1 $ with probability and with probability $\frac{1+a}{2}$.
With this interpretation, the natural definition of is as follows:
Indeed, the above expression is equal to the expected value of the cut obtained by randomly rounding the values of the function to as described in Equation 2.
The dictator cuts are given by the functions for some . The of the test is the minimum value of a dictator cut, i.e.,
The soundness of the dictatorship test is the value of cuts that are far from every dictator. We will formalize the notion of being far from every dictator is formalized using influences as follows: