Notes of Mark Braverman’s talk

Poly-logarithmic independence fools bounded depth circuits

1. Boolean circuits

It is a model of computation. Use AND, NOT and OR gates only. They suffice to compute any Boolean function {F:\{ 0,1 \}^n \rightarrow\{ 0,1 \}}, but this requires exponential size circuits. We stick to polynomial size circuits, of bounded depth, i.e. the number of gates encountered from each input to output is bounded. This class is called {AC^0}. This models computation that can be performed in constant time.

Example 1 The addition of two integers is in {AC^0}, but their multiplication is not.

Theorem 1 (Furst, Saxe, Sipser 1981) Parity is not in {AC^0}.

Multiplication reduces to Parity, this is why it is not in {AC^0}.

Proof: (Uneasy). If one restricts to {0} a vast majority of inputs of a bounded depth circuit, with high probability nothing remains of the circuit (computes constant function). But parity still varies. \Box

2. {k}-wise independent distributions

Definition 2 A distribution {\mu} on {\{ 0,1 \}^n} is {k}-wise independent if its restriction to any {k} coordinates is uniform.

Example 2 Let {x_1 ,\ldots,x_{n-1}} be uniform and {x_n =\sum_i x_i } mod {2}. This is a {n-1}-wise independant distribution.

This example, confronted with Theorem 1, indicates that non local dependence should be invisible to {AC^0}.

Problem 1: What looks random to {AC^0} circuits ?

Today, we focus on a subproblem.

Problem 2: For which {k} do {k}-wise independent distributions {\mu} look random to {AC^0} circuits, i.e.

\displaystyle  \begin{array}{rcl}  \forall F\in AC^0, \quad |\mathop{\mathbb E}_{\mu}(F)-\mathop{\mathbb E}_{U}(F)|<\epsilon ? \end{array}

The parameters of the problem are {n=} number of inputs, {m=} size of circuit, {d=} depth of circuit, {\epsilon=} error, {k=} degree of independence. We should not expect {k\leq \log n}. Indeed, our circuits can compute every Boolean function on {\log n} variables, so are able to detect {k}-wise dependence.

A similar argument gives {k\geq (\log n)^d}, {d=depth} (indeed, Parity can be computed by a depth {d} circuit of size {2^{n^{1/d}}}).

In 1990, Linial and Nisan conjectured that {k=(\log n)^{O(1)}} is sufficient.

In 2007, Bazzi proved it for depth {2}. Simplified proof by Razborov in 2008.

Theorem 3 {k=(\log n)^{O(d^2)}} is sufficient.

Proof: Approximation by polynomials. 1. Low degree polynomials are unsensitive to partial dependence. 2. Show that if {F} is computable by a bounded depth circuit, then {F} is close to a low degree polynomial {f}.

1. If {f} is a degree {\leq k} monomial,

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_{\mu}(f)=\mathop{\mathbb E}_U (f), \end{array}

since {f} involves at most {k} variables.

2. Given {F\in AC^0}, find degree {k} polynomials {f_l}, {f_u :{\mathbb R}^n\rightarrow{\mathbb R}} such that

\displaystyle  \begin{array}{rcl}  1.&&\forall x\in\{ 0,1 \}^n ,\quad f_l (x)\leq F(x)\leq f_u (x).\\ 2.&&\mathop{\mathbb E}_U (f_u -f)<\epsilon,\quad \mathop{\mathbb E}_U (F-f_l)<\epsilon. \end{array}


\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_{\mu}(F)... \end{array}

By LP duality, the search for sandwiching polynomials is in fact equivalent to the original problem. \Box

2.1. Approximation by polynomials

Theorem 4 (Linial, Mansour, Nisan 1989) Let {F\in AC^0}. For every {t}, there is a degree {t} polynomial {\tilde{f}} such that the {L_2} distance

\displaystyle  \begin{array}{rcl}  \|F-\tilde{f}\|_{2}^2 :=\frac{1}{2^n}\sum_{x\in\{ 0,1 \}^n}|F(x)-\tilde{f}(x)|^2) \end{array}


\displaystyle  \begin{array}{rcl}  \|F-\tilde{f}\|_{2}^2 \leq 2m \,2^{-t^{1/d}/20}. \end{array}

So if {t=(\log n)^{O(d)}},

Theorem 5 (Razborov 1987, Smolensky 1987) Let {F\in AC^0}. For every {t}, there is a degree {t=(s\log n)^d} polynomial {\tilde{f}} such that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(F(x)\not\tilde{f}(x))<0.9^s \,m. \end{array}

2.2. Proof of Theorem 5

By induction on depth. Assume {F} is the AND of functions {G_1 ,\ldots,G_{\ell}} which we can approximate by {G_1 ,\ldots,G_{\ell}} Let {T_i} be a random subset of {[\ell]}, where each element is kept with probability {2^{-i}}. Let {S_1 ,\ldots,S_t} be samples, {t=s\log\ell}, with {s} of them of each size {2^{-i}}, {i=1,\ldots,\log\ell}. Let

\displaystyle  \begin{array}{rcl}  f=\prod_{i=1}^t (\sum_{j\in S_i}g_j -|S_i|+1). \end{array}

If all {G_i} are {1}, then {f=1}, Since we have a large supply of sets of each size, one of them will adjust to the size of {\{F=0\}}.

2.3. Our proof

Combining Theorems 4 and 5, get {f} such that

  1. If {F(x)=0}, then {f(x)=0}.
  2. {\|F-\tilde{f}\|_{2}^2 <\epsilon}.


\displaystyle  \begin{array}{rcl}  f_l =1-(1-f)^2 . \end{array}

Then {f_l \leq F} and {\mathop{\mathbb E}(F-f_l)=\|F-\tilde{f}\|_{2}^2 }.

The key observation is that the set of {x} where {f_l \not=F} can be computed by a bounded depth circuit. More precisely, the set of {x} where the construction in the proof of Theorem 5 fails. Its characteristic function can be approximated by a low degree polynomial.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s