\documentstyle[fullpage,11pt]{article}

%% MACROS
%\newtheorem{theorem}{Theorem}
\newcommand{\DS}[1]{{\LARGE{\it [DS: {#1}]}}}   %notes to Dan

%% NOTATION
\newcommand{\paren}[1]{\left({#1}\right)}
\newcommand{\Oh}[1]{O\!\paren{#1}}
\newcommand{\poly}[1]{{\em poly}\!\paren{#1}}

\newcommand{\TM}{\mbox{TM}}
\newcommand{\TIME}{\mbox{TIME}}
\newcommand{\A}{A}
\newcommand{\accept}{{\em accept}}
\newcommand{\reject}{{\em reject}}

\newcommand{\ppoly}{\mbox{$P/poly$} }
\newcommand{\cs}{\mbox{$\cal{C/S}$} }


%% FORMATTING
\newcommand{\nolineskips}{%
\setlength{\parskip}{0pt}%
\setlength{\parsep}{0pt}%
\setlength{\topsep}{0pt}%
\setlength{\partopsep}{0pt}%
\setlength{\itemsep}{0pt}}

\input{preamble.tex}

\begin{document}
\lecture{15}{April 7, 1998}{Daniel A. Spielman}{David Ratajczak}

\section{Proof of Razborov's Theorem (cont.)}

We start with a recap of the previous lecture.  Razborov's Theorem
asserts that any monotone circuit\footnote{ Circuits with only $\vee$
and $\wedge$ gates.} that computes $CLIQUE_{\log n}$ has at least
$n^{\Omega(\log n)}$ gates.  This theorem (and the more recent
Alon-Boppana theorem) establishes one of the most important circuit
lower bounds presently known: $NP$-complete problems cannot be
computed by polynomially-sized monotone circuits.

Razborov's approach is as follows: Consider the $CLIQUE_k$
problem\footnote{The decision problem of determining whether or not a
$k$ clique exists in a graph of $n$ nodes.} for a graph on $n$
nodes. We wish to approximate a circuit that decides instances of
$CLIQUE_k$ with a $clean$ function.  Recall from last time that a
$clean$ function is an $\vee$ of a set of no more than a fixed number
of {\em clique indicators}, where each clique indicator of size $l$ is
just an $\wedge$ of at most ${l \choose 2}$ inputs.

The inputs to the circuit are certainly clean functions (trivially,
they are an $\vee$ of one clique indicator of size 1). We can thus
approximate the whole circuit with a clean function by showing that if
we are given two clean functions $f$ and $g$, that $f\wedge g$ and
$f\vee g$ can both be approximated by a clean function.  Our circuit
approximation would be constructed by recursively replacing each gate
of the circuit with a clean function.  We therefore define,

\begin{description}
\item[Approximate-$\vee$ ($\sqcup$)]
For every $\vee $ in the circuit, we can replace it with $\sqcup$
which is defined as: \[(f{\sqcup}g) = weed(f{\vee}g),\]where $weed$
was defined to be: repeatedly $pluck$ sunflowers with at least
$p=(log(n))^3$ petals until at most $m=(p-1)^kk!$ clique indicators
are left.

\item[Approximate-$\wedge$ ($\sqcap$)]
For every $\wedge$ in the circuit, we replace it with $\sqcap$ defined
as: \[(f{\sqcap}g) = weed(trim(cover(f{\wedge}g))),\footnote{ Refer to
the previous lecture for definitions of the $pluck$, $trim$ and
$cover$ operations, as well as the Sunflower Theorem.}\]
\end{description}

\subsection{Proof Continued}
In the last lecture we saw that every monotone function has a
characteristic set of {\bf minterms} and {\bf maxterms}.  We found
that in the case of the $k$-clique problem.
\begin{description}
\item[minterms (C):] graphs on $n$ nodes with exactly one $k$-clique and no 
other edges.
\item[maxterms (D):] complete $k-1$ partite graph (nodes divided into 
at most $k-1$ colors, and an edge exists between any two nodes of different 
colors.)
\end{description}

We are only going to analyze the performance of the Approximate-$\vee$
and Approximate-$\wedge$ operations on these two sets, rather than on
all instances of the $k$-clique problem.  We will show that for these
two sets, a clean function will be unable to compute $k$-clique.

We also defined $\#_c(h)$ and $\#_d(h)$ to be the number of minterms
and maxterms that are accepted by a clean function $h$.  We found that
\begin{eqnarray*}
\#_c(cover(h)) & = & \#_c(h)\\
\#_d(cover(h)) & \leq & \#_d(h)\\
\#_c(trim(h)) & \geq & \#_c(h)-k\\
\#_d(trim(h)) & \leq & \#_d(h)\\
\#_c(pluck(h)) & \geq & \#_c(h)\\
\#_d(pluck(h)) & \leq & \#_d(h)+n^{-\log(n)}|D|
\end{eqnarray*}

From the definitions of $\sqcup$ and $\sqcap$ above, it is
straightforward to compute:
\begin{eqnarray}
\#_c(f\sqcup g) & \geq & \#_c(f\vee g)\\
\#_d(f\sqcup g) & \leq & \#_d(f\vee g)+2n(n^{-\log(n)})|D|\\
\#_c(f\sqcap g) & \geq & \#_c(f\wedge g)-n^2\\
\#_d(f\sqcap g) & \leq & \#_d(f\wedge g)+n^2n^{-\log(n)}|D|
\end{eqnarray}
\begin{proof}
\begin{enumerate}
\item Follows trivially from $f \sqcup g = weed(f \vee g)$.
\item During the $weed$ operation, This part follows from Lemma 2 and the fact that during the $weed$ operation we pluck the sunflower at most $2n$ times. 
\item $(f \sqcap g)=weed(trim(cover(f \wedge g)))$. This result follows.
\item We only need to worry about the weed operation here, since it is the only operation that increases $\#_d$.  We only need to pluck at most $n^2$ times after $trim(cover())$ has been applied.  The above result follows.
\end{enumerate}
\end{proof}

The main idea is that the $\sqcup$ and $\sqcap$ approximations neither
decrease the probability of accepting a maxterm by too much, nor
increase the probability of accepting minterm by too much.

\begin{lemma}\label{one}
Let $A$ be a monotone circuit with $g$ gates that computes $k$-clique,
where $k=log(log(n))$. If $A'$ is the circuit obtained by replacing all
$\wedge$'s and $\vee$'s with $\sqcap$'s and $\sqcup$'s respectively,
then we have $\#_c(A)=|C|$, $\#_d(A)=0$, and $$\#_c(A')\geq
|C|-gn^2\hbox{,  and  }\#_d(A')\leq gn^{-log(n)+2}|D|.$$
\end{lemma}
\begin{proof}
This follows from applying the inequalities listed above for each of
the $g$ gates in the circuit $A$.
\end{proof}

\begin{lemma}
If $h$ is a clean function, then either
$$\#_d(h)=|D|,\hbox{ or }\#_c(h)\leq \frac{|C|}{2}.$$
\end{lemma}

\begin{proof}
The first case occurs if $h$ is an $\vee$ of no $\wedge$'s.  This
circuit accepts all graphs and therefore $\#_d(h)=|D|$.  The second
case occurs when $h$ is an $\vee$ of at most $n$ $\wedge$'s.  For this
case we choose a $k$-clique graph at random and check whether it is
accepted by a particular $\wedge$.

The probability that a particular $\wedge$ accepts a particular
$k$-clique (chosen randomly) is certainly less than the probability
that a given edge (in the $\wedge$) is in the $k$-clique.  This
probability is just $\frac{{n-2 \choose k-2}}{{n \choose k}}$ as this
is the number of $k$-cliques that contain a given edge divided by the
total number of $k$-cliques.  We can simplify this and say that
$$\frac{{n-2\choose k-2}}{{n \choose k}}<\frac{k^2}{n^2}.$$ Since
there are at most $n$ $\wedge$ gates, then the probability that a
random $k$-clique is accepted by the circuit is no greater than
$$\frac{k^2}{n^2}n=\frac{(log(log(n)))^2}{n}<\frac{1}{2}.$$ This means
the number of maxterms accepted by $h$ is less than half the total or
$\#_c(h)\leq \frac{|C|}{2}.$
\end{proof}

Combining the above two lemmas, we can see that if $A$ is a monotone
circuit with $g$ gates that computes the $k$-clique problem, then
$$g\geq min\left(\frac{|C|}{2n^2},n^{log(n)-2}\right)=min\left(\frac{{n
\choose k}}{2n^2},n^{log(n)-2}\right)=min\left(\frac{{n \choose
log(log(n))}}{2n^2},n^{log(n)-2}\right).$$ And this proves the desired
lower bound of $n^{\Omega(log(n))}$ for monotone circuits computing
$CLIQUE_{log(n)}$.

\section{The Parity Function Revisited}

We now revisit a familiar result which was established in a previous
lecture.
\begin{theorem}
{\bf (Furst, Saxe, Sipser)} The parity function cannot be computed by
constant depth, polynomial size, unbounded fan-in
circuits.\footnote{Any $NOT$ gates should only be at the input.}
\end{theorem}
We aim to reprove this result, but using techniques that were
established in the original publication of this result by Furst, Saxe,
and Sipser.  In this lecture, we will outline the proof and produce
some necessary intermediate results.

\subsection*{Proof Idea}
In this proof we will use the idea of a {\em restriction}, where we
fix some of the inputs of a circuit while leaving others variable.

We will prove the result by contradiction.  We start by letting $d$ be
the smallest depth admitting polynomial size parity circuits.  Now
suppose we have a depth $d$ circuit with alternating $\vee$'s and
$\wedge$'s at each level, and the $NOT$ gates moved to the inputs.  It
is not difficult to show that we can convert any constant depth
circuit into this form with only a factor of $2$ increase in its size.
We will assume that the bottom level gates are $\wedge$ gates.

We first apply a random restriction (chosen from a suitable
distribution) so that the gates on the bottom level have constant
fan-in.  Then we apply a second set of restrictions to this circuit to
obtain constant fan-in in all gates on the bottom two levels.
Finally, we will interchange the bottom two levels and collapse the
circuit to a constant $d-1$ depth circuit.  We will show that with
high probability, this final circuit will also compute parity.

By repeating this method and applying new restrictions, we can
collapse the circuit down to a depth $2$ circuit where the bottom
level has constant fan-in.  Lupanov originally showed that no
polynomially sized depth $2$ circuits can compute parity, so this
completes the proof.

\subsection*{Proof}
Let us begin with depth $d$ circuits $C_1$, $C_2$,\dots, where $C_n$
computes the parity of its $n$ inputs.  We will consider a random
restriction $\rho: x_1,x_2,\dots,x_n\longrightarrow \{0,1,*\}$ where
for each $i$,
\begin{eqnarray*}
Pr[\rho(x_i)=*]&=&\frac{1}{\sqrt{n}}\\
Pr[\rho(x_i)=1]&=&Pr[\rho(x_i)=0]=\frac{1-1/\sqrt{n}}{2}
\end{eqnarray*}
We wish to show that there is a non-zero probability that the
restriction $\rho$ leaves more than $\sqrt{n}/2$ inputs variable but
which bounds the fan-in of the bottom level $\wedge$ gates.

The probability that there are less than $\sqrt{n}/2$ inputs left
variable is $O(n^{-1/2})$.\footnote{Actually, you can say it is
$O(2^{-c\sqrt{n}})$ for some constant $c$, but it is not necessary.}

\begin{lemma}
Let $G$ be a bottom level $\wedge$ gate, then for all $l>0$ there is a
constant $c$ such that the probability that $G$ has fan-in greater
than $c$ after the restriction $\rho$ is less than $n^{-l}$.
\end{lemma}
This result will imply that we can choose $c$ large enough that the
probability that a random restriction does {\em not} satisfy the above
requirements approaches $0$ as $n$ increases.  We will prove this
lemma and complete the rest of the proof in the next lecture.

\begin{thebibliography}{9}
\bibitem{fss}Furst, Saxe, Sipser, {\em Parity, Circuits, and the Polynomial-Time Hierarchy}.  Mathematical Systems Theory, vol. 17, no. 1, p. 13-27.  April 1984
\end{thebibliography}
\end{document}