\documentclass[10pt]{article} \usepackage{amsfonts} \usepackage{amssymb, fullpage} \usepackage{epsfig} \begin{document} \input{preamble.tex} \lecture{5}{Feb 21, 2007}{Madhu Sudan}{Salman Abolfathe} %%%% body goes in here %%%% \section{Overview} \begin{itemize} \item Bounded depth circuits $=AC^0$. \item PARITY$\notin AC^0$. \item Switching lemma $DNF\rightarrow CNF$ \end{itemize} \section{Introduction} $AC^i$ is the class of languages recognized by a circuit of polynomial size and depth $O(\log ^i n)$, that can use gates $$\{\infty-AND, \infty-OR, NOT\}.$$ So for $AC^0$ circuits should have polynomial size and $O(1)$ depth. Loosely speaking, depth of a circuit shows the amount of parallel time, and size is the amount of work needed for computing. Through this lecture we assume that the circuits are organized into alternating levels of $AND$ and $OR$ gates. In fact, all $NOT$ gates can be pushed to the first level, and since here we use $\infty-AND$ and $\infty-OR$ gates instead of usual $AND$ and $OR$ gates, we can combine consecutive $AND$ and $OR$ levels. So each circuit by a constant blowup can be organized such that the first level is $NOT$ gate, and the others are alternating $AND$ and $OR$. In a such circuit, we don't care about the first level ($NOT$ gates) and say the depth is number of $AND$ and $OR$ levels. As an example the following language, for a constant $k$, is in $AC^0$ $$T_{k,n}(x_1,x_2,\dots x_n)=\left\{\begin{array}{l} 1 \textrm{ if } \sum_i x_i\geq k\\ 0 \textrm{ otherwise} \end{array}\right.$$ In fact, $T_{k,n}(x_1,x_2,\dots x_n)=\bigvee_{A}\bigwedge_{x_i\in A } x_i$, where $A$ ranges over all subsets of $\{x_1,x_2,\dots x_n \}$ of size $k$. The goal of this lecture is to show PARITY is not in $AC^0$. By PARITY we mean $$PARITY(x_1,x_2,\dots x_n)=\sum_i x_i\ (mod 2).$$ \section{Random Restriction} In the last session we studied the idea of restriction of some variables to get a bound on the size of a circuit that can compute a certain language. Here we use another version of this idea, called {\it random restriction}. Namely, if $x_1,x_2,\dots x_n$ are variables, for each $i$, with probability $q$ we don't restrict $x_i$, and restrict it as $x_i=0$ or $x_i=1$, each of which with probability $\frac{1-q}{2}$. $$x_i=\left\{\begin{array}{l} x_i \textrm{ with prob. } q\\ 0 \textrm{ with prob. } \frac{1-q}{2}\\ 1 \textrm{ with prob. } \frac{1-q}{2} \end{array}\right.$$ and we repeat it for each $i$ independently. Therefore, if we have a function $f$ that can be computed by circuit $C$, after this restriction, say $\rho(q)$, we get to the function $f\vert_\rho$ that can be computed by $C\vert_\rho$, which is hopefully is a simpler circuit. In our case, the PARITY problem, after restricting some variables we get to the same problem, i.e. PARITY over remaining variables. $$\textrm{ PARITY over}\ n\ \textrm{variables} \longrightarrow \textrm{PARITY over}\ qn\ \textrm{variables }.$$ \section{Switching Lemma} Consider a depth $2$ circuit. Then it is either a CNF or DNF formula. By random restriction idea we want to convert a DNF formula to a CNF formula. In general, if we want to write a DNF as a CNF formula we may get to an exponential one (it is because SAT is hard). But after random restriction we may get to a polynomial size one. Indeed, if $q=0$ then we get the trivial formula, and if $q=1$ we get the same function. So our goal is to find the largest possible $q$ such that after restriction $\rho(q)$, we get to a polynomial size CNF. The following lemma, called Switching lemma, is first proved by Furst, Saxe and Sipser in $1981$. \begin{lemma}\label{switch} {\rm ({\bf Switching Lemma})} Let $q=n^{-\frac{2}{3}}$, then for any DNF of polynomial size $P(n)$, and $\delta=\frac{1}{poly(n)}$, after random restriction we get to a CNF of size $C$ with probability $(1-\delta)$, where $C$ is constant. \end{lemma} Before proving Switching lemma, let's use it to prove PARITY$\notin AC^0$. \begin{theorem} \label{parity} PARITY $\notin AC^0$. \end{theorem} \begin{proof} Suppose there is formula of size $s=poly(n)$ and depth $d$ that computes PARITY$_n$. By induction we can assume there is no formula of size $poly(n)$ and depth $d-1$ that computes PARITY$_n$. Now consider the DNF formulas in the first two levels of this formula, and apply the Switching lemma on them. Since number of these formulas is at most $s$, with probability $1-s\delta$ each of DNF's will change to a CNF. Now by the same idea as before, we have two consecutive AND levels and can combine them. Therefore we get to a circuit that compute PARITY on unrestricted variables, and has size $\leq O(s)$ and depth $d-1$, which is a contradiction. For the base of induction it is not hard to see that, if a circuit of depth $2$ computes PARITY then its size is $O(2^n)$. $\hfill$ \end{proof} \section{Proof of Switching Lemma} Let $f=T_1\vee T_2\vee \dots T_m$ be a formula that solves PARITY. Call each $T_j$ a term. Suppose we restrict variables in two stages {\bf Stage 1} Restrict variable with probability $\sqrt{q}$, i.e. $$x_i=\left\{\begin{array}{l} x_i \textrm{ with prob. } \sqrt{q}\\ 0 \textrm{ with prob. } \frac{1-\sqrt{q}}{2}\\ 1 \textrm{ with prob. } \frac{1-\sqrt{q}}{2} \end{array}\right.$$ $$f \longrightarrow\ f\vert_{\rho_1}.$$ {\bf Stage 2} Restrict variables in $f\vert_{\rho_1}$ with probability $\sqrt{q}$, i.e. $$x_i=\left\{\begin{array}{l} x_i \textrm{ with prob. } \sqrt{q}\\ 0 \textrm{ with prob. } \frac{1-\sqrt{q}}{2}\\ 1 \textrm{ with prob. } \frac{1-\sqrt{q}}{2} \end{array}\right.$$ $$f\vert_{\rho_1} \longrightarrow\ f\vert_{\rho_1\cup \rho_2}.$$ {\bf Claim 1} There is a constant $c$ such that all terms of $f\vert_{\rho_1}$ are of size $\leq c$ (with high probability). Consider two cases \begin{itemize} \item $T_i$ has a {\it large} size Suppose $T_i$ consists of $k=\Omega(\log n)$ variables. Then after restriction $T_i$ is non-zero iff non of the variables restricted to $0$. Therefore $$Pr(T_i\neq 0)\leq (\frac{1-\sqrt{q}}{2})^k\leq \frac{1}{poly}.$$ \item $T_i$ has{\it small} size Suppose $T_i$ contains $k'=O(\log n)$ variables. Then the probability that at least $c$ of them remain unrestricted is $$Pr( c\ \textrm{variables\ remain\ unrestriced})\leq {k'}^c(\sqrt{q})^c\leq \big(\frac{k'}{\sqrt{q}}\big)^c\leq \frac{1}{poly}$$ \end{itemize} Therefore {\bf Claim 1} is true. {\bf Claim 2 } Each term of $f\vert_{\rho_1\cup\rho_2}$ depends on $b_c$ variables, again with high probability. Here $b_c$ is a constant depends on $c$. We prove it by induction on $c$. Consider two cases. \begin{itemize} \item There are $l=\Omega(\log n)$ terms $T_1, T_2,\dots T_l$ in $f\vert_{\rho_1}$ such that they have disjoint variables. In this case, the probability that $f\vert_{\rho_1\cup \rho_2}= 1$ is $$Pr(f\vert_{\rho_1\cup \rho_2}= 1)\geq \log n\big( \frac{1-\sqrt{q}}{2}\big)^c\rightarrow 1$$ then with high probability $f\vert_{\rho_1\cup \rho_2}= 1$. \item $T_1, T_2,\dots T_l$, where $l=O(\log n)$, are maximal disjoint terms in $f\vert_{\rho_1}$, i.e. any other term has at least one variable in $T_1, T_2,\dots T_l$. Let $H$ be set of variables in $T_1, T_2,\dots T_l$, and $Y$ be the remained variables, and assume after restriction $\rho_2$, $H$ changes to $H'$ and $Y$ to $Y'$. Since each $T_i$ has most $c$ variables (Claim 1) then $\#H\leq cl$. Therefore after the second restriction, with high probability $\#H'\leq c'$, for some constant $c'$. Now set all variables in $H$, $0$ or $1$, then $f\vert_{\rho_1\cup \rho_2\cup H'}$ depends just on $b_{c-1}$ variables. It is because we assigned either $0$ or $1$ to each variable in $T_1, T_2,\dots T_l$, and by the maximality assumption in $T_1, T_2,\dots T_l$, each of the remained terms has at most $c-1$ variables. So by the induction assumption $f\vert_{\rho_1\cup \rho_2\cup H'}$ has at most $b_{c-1}$ variables. Set $b_c=c'+2^{c'}b_{c-1}$. Then $f\vert_{\rho_1\cup\rho_2}$ depends on at most $b_c$ variables. Because there are at most $c'$ variables in $H'$, and for each of $2^{c'}$ assignments of variables in $H'$, $f\vert_{\rho_1\cup \rho_2 \cup H'}$ depends on $b_{c-1}$ variables. Note that all of these arguments are true with high probability. \end{itemize} So after two restrictions $\rho_1$ and $\rho_2$, with high probability, we get to a formula that has constant number of variables. Now use the distributive law to switch the order of AND and OR gates. Since number of variables in constant, number of gates after that is also constant. \end{document}