\documentstyle{article}
\input{preamble.tex}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\Floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceiling}[1]{\lceil#1\rceil}
\newcommand{\Ceiling}[1]{\left\lceil#1\right\rceil}
\newcommand{\clique}{\mbox{CLIQUE}}
\newcommand {\fp} {\mbox{FP}}

\begin{document}
\lecture{14}{April 2, 1998}{Daniel A. Spielman}{Yu Sui}

\section*{Circuit Lower Bounds}

\subsection*{Quick review on last lecture}


\begin{definition}
Let  $\clique_k$  be the function
on n-nodes graphs that outputs 1 if and only if the input graph 
has a k-clique.
\end{definition}

 $\clique_k$ funtions are monotone functions.


\begin{definition}
 A {\bf Clean function} is an OR of at most n clique indicators
of size $< k$.
\end{definition}
%


\begin{definition}
A {\bf sunflower} is a collection of  sets $S_1,S_2,...,S_m$
such that 
$$
\forall{}i\ne j, S_i\cap{}S_j=\bigcap\limits_i{}S_i
$$
We call $\bigcap\limits_i{}S_i$ the ``core'' of the
  sunflower, and each 
  $S_j$
is called a ``petal''.
\end{definition}

\begin{theorem}[Sunflower theorem]
 Let $C$ be a collection of sets of size $\leq$ $l$, and $|C|>{}(p-1)^ll!$,
 then C contains at least one sunflower with p petals.
\end{theorem}

\begin{theorem}[Razborov]
 Any monotone circuit that computes $\clique_{\log{n}}$ has at least $n^{log{n}}$ gates.  
 \end{theorem}
 
\begin{theorem}[Alon-Boppana]
$Size(\clique_{n^{\frac{2}{3}}})>
2^{\frac{n^{\frac{1}{3}}}{\log{n}}}$
\end{theorem}

Razborov's Theorem roughly states
that no family of small monotone circuits exists for an NP-complete problem. The approach to prove is the following:  Let's say that the problem is the
$k-clique$ problem for a graph on $n$ nodes. The method is to
approximate with a $clean$ function a circuit that is said to decide
instances of the $clique$ of particular size.

The inputs to the circuit are certainly clean functions (trivially, they
are $\vee$ of one clique indicator of size 2). We proceed to approximate
the whole circuit with a clean function by replacing every $\vee$/$\wedge$ gate in the circuit with an Approx-OR/Approx-AND gate, which is defined as following:\\

\begin{definition}
For clean functions f and g: \\
$$ Approx-OR(f,g)=Weed(f \vee g) $$
$$ Approx-AND(f,g)=Weed(Trim(Cover(f \wedge g))) $$ 
Where Weed = Repeated application of Pluck \\
      Pluck = Find a sunflower among the sets/clique
  indicators, delete petals of the sunflower and replace
  with the clique indicator corresponding to the core. \\ Cover
  = Replace each minterm with  the clique indicator for the nodes
  touching edges in the minterm. \\ Trim = Discard all
  clique indicators of size $\ge k$. \\
\end{definition} 

\subsection*{Proof continued}

Define: \\
$C$ = minterms = graphs with exactly one $k$-clique \newline
$D$= complete colored graphs with $\le k-1$ colors( i.e., each
  node gets a color and there are altogether $\le k-1$
  colors, and there is edge between all pairs of nodes of
  different colors.)


For a function $a$: \\
$$ \#_C(a)=|a^{-1}(1)\cap C|  $$ 
$$ \#_D(a)=|a^{-1}(1)\cap D| $$
 
Where $\#_C(a)$ is the number of members of C that are accepted by $a$ \\
$      \#_D(a)$ is the number of members of D that are accepted by $a$\\

Let $a$ be a monotone function, we have:

\begin{lemma} \ \\
a) $\#_D(Cover(a))\le \#_D(a)$ \\
b) $\#_C(Cover(a))= \#_C(a)$ \\
\end{lemma}
  
\begin{proof}:\\
a) In Cover operation, we make the AND more restrictive--it can not accept a
 graph that was not accepted previously.\\ 
b) Let T be the set of edges examined by the clique
  indicator, and 
       let S be the set of nodes touching these edges. \\
Cover(AND) accepts if every edge between nodes in S is there. 
Thus if AND accepts a clique, all the edges are there, and Cover(AND) accepts \\
\end{proof} 

Let $a$ be an OR of $i$ clique detectors, we have: \\

\begin{lemma} \ \\
a) $\#_D(Trim(a))\le \#_D(a)$   \\
b) $\#_C(Trim(a))\ge \#_C(a)-i$ \\
\end{lemma}
  
\begin{proof}:\\
a) The Trim operation removes inputs to the OR, and so
  cannot make more  graphs  accepted \\
b) Each removal of a clique detector of size $\ge k$ can
  only cause one element of C to be rejected. \\
\end{proof}

\begin{lemma} \ \\
a) $\#_C(Pluck(a))\ge \#_C(a)$ \\
b) $\#_D(Pluck(a))\le \#_D(a)+|D|*n^{-logn}$ \\
\end{lemma}
  
\begin{proof}:

(a) If a graph G in $C$ is accepted by a petal, then it is also accepted by the core. The pluck operation removes the clique indicators
corresponding to the petals of the sunflower, and adds the indicator
corresponding to the core. Thus it doesn't decrease the number of graphs accepted. \\

(b)  Let's say that the sunflower being plucked has petals
$Z_1$...,$Z_i$,..$Z_p$, and core $Z$. We consider the probability that a
 graph in $D$  is accepted by $pluck(a)$ but not by $a$. The only way $a$
does not accept a graph with a clique on the vertices in the core of
the sunflower is if in each petal of the sunflower there are at least 2
nodes of the same color. For $pluck(a)$ to accept the graph, the core
must have all different colors. The probability that both of
  there events happens is:

\begin{eqnarray}
\mbox{Pr}[pluck(a)(G) =1, \mbox{ while } a(G)=0]
\end{eqnarray} \vspace{-0.5in}

\begin{eqnarray}
& = & \mbox{Pr}[(\mbox{all nodes in $Z$ have different colors})
  \wedge \nonumber \\
& &
  \forall_{j}, (\exists \mbox{ two nodes of same color in
  $Z_j$})]   \\ 
& \leq & \Pr{\forall_{j},
  (\exists \mbox{two nodes of same color in $Z_j$}) | \mbox{all nodes
  in $Z$ have different colors}}
 \\ 
 &=&
\prod_{i=1}^{p} \Pr{\exists \mbox{two nodes at same color in
  $Z_j$} | \mbox{all nodes in $Z$ have different colors} } 
 \\ 
  & \leq  &
 \prod_{i=1}^p \Pr{\exists \mbox{two nodes at same color in
  $Z_j$}}.  
\end{eqnarray}



Since 
\[ \Pr{\exists \mbox{ two nodes at same color in } Z_j} =
  1-\Pr{\mbox{all nodes are colored differently in $Z_j$}}, 
\]

\[\Pr{\mbox{all nodes in $Z_j$ are colored differently }} >
  \frac{{(k-1)!}}{(k-1)^{k-1}} >
  \frac{{1}}{e^{k-1}}, 
\]
Thus 


\[\Pr{\exists \mbox{two nodes at same color in $Z_j$}} <
  1-\frac{{1}}{e^{k-1}}
\]
\[\mbox{~~~$\Rightarrow$ ~~~~} 
  \prod_{i=1}^p \Pr{\exists \mbox{two nodes at same color in
  $Z_j$}} < (1-\frac{{1}}{e^{k-1}})^p
\]
In our setting, $p=ln^3 n$, $k=lnln n$,

\[\prod_{i=1}^p \Pr{\exists\mbox{ two nodes at same color in
  $Z_j$}} < e^{-ln^2 n} = n^{-ln n}
\] 
(2) $\leq$ (3) follows from the definition of conditional
probability. (4) = (3) holds by the virtue of the fact that all petals
are independent, since if the 2 nodes have the same color (if there are
such nodes at all), then they must lie outside the core (or all the
petals will have them). The $\leq$ relation of (4) to (5) holds since
the events ($Z_i$ has 2 nodes of same color) and ($Z$ has all distinct
colors) are negatively correlated (i.e., the more likely one event, the
less likely the other).
 \end{proof}
\end{document}
