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:
