\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\lecture{5}{Feb 18, 2009}{Madhu Sudan}{Yang Cai}
%%%% body goes in here %%%%
\section{Overview}
\begin{itemize}
\item $PARITY\notin AC^0$.
\item Random Restriction
\item Switching Lemma $DNF\to CNF$
\end{itemize}
\section{Introduction}
We first introduce two sets of classes.
\begin{itemize}
\item $AC^k$: Class of functions computable by
polynomial size and $O((\log n)^k)$ depth circuits over \\$\{\infty-AND,
\infty-OR, NOT\}$ gates.
\item $NC^k$: Class of functions computable by
polynomial size and $O((\log n)^k)$ depth circuits over \\$\{2-AND,
2-OR, NOT\}$ gates.
\end{itemize}
We know that for any $k$, $AC^k\subseteq NC^{k+1}\subseteq AC^{k+1}$,
so $\bigcup_k AC^k=\bigcup_k NC^k $.
Through this lecture, we assume all circuits in $AC^k$ are organized
to have alternating levels of $AND$ and $OR$ gates. Because all $NOT$
gates can be moved to the first level, and since the $AND$ and $OR$
gates have infinite fan-in, we can combine any consecutive $AND$ or
$OR$ levels. So we can consider the depth as the number of
$AND$ and $OR$ levels.
The goal of this lecture is to prove the following theorem
$PARITY\notin AC^0$. By $PARITY$ we mean
$$PARITY(x_1,x_2,\ldots, x_n)=\sum_i x_i\ (mod\ 2).$$
\begin{theorem} \label{thm1}
[Furst, Saxe, Sipser; Ajtai; Yao; H\"{a}stad; Razborov;
Razborov-Smolensky]\center $PARITY \notin AC^0$.
\end{theorem}
\section{Random Restriction}
If $x_1,x_2,\ldots,x_n$ are variables, a random restriction on them is
to randomly set values for most of the variables. Formally, we say a
random restriction $\rho$ with parameter $p$, if for every $i$, we
leave $x_i$ unset with probability $p$, restrict it as $x_i=0$ or $x_i=1$
with equal probability $\frac{1-p}{2}$.
$$x_i=\left\{\begin{array}{l}
0 \textrm{ with prob. } \frac{1-p}{2}\\
x_i \textrm{ with prob. } p\\
1 \textrm{ with prob. } \frac{1-p}{2}
\end{array}\right.$$
If a function $f$ has $n$ variables, after this restriction, we get
the function $f|_\rho$ with about $pn$ variables. Then
$$PARITY\mid_\rho(x_1,x_2,\ldots,x_n)=PARITY(x_{i_1},x_{i_2},\ldots,x_{i_t})(\oplus
1)\ (t\approx pn)$$
\section{Switching Lemma}
\begin{lemma}
(Switching Lemma) Let $F$ be a DNF formula on $n$ variables with size
$S\leq n^{c_1}$. Let $\rho$ be a random restriction with
$p=\frac{1}{\sqrt n}$,
$$\Pr[F\mid_\rho\ depends\ on \geq C\ variables]\leq
\frac{1}{n^{2c_1}}$$ $C$ is a constant decided by $c_1$.
\end{lemma}
We will first use Switching Lemma to prove $PARITY\notin AC^{0}$, then
prove the Switching Lemma. Notice that we can always set the circuit's bottom $2$
levels to be DNF's, because if it's a CNF, we can just negate the
circuit.\\\\
\textbf{Theorem~\ref{thm1}}
$PARITY \notin AC^0$
\\
\begin{proof}
We prove this by induction. The base of induction is not hard to see
that, if a circuit of depth $2$ computes $PARITY$ then its size is
$O(2^n)$.
If for every $c$ and depth $d$, no depth $d$ circuit of size $S=n^c$
computes $PARITY$. Now we prove this is also true for $d+1$.
Say $G$ is a circuit with depth $d+1$ and size $n^{c_1}$ that computes
$PARITY(x_1,x_2,\ldots,x_n)$.
Hit $G$ with random restriction $\rho$ with parameter
$p=\frac{1}{\sqrt n}$. We know the following:(a) According to Chernoff bound, we know with probability
$(1-2^{-\sqrt n})$, there are at least $\frac{pn}{2}=\frac{\sqrt
n}{2}$ variables are unset. (b) According to Switching Lemma, for every DNF formula, it depends on
only $C$ variables with probability $1-\frac{1}{S^2}$. (c) Since there
are at most $S$ DNF formula at the bottom, all depth $2$ gates depend
on $\leq C$ variables with probabilty $1-\frac{1}{S}$. When all depth
$2$ gates depend on $\leq C$ variables, we can replace the bottom
levels by CNF of size $2^C$, then $G$ becomes $\widetilde
G$. $\widetilde G$ computes PARITY of $\frac{\sqrt n}{2}$ unrestricted
variables in a circuit with depth $d$ and
size $n^{c_1}2^C=poly(\frac{\sqrt n}{2})$. Contradiction to the
induction hypothesis.
\end{proof}
\section{Proof of Switching Lemma}
Let the DNF $F=T_1\lor T_2\lor \ldots \lor T_m$. We restrict variables in two stages
{\bf Stage 1}
Restrict variable with probability $\sqrt{p}$, i.e.
$$x_i=\left\{\begin{array}{l}
0 \textrm{ with prob. } \frac{1-\sqrt{p}}{2}\\
x_i \textrm{ with prob. } \sqrt{p}\\
1 \textrm{ with prob. } \frac{1-\sqrt{p}}{2}
\end{array}\right.$$
$$f \longrightarrow\ f\vert_{\rho_1}.$$
{\bf Stage 2}
Restrict variables in $f\vert_{\rho_1}$ with probability
$\sqrt{p}$, i.e.
$$x_i=\left\{\begin{array}{l}
0 \textrm{ with prob. } \frac{1-\sqrt{p}}{2}\\
x_i \textrm{ with prob. } \sqrt{p}\\
1 \textrm{ with prob. } \frac{1-\sqrt{p}}{2}
\end{array}\right.$$
$$f\vert_{\rho_1} \longrightarrow\ f\vert_{\rho_1\cup \rho_2}.$$
{\bf Stage 1}
\begin{itemize}
\item {\bf Case 1}: Terms with fan-in $\geq$ $4\log S$ $$\Pr[Any\ Term\ with\ fan-in\geq 4\log S \neq 0]\leq (\frac{1+\sqrt{p}}{2})^{4\log
S}\leq (\frac{2}{3})^{4\log S}\leq \frac{1}{S^3}$$
Therefore, $$\Pr[\exists\ Term\ with\ fan-in\geq 4\log S\ doesn't\
become\ 0]\leq \frac{1}{S^2}$$
\item {\bf Case 2}: Terms with fan-in$\leq 4\log S$
$$\Pr[T_i\ depends\ on\ c_0\ variables]\leq(4\log
S)^{c_0}(\sqrt{p})^{c_0}\leq \frac{1}{S^3}$$ Therefore,
$$\Pr[\exists\ Term\ with\ fan-in\leq 4\log S,\ depends\ on\geq c_0\
variables]\leq \frac{1}{S^2}$$.
$c_0$ is a constant depend on $c_1$, so now the DNF is a $c_0$-DNF.
\end{itemize}
{\bf Stage 2}
\begin{itemize}
\item {\bf Case 1}: $\exists$ many disjoint Term
$T_1,T_2,\ldots,T_l$, $l\geq 3^{c_0}4\log S$.
$$\Pr[T_i=1]\geq (\frac{1}{3})^{c_0}$$
$$\Pr[T_i\neq 1]\leq (1-\frac{1}{3})^{c_0}$$
$$\Pr[\exists\ T_i=1]\geq
1-((1-\frac{1}{3})^{c_0})^l=1-2^{-l/3^{c_0}}\geq 1-\frac{1}{S^2}$$
\item {\bf Case 2}: The max number of disjoint $T_i$'s $\leq$ $4\log
S$
{\bf Claim}: $\exists$ set $H$ with $4c_03^{c_0}\log S$ variables,
s.t. $\forall i$ $H\cap T_i\neq \emptyset$.\\
\begin{proof}
Select disjoint $T_i$'s greedily. When stop, variables in $H$ hit all
$T_i$'s
\end{proof}
\begin{itemize}
\item {\bf Part a}: First restrict variables of $H$; As in Case 2 of
Stage 1, we can find a constant $b$, s.t. the number of unset
variables in $H\leq b$.
\item {\bf Part b}: Now we restrict variables not in $H$. And we use
induction on $c_0$.\\
Induction hypothesis: Any $(c_0-1)$-DNF under random restriction
depends on only $C'$ variables with high probability, $C'$ is a constant.
Now we want to prove that $c_0$-DNF under random restriction also only
depends on constant many variables with high probability.
{\bf Claim}: With high probability $c_0$-DNF only depends on $C\leq
b+2^bC'$ variables.\\
\begin{proof}
After restricting variables in $H$, enumerate all possible assignments
of the $b$ unset variables. After assignning values to these
variables, the $c_0$-DNF becomes a $(c_0-1)$-DNF. According to the
induction hypothesis, we know this depends on $C'$ variables under
restriction. So the $c_0$-DNF depends on at most $b+2^{b}C'$ variables.
\end{proof}
\end{itemize}
\end{itemize}
\end{document}