\documentclass[10pt]{article}
\usepackage{amsfonts,epsfig}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\newtheorem{technique}[theorem]{Technique}
\newtheorem{conjecture}[theorem]{Conjecture}
\lecture{4}{Feb 20, 2007}{Madhu Sudan}{Katherine Lai}
\section{Overview}
In this lecture, we look at some lower bounds concerning the
non-uniform forms of computation we discussed last time.
\begin{itemize}
\item Neciporuk's Theorem ($f\in P$ with BP size
$\Omega((\frac{n}{\log n})^2)$)
\item Barrington Construction of Small-Width BPs
\end{itemize}
\section{Previous Lecture}
In the previous lecture, we discussed non-uniform forms of computation
and their complexity measures.\\
\begin{tabular}{l|c|c|c|c|c}
Nonuniform computation & \# bits of advice & time & size & width &
depth\\\hline
TM with advice & x & x & & \\
Circuits & & & x & & x \\
Branching Programs (BPs) & & & x & x & \\
Formulae & & & x & & x\\
\end{tabular}
%$\log(width) \approx$ space
We try to study these forms of computation to try to see what you can
and can't solve with them, and in doing so divide up logspace and
other classes.
\section{Counting Technique}
Before we discuss Neciporuk's theorem, we define the counting
technique, which we will find useful.
\begin{technique}
Let ${\mathcal F} \subseteq \{f: \{0,1\}^n\rightarrow\{0,1\}\}$. Then
$\exists f \in {\mathcal F}$
s.t. $size(f)\geq\Omega\left(\frac{log|{\mathcal
F}|}{\log\log|{\mathcal F}|}\right)$.
\end{technique}
We can use this technique to count the number of functions circuits of
a particular size can calculate. If we have circuits with size at
most $s$, they can calculate $|{\mathcal F}|\leq2^{s\log s}$.
However, if we wanted to use only this technique to prove anything
meaningful about NP, it's never going to really work. NP is an
infinite family of functions. For this concept to make sense, we
would need to look at the first constant number of functions in NP,
and we don't get anywhere if we use counting to find one function in
NP. We will, however, see how we can get lower bounds with counting
anyway.
\section{Neciporuk's Theorem}
%$$f\in P with BP size \Omega\left(\frac{n}{\log n}\right)^2$$
With Neciporuk's Theorem, we get a lower bound on the size of BP that
calculates a function in P. First, we define the function.
\begin{definition}
Let $f:\{0,1\}^k\times \{0,1\}^{n-k}\rightarrow\{0,1\}$, with
$f_x(i)=f(i,x)$.
\end{definition}
The question at hand is, how many different $f_x$ do we get? If all
$f_x$'s are different, can we say anything about $size(f)$? We want
to find out what the smallest circuit or BP we would need for this
$f$. The key idea is if we have a circuit for $f$, we have a circuit
for $f_x$--we just hardcode $x$ into the circuit. This doesn't
increase the size of the circuit. If all $f_x$ are different, we have
$${\mathcal F}=\{f_x\} \textrm{ with } |{\mathcal F}|\geq 2^{n-k}$$
$$size(f)\geq \frac{n-k}{\log(n-k)}=\Omega\left(\frac{n}{\log
n}\right)$$
This result is unfortunately sublinear, so it doesn't tell us much
yet.
To construct ${\mathcal F}$ with a different $f_x$ for every $x$, we
do the following. We set $f(i,x) = x_i$, where $x$ is the truth table
where $x = x_1 \ldots x_{n-k}$, provided that $2^k\geq n-k$.
\subsection{A superlinear lower bound}
We want to find a superlinear lower bound, and to do this we have to
restrict ourselves to only using BPs. We also need a metric for the
size of the BP.
\begin{definition}
Let $BPSIZE_i(B)$ be the number of times the literal $x_i$ or its
complement appears in the branching program $B$.
\end{definition}
% maybe include a diagram of example of a BP
%% start node, two end nodes, outdegree of interior nodes = 2 with a
%% literal and its complement.
%% $BPSIZE_{1}$(of his example) = 2
%% because we see $x_1$ and $\bar{x}_1$ each once
%% $BPSIZE_{1,3}$()=6
%% x1 !x1
%% !x2 x2 x2 !x2
%% !x3 x3 x3 !x3
%% 1 0
In the case of branching programs, we actually have a big advantage.
Take subset $S\subseteq {1\ldots n}$ $BPSIZE_S(B)$ = \# edges labelled
by literals of $S$ in the branching program $B$. To get a BP for
$f_x$ from one for $f$, we simply fix the literals and shortcircuit
some of the edges and erase other ones.
If $f$ is a function on $n$ variables and $S_1, S_2\ldots S_l$ is a
partition of the set $\{1\ldots n\}$, then $BPSIZE(f)\geq \sum_{i=1}^l
BPSIZE_{S_i}(f)$
\begin{definition}
Let the function Distinct? be defined as
$$Distinct?(x_{11}\ldots x_{1k}, x_{21}\ldots x_{2k}, \ldots,
x_{l1}\ldots x_{lk})=\left\{\begin{array}{l}
1 \textrm{ if } \forall j\neq k, i_j\neq i_k\\
0 \textrm{ otherwise}
\end{array}\right.$$
with $n=lk$.
\end{definition}
We would like to try to relate the lower bound to the number of bits.
Take any block of variables. If we restrict the remaining variables,
we get many different functions. There are $2^{k^{(l-1)}}$ ways to
choose them all different for every set $T\subseteq \{1\ldots 2^k\}$
with $T={i_2f_1(i_1)=f(i1,i2,...il)\\ 0 \textrm{ if } i_1 \in T
\end{array}\right.$$
The number of functions on $S_1$ is at least
$$\left(\begin{array}{c}2^k\\l-1\end{array}\right) \approx
\left(\begin{array}{c}2^k\\l\end{array}\right)\geq
\left(\frac{2^k}{l}\right)^l$$
This is actually true for any $S_i$, so we get, by picking $k\geq
2\log l$,
\begin{eqnarray*}
BPSIZE_{S_i}(f)&\geq& \frac{\log(2^k/l)^l}{\log\log(2^k/l)^l}\\
&\geq& \frac{kl-l\log l}{\log(kl)}\\
&\geq& \Omega\left(\frac{n}{\log n}\right)
\end{eqnarray*}
Using the result from before, we have a total size
\begin{eqnarray*}
BPSIZE(f)&\geq& \sum_{i=1}^l BPSIZE_{S_i}(f)\\
&\geq&l\cdot\frac{n}{\log n}=\Omega\left(\frac{n}{\log n}\frac{n}{\log
n}\right)
\end{eqnarray*}
and we achieve the desired superlinear lower bound. This may come in
useful when we try to separate NP from NL or other complexity classes.
In the next lecture, we'll see different examples of restricting other
values.
\section{Barrington Construction of Small width BPs}
\subsection{Background}
Roughly at stage of Neciporuk's Theorem, people were trying to
separate NP from P or NL. Some thought that maybe looking at not just
size, but size and width simultaneously, they would get some result.
They hoped the following would be true.
\begin{proposition}
If $f\in P$ needs large width branching programs (super polynomial),
then $P \neq L$.
\end{proposition}
The problem with this, however, is whether we can prove super
polynomial large widths. Given any DNF formula, it is trivial to
construct a BP for it with only three branches. For example, if we
have the DNF formula $x_1x_2x_3 \vee \bar{x}_1x_3x_4 \vee x_2
\bar{x}_3 x_5$, the BP can sequentially try every term and branch
between two of the branches, exiting to the third branch if it is
clear that the whole formula will be satisfied already. Since any
formula for $f\in P$ can reduce to a DNF formula, no $f$ needs super
polynomial width. This leads to the next idea.
\begin{proposition}
If $\exists f \in P$ that needs large branching programs-- super
polynomial width or super polynomial size then $P\neq L$.
\end{proposition}
This turns out to be true, but we still don't know how to prove super
polynomial size. We will instead pursue a weaker goal: we will try to
find $f\in P$ that requires super constant width or super polynomial
size. (This doesn't actually prove anything.)
\begin{proposition}
The function $$Majority(x_1\ldots x_n) = \left\{\begin{array}{l}1
\textrm{ if }\sum x_i \geq n/2\\ 0\textrm{
otherwise}\end{array}\right.$$ requires super constant width if the
size is polynomial.
\end{proposition}
\begin{theorem}
Barrington's Theorem: Let $f$ be a function that has a depth $d$
formula over \{binary AND, NOT\}. Then $f$ has a BP of width 5 (we
will prove 8 today) and depth $4^d$. It has a log-depth formula, so it
has a polynomial-sized BP.
\end{theorem}
\subsection{Register Machine}
To prove Barrington's theorem, we will be using a register machine
[Ben-Or,Cleve]. A register machine consists of $l$ registers, $R_1,
\ldots, R_l$, each of which stores one bit. The register machine is
fed a set of instructions $I_1,\ldots, I_S$ that describe how to
update the registers. For example, $I_2$ might be $R_1 \leftarrow R_2
+ x_i\cdot R_3$. The end result is then some linear combination of the
registers.
If a register machine takes $(R_1\ldots R_l) \rightarrow (R_1\ldots
R_{(l-1)}, R_l+f(x_1\ldots x_n)\cdot R_1)$, then this machine is said
to compute $f$. This can be done by setting the registers to $(1, 0,
\ldots, 0)$ initially. This leaves the first $l-1$ registers the same
and the answer in $R_l$.
\begin{fact}
If an $l$-register machine of size $S$ computes $f$, then $\exists BP$
of width $2^l$ and size $O(S)$.
\end{fact}
The width comes from needing to remember all registers, of which must
have at least $2^l$ states. To prove the BP of width 8, we will thus
need a 3-register machine.
\subsection{Ben-Or Cleve Induction}
If $f$ has depth $d$ formula over \{binary NOT, AND\}, then $f$ is
computed in size $4^d$ by a 3-register machine.
%% R1 arrow to new R3, labelled with f R1
%% R2 R2
%% R3 R3+f*R1
%% $$f(x)=\neg g(x)$$
%% $$R_3 \oplus R_1 (1 \oplus g(x))$$
%% $$R_3+R_1+g(x)*R_1$$
%% $$I=R_3 <- R_3 + R_1$$
%% so this (negation function) is taken care of
%% $f = f_1 \wedge f_2$
%% $f_1$ and $f_2$ both have depth $d$, so $f$ has depth $d+1$
%% first compute f1
%% R1 R1 R1 R1 R1
%% R2 R2 R2+f2(R3+f1R1) R2+f2R3+f1f2R1 R2+f1f2R1
%% R3 R3+f1R1 R3+f1R1 R3 R3
%% arrow goes from R1 to R3,
%% R3 to R2
%% R1 to R3
%% R3 to R2
To calculate NOT, or $\neg f_1$ for some $f_1$, we use the following
register machine. The instructions are:
\begin{center}
\begin{tabular}{ll}
$I_1$: & $R_3 \leftarrow R_3 + f_1R_1$\\
$I_2$: & $R_3 \leftarrow R_3 + R_1$
\end{tabular}
\end{center}
\noindent which leaves the first two registers unchanged, and changes
$R_3$ to contain the value $r_3+(1+f_1)r_1$, where $r_1$ and $r_3$ are
the initial values in registers $R_1$ and $R_3$ respectively. We can
then obtain the value $\neg f_1$ from the result in $R_3$.
\fig{not}{0pt}{Diagram of a BP used for a NOT operation}{not.eps}
To calculate AND between $f_1$ and $f_2$, it is somewhat more
complicated. We use the following instructions for the register machine:
\begin{center}
\begin{tabular}{ll}
$I_1$: & $R_3 \leftarrow R_3 + f_1R_1$\\
$I_2$: & $R_2 \leftarrow R_2 + f_2(R_3 + f_1\cdot R_1)$\\
$I_3$: & $R_3 \leftarrow R_3 + f_1R_1$\\
$I_4$: & $R_2 \leftarrow R_2 + f_2R_3$\\
\end{tabular}
\end{center}
\noindent If we let the initial values in the registers be $r_1$, $r_2$, and
$r_3$, we see that $I_3$ had the effect of restoring $R_3$ to its
original value $r_3$, and $I_4$ cancelled out the $f_2r_3$ term, so
that in the end, $R_2$ contained $r_2+f_1f_2r_1$.
\fig{and}{0pt}{Diagram of a BP used for an AND operation}{and.eps}
\subsection{Conclusions}
At the end of Barrington's results, there were many objects coming
together and looking identical--log-depth circuits, formulas,
polynomial size and bounded width BPs, and so on. Counting has not
worked to show if circuits and formulae are different. In actuality,
the conjecture mentioned earlier is false. We know functions that
require super polynomial size, but they're not in PSPACE, and the
question is how far away that is. Relatedly, the complexity class
``Nick's class'' $\textrm{NC}^i$ is for circuits of depth $\log^in$,
and it is named after Nick Pippenger.
\end{document}