\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf Computational Complexity II} \hfill Course Instructor: #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\em #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe:
    #4}{#1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}

%my custom commands
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\ltwo}[1]{\left\Vert #1 \right\Vert_2}
\newcommand{\lone}[1]{\left| #1 \right|_1}
\newcommand{\linf}[1]{\left| #1 \right|_{\infty}}
\newcommand{\innerp}[1]{\langle #1 \rangle}
\newcommand{\blah}{x\perp u,\norm{x}=1}
\newtheorem{subclaim}[theorem]{Subclaim}
\newcommand{\z}{\textcircled{z}}
\newcommand{\parn}[1]{\left( #1 \right)}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\f}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\parl}{\parallel}
\newcommand{\md}[1]{\left|#1\right|}
\newcommand{\ldju[2]}{\bigcup_{#1}^{#2}\hspace{-9mm\cdot}\hspace{7mm}}

\begin{document}

\lecture{Monotone Circuit Lower Bounds}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}

\section{Motivation}

The holy grail for computer science has been trying to somehow show
that $P\neq NP$. And another problem that is equally intriguing is to
show that $NP \nsubseteq P/poly$, trying to find circuit (over
$\wedge, \vee, \neg$) lower bounds for problems in $NP$. 

But suppose we were able to drop the $\neg$ gate from the basis, we
would be able to compute only monotone functions, but can we show some
monotone circuit lower bounds for some hard problem in $NP$? In this
lecture we shall see that the $CLIQUE$ function requires
super-polynomial sized monotone circuits. 

\section{Preliminaries}

\begin{definition}
A boolean function $f$ is said to be a monotone boolean function if
$x \leq y \implies f(x)\leq f(y)$ where $x\leq y$ is by the bit-wise
partial order on strings. 

A circuit is said to be monotone if it consists of only $\vee$ and
$\wedge$ gates. 
\end{definition}

\begin{claim}
A boolean function is monotone if and only if it can be computed by a
monotone circuit
\end{claim}
\begin{proof}
One direction is clear, if a function can be evaluated by a monotone
circuit, it has to be monotone. The other direction as well is fairly
obvious. 

Clearly $f(O^n) = 0$ and $f(1^n) = 1$ (otherwise it has to be a
constant function, which has a trivial monotone circuit). Hence on
every path from $O^n$ to $1^n$ on the boolean hypercube, take the
first string $x$ such that $f(x)=1$. We now just need to have an
$\wedge$ gate with all the $1$ positions of $x$ as input, and this has
to be $\vee$-ed over the $x$ on every path. 
\end{proof}

\begin{definition}
$$CLIQUE_{k,n} = \{(x_1, \cdots, x_{\binom{n}{2}})|\text{the graph induced by them
  has a $k$ clique}\}$$
\end{definition}

\begin{theorem}[Razbarov]
$CLIQUE_{k,n}$ requires monotone circuits of size $O(n^{\sqrt{k}})$ for
$k\leq n^{\frac{1}{4}}$
\end{theorem}

This could have been an attack on the $NP\nsubseteq P/poly$ problem if the
monotone complexity and actual complexity of any function was
polynomially related. But unfortunately this isn't true for general
functions, one could tweak the perfect matching problem to have a
problem in $P$ to have exponential monotone circuit complexity. 

However these are true for the so called ``Slice Problems'' where the
functional value is defined by a singe slice on the hyper cube. That
is, there exists a $k$ such that for any string with weight more than
$k$ has $1$ as the output, and any string with weight less than $k$
has $0$ as the output.\\

The proof of Razborov's theorem will be achieved by approximating
circuits by ``clique indicators'', and showing that the approximated
circuit will have to make a lot of errors and also that every gate as
such makes small errors (thereby meaning that there should be a lot of
gates that collectively make a lot of error).

\section{Proof of Razborov' Theorem}

\begin{definition} A clique indicator $I_X$ is a simple circuit such
  that $I_X$ is $1$ on graphs that have the subset $X\subseteq [n]$ as
  a clique. 

  A $(m,l)$ approximator is $\vee_{i=1}^r I_{X_i}$ such that
  $|X_i|\leq l$ for every $i$ and that $r\leq m$, (i.e) it is the OR
  of at most $m$ clique indicators each of whose size is bounded by
  $l$. 
\end{definition}

We shall approximate the circuit for $CLIQUE_{k,n}$ with $(m,l)$
indicators and measure the errors on specific types of instances:
\begin{itemize}
\item Positive Tests: Graphs on $n$ vertices with just a
  $k$-clique. There are $\binom{n}{k}$ such graphs. 
\item Negative tests: $(k-1)$ colourable graphs or $(k-1)$-partite
  graphs. If these are counted with the colouring, then there are
  $(k-1)^n$ of them. 
\end{itemize}

\subsection{Building the Approximate Circuit}

The circuit shall be built bottom up, each input $x_i$ is already a
clique indicator so there is nothing to be done there. 

Suppose at some internal node of the circuit, say an $\vee$ gate,
has two inputs $A$ and $B$ whose approximators have already been
defined. 
\begin{eqnarray*}
A = \bigvee_{i=1}^r I_{X_i}, & |X_i| \leq l, r\leq m\\
B = \bigvee_{j=1}^s I_{Y_j}, & |Y_j| \leq l, s\leq m\\
\end{eqnarray*}

We could approximate this $\vee$ gate by just $A \vee B$ but that
could potentially give us a $(l,2m)$ approximator, while want to stay
at $(l,m)$. The following lemma by Erd\"{o}s and Rado comes to our
rescue. 

\begin{lemma}[Sunflower Lemma] Suppose $\mathfrak{F}\subseteq 2^{[n]}$
  such that for all $S\in \mathfrak{F}, |S| \leq l$. Then if
  $|\mathfrak{F}| > (p-1)^l\cdot  l!$, then there exists a
  ``$p$-petalled sunflower'', that is, there exists $Z_1, \cdots Z_p
  \in \mathfrak{F}$ such that $Z_i \cap Z_j = Z$ for all $i\neq j$.
\end{lemma}
\begin{proof}
The proof will just be an induction on $l$. 

When $l=1$, then the core is the null set and we have $p$ disjoint
sets as the $p$ petals. 

As for the inductive step, pick a maximal disjoint collection of
subsets from $\mathfrak{F}$ say $Z_1, \cdots, Z_m$. If $m>p$ there is
nothing to be done since we already have a $p$-petalled sunflower with
an empty core. 

The other case is when $m<p$. Let $Z = \bigcup Z_i$, and by maximality
of the collection of sets, every set in $\mathfrak{F}$ must intersect
with $Z$ and $|Z| \leq m\cdot l \leq (p-1)\cdot l$. Hence an element
of $Z$ is contained on an average in $\frac{|\mathfrak{F}|}{|Z|} >
\frac{(p-1)^l\cdot l!}{(p-1)\cdot l} = (p-1)^{l-1}\cdot (l-1)!$ many
sets of $\mathfrak{F}$, and hence there exists an element $x\in Z$ such
that it is contained in more than $(p-1)^{l-1}\cdot (l-1)!$ sets of
$\mathfrak{F}$. Now consider the collection of those sets that contain
$x$ and remove $x$ from it. By induction you have a sunflower of $p$
petals, put back $x$ into the core and we have got the required
sunflower
\end{proof}

We shall have $\mathfrak{F} = \{X_1, X_2, \cdots, X_r, Y_1, \cdots,
Y_s\}$ and choose $m$ such that $m = (p-1)^l\cdot l!$, hence if we have
more than $m$ clique indicators, we ``pluck'' the sunflower. If
$X_1, \cdots,X_p$ form the $p$-petalled sunflower, replace
all of them by the common intersection $X_1 \cap X_2$. And hence, with
every plucking, the number of clique indicators go down by $1$, repeat
this process until you have at most $m$ clique indicators. 

Thus we have approximated an $\vee$ gate, we shall call it $A \sqcup
B$. \\

Approximating an $\wedge$ gate requires a little more work. $A\wedge
B$ looks like
\begin{eqnarray*}
A\wedge B & = & \parn{\bigvee_{i=1}^r I_{X_i}}\wedge \parn{\bigvee_{j=1}^s
  I_{Y_j}}\\
 & = & \bigvee_{i=1}^r \bigvee_{j=1}^s \parn{I_{X_i} \wedge I_{Y_j}}
\end{eqnarray*}

We now have two problems, firstly $I_{X_i} \wedge I_{Y_j}$ isn't even
a clique indicator. This can be tackled by just replacing
$I_{X_i}\wedge I_{Y_j}$ by $I_{X_i \vee Y_j}$. If $|X_i + Y_j| > l$,
just drop this clique indicator. As for our second problem of having a
union of $2m$ clique indicators, apply the plucking as before to
reduce this number to $m$. 
This approximator will be denoted by $A\sqcap B$\\

The approximator of the output gate will be our approximate circuit
$C'$. 

\subsection{Approximated circuit makes lots of errors}

\begin{lemma}
Either $C'$ is $0$ on all positive tests or the number of negative
tests on which $C'$ is $1$ is at least
$$\parn{1 - \frac{\binom{l}{2}}{k-1}}(k-1)^n$$ 
\end{lemma}
\begin{proof}
The only way $C'$ is $0$ on all positive instance is when our
$A\sqcap B$ approximator throws out all clique indicators because
their sizes are greater than $l$. Hence, if it is non-zero on positive
test cases, 
$$
C' = \bigvee_{i=1}^r I_{X_i}
$$
where $0\neq r \leq m$ and $|X_i|\leq l$. Pick a negative instance at
random among the $(k-1)^n$ choices. The probability that the
approximator outputs a $1$ is clearly upper bounded by the probability
that $I_{X_1}$ outputs a $1$, which is equal to $1 - \Pr[I_{X_1} =
0]$. $I_{X_1}$ outputs a $0$ if and only if two vertices of $X_1$ lie
in the same partition of the random negative test, and this happens
with probability
$$
\frac{\binom{|X_i|}{2}}{k-1} \leq \frac{\binom{l}{2}}{k-1}
$$
Hence, the number of errors made on negative tests is lower bounded as
claimed in the lemma. 
\end{proof}


\subsection{Each gate makes few errors on positive tests}
\begin{lemma}
The number of positive tests on which $C'$ fails is at most 
$$
size(C)\cdot m^2\cdot \binom{n-l-1}{k-l-1}
$$
\end{lemma}
\begin{proof}
We shall consider the errors introduced by the approximator at a
single gate, and then apply the union bound to get the bound claimed. 

If $g = A \vee B$, then our construction for the approximator for
$g$ involves taking a simple $\vee$ (which doesn't introduce any
error) and then repeatedly plucking until we get down our number of
clique indicators. The plucking operation replaces a larger clique
indicator $I_{X_i}$ by $I_X$ with $X\subseteq X_i$ and hence will
accept only more graphs and cannot make the approximator answer a
$0$. Hence $A \sqcup B$ introduces no errors on positive tests. \\

Suppose $g = A\wedge B$, our first step was to replace $I_{X_i}\wedge
I_{Y_j}$ by $I_{X_i \cup Y_j}$. These two functions behave the same on
positive tests and hence won't introduce any errors. The second step
was to drop indicators of size greater than $l$. Dropping such clique
indicators may make the approximator err on those positive graphs that
contain a clique on these $l+1$ or more places, and there are at most
$\binom{n-l-1}{k-l-1}$ of them and there are at most $m^2$ clique
indicators, giving us the bound claimed. 
\end{proof}
\subsection{Each gate makes few errors on negative tests}
\begin{lemma}
The number of negative tests on which $C'$ fails is at most
$$
size(C)\cdot m^2 \cdot \parn{\frac{\binom{l}{2}}{k-1}}^p \cdot (k-1)^n
$$
\end{lemma}
\begin{proof}
Again, we shall analyse the errors introduced at each gate. 

If $g = A \vee B$ then the errors have to be introduced at the
plucking operations. We need to consider the negative tests that are
accepted after plucking which were rejected before. Pick the
$(k-1)$-partition randomly among the $(k-1)^n$ partitions, and let $G$
be the resulting negative graph. For any sunflower $Z_1, \cdots, Z_p$,
we estimate the probability that $I_{Z_i}$ outputs $0$ on $G$ whereas
$I_Z$ outputs a $1$. 

\begin{eqnarray*}
Pr\left[I_{Z} = 1 \wedge \parn{\bigvee I_{Z_i} = 0} \right] & \leq & \Pr\left[\bigvee
  I_{Z_i} =0|I_Z = 1 \right]\\
 & = & \prod_{i=1}^p \Pr\left[I_{Z_i}=0 | I_Z = 1\right]\\
 & \leq & \prod \Pr[I_{Z_i}=0]\\
 & \leq & \parn{\frac{\binom{l}{2}}{k-1}}^p
\end{eqnarray*}
The first line follows from the definition of conditional probability.
The second line is true because the petals of the sunflower are
disjoint and hence the probabilities are independent. The third is
true because ``$Z_i$ is not a clique'' is less likely to happen given
the fact that $Z$ is a clique\footnote{if this intuition is not clear,
  the reader should work out the easy details}. The fourth line
follows because $Z_i$ is not a clique if and only if two vertices of
it fall in the same partition. 

And since there are at most $m$ plucks, the desired bound follows
if $g$ is an $\vee$ gate. \\

Suppose $g = A \wedge B$, the step where we replace $I_{X_i} \wedge
I_{Y_j}$ by $I_{X_i \vee Y_j}$ does not cause any graph that was
rejected before to be accepted now. The step of dropping large clique
indicators also doesn't not cause additional negative graphs to be
accepted. It's again the plucking process that creates the trouble,
and that goes through the same analysis as given for the $\vee$
gate. And since there are at most $m^2$ packing's, the claimed bound
is obtained. 
\end{proof}

\subsection{Choosing parameters}

If we choose $l = \floor{\sqrt{k}}$, $p = \ceil{\sqrt{k}\log n}$ and
$m = (p-1)^l\cdot l!$, the lemmas would then show that
$$
size(C) =  n^{\Omega(\sqrt{k})}
$$
The details are left to the reader.


\end{document}
