\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}