\documentstyle{article} \input{preamble.tex} \newtheorem{example}{Example} \newcommand{\ti}{\hbox{TIME}} \newcommand{\p}{\hbox{P}} \newcommand{\np}{\hbox{NP}} \newcommand{\conp}{\hbox{coNP}} \newcommand{\exptime}{\hbox{EXPTIME}} \newcommand{\ntime}{\hbox{NTIME}} \newcommand{\ac}{\hbox{AC}^0} \begin{document} \lecture{11}{March 17, 1998}{Daniel A. Spielman}{Abby Knickerbocker} This lecture presents a first proof that parity is not in $\ac$. Recall that $\ac$ is the class of languages decided by a logspace-uniform family of polynomial-size, constant-depth circuits. Each circuit is composed of inverters and AND and OR gates with an unbounded number of inputs. (Inverters are excluded when measuring the depth or size of a circuit.) Also recall that parity is the language of binary strings containing an odd number of ones. Parity can also be regarded as the boolean function which is 1 when an odd number of the inputs are 1. The result is originally due to Furst-Saxe-Sipser and Ajtai. We will actually prove something stronger: that a parity circuit of constant depth must have exponential size. The proof given here is similar to that given in Beigel-Reingold-Spielman, which in turn uses an idea of Smolensky. \section{Approximating the OR function} Recall: \[S_a=\sum_{i=1}^{N}\left[x_i\prod_{k=1}^{a} \left[1-\frac{1}{2}\left(1-\prod_{j=1}^{n}(1-2i_jr_j^{(k)}) \right) \right] \right] \] for the following: \begin{itemize} \item $1 \leq a \leq n+1$; \item $x_i: 1 \leq i \leq N$; \item $r_j^k:1 \leq j \leq n$; \item $n=\lceil \log N \rceil$; \item $1 \leq k \leq n+1$; \item $x_i\in\{0,1\}$; \item $r_j\in\{0,1\}^n$ \end{itemize} properties of S: \begin{enumerate} \item if $\sum x_i = 0$ then $S_a(x,r)=0$ \item if $2^{a-2} \leq \sum_{i=1}^{N}x_i \leq 2^{a-1}$ then $S_a(x,r) = 1$, with probability $\geq \frac{1} {8}$ over the choice of $r$'s. \end{enumerate} \ We want a polynomial that approximates the OR function; in order to do so, make a polynomial $V$ that is $1$ if any of the $S_a$'s are $1$. \begin{itemize} \item $OR(y_1,...,y_k)=1-\prod_{i=1}^{k}(1-y_i)$ \item $degree(OR(x_1,...,x_N))=N$ \item $V(x,r)=OR(S_1(x,r),...,S_{n+1}(x,r))=1-\prod_{a=1}^{n+1}(1-S_a(x,r))$ \end{itemize} properties of V: \begin{enumerate} \item if $\sum x_i = 0$ then $V=0$ \item if $\sum x_i \geq 0$ then $V(x,r)=1$ with probability $\geq \frac {1} {8}$ over the choice of $r$. \end{enumerate} \ In order to amplify the probability of correctness, repeat this many times, with different random variables: \[ 1-\prod_{b=1}^{m} (1-V(x,r_b))=V^m \] this polynomial $=0$ if $[OR(x_1,...,x_N)=0]$ and $=1$ with probability $\geq 1-(\frac{7}{8})^m$ if $[OR(x)=1]$. \ \begin{itemize} \item in $x_i$'s, $degree=O(m\log(N))$ \item number of random variables $=O(m\log^2(N))$ \item in random variables, $degree=O(m\log^3(N))$ \end{itemize} \section{Main Theorem and Proof Idea} $AC^0$ is the class of polynomial-sized circuits using AND, OR, and NOT gates, with constant depth and unbounded fanin. The parity function, given inputs $x_1,...,x_n$ computes $\sum x_i ~ mod ~2.$ The theorem proved in this lecture is that the parity function cannot be computed in $AC^0$. \begin{theorem} parity $\notin AC^0$. \end{theorem} \begin{proof} Take an $AC^0$ circuit, having $g=polynomial(N)$ gates (NOTE: We can just use OR and NOT gates to represent all gates in the circuit and still maintain its size). Replace all the bottom level gates with polynomials $V^m$. These have degree $\leq O(m \log (N))$. Now replace every single gate by a polynomial. Choose $m$ such that $(\frac{7}{8})^m<\frac{1}{4g}$, so $m=O(g)=g$. Then with probability $\geq \frac{3}{4}$, this circuit of polynomials produces the correct answer. We can use the same set of random variables for each polynomial. If the probability that a particular gate is wrong is $< \frac{1}{4g}$, then the probability that there exists a wrong gate is $< \frac{1}{4}$. \begin{itemize} \item degree of each polynomial $\leq O(m \log (g))$ \item degree of entire polynomial (after composition) is $O((m \log (g))^d)$ in the $x_i$'s \item degree in the random variables is $O((m \log ^3 (g))^d)$ using only $O(m \log ^2(g))$ random variables. \end{itemize} Now we have a polynomial, let's call it $p(x_1,...,x_N)$, having a degree of $O(\log(g)^{2d})$ that is supposed to compute the parity function with probability $\geq \frac{3}{4}$. As we will see, this implies that $\log(g)=\Omega(n^{\frac{1}{4d}})$. In other words, $g=2^{\Omega(n^{\frac{1}{2d}})}$, which proves the theorem. Fix the random variables so that $p$ is correct on $\geq \frac{3}{4}$ of its inputs. Perform the linear transformation : \[1 = true \rightarrow -1 \] \[0 = false \rightarrow 1 \] Now the parity function on inputs $(x_1,...,x_N)$ is computed by $\prod_{i=1}^{N}x_i$. Let $T$ be the subset of $\{-1,1\}^N$ on which $p$ computes parity. Consider the real functions over $T$. Every function over the reals on $T$ can be expressed by a polynomial in $x_1,...,x_N$. Since for all $x_i \in \{1,-1\}$, $x_i^2 = 1$, every real function on $T$ can be expressed by a polynomial in which the degree of any $x_i \leq 1$, so the total degree $\leq N$. \ Claim: Can do this in $degree \leq \frac {N}{2} + degree(p)$. \ On $T$, $p(x) = \prod_{i=1}^{N}x_i$. Any monomial of degree $> \frac {N}{2}$ can be expressed as $p(x) \cdot monomial$, where the {\it monomial} is the product of the complement of the variables in the original. This gives us a basis of real functions on $T$ of dimension \[ \sum_{i=0}^{\frac {N}{2}+degree(p)} \left( \begin{array}{c} N \\ i \end{array} \right) \] However, the dimension of this space is $= |T|$ because the standard basis has elements that are $1$ at one point of $T$ and $0$ elsewhere. So, $|T| \geq \frac{3}{4} \cdot 2^N$. If $degree(p)=o(\sqrt{N})$ then we arrive at a contradiction: \[ \sum_{i=0}^{\frac {N}{2}+degree(p)} \left( \begin{array}{c} N \\ i \end{array} \right) < (\frac{1}{2} + o(1)) \cdot 2^N,~~~~~ < |T| ~~~\Rightarrow contradiction! \] $\Rightarrow g \geq 2^{\Omega(n^\frac{1}{4d})}$, which is certainly super-polynomial. \end{proof} \end{document} %This %would yield the contradiction that %\[ %\sum_{i=0}^{\frac {N}{2}+degree(p)} \left( \begin{array}{c} N \\ i %\end{array} \right) < |T| %\]