\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{tikz}
\usepackage{fullpage}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\lecture{14}{March 30, 2015}{Madhu Sudan}{Govind Ramnarayan}
%%%% body goes in here %%%%
\section{Today: Arithmetic Circuits}
\begin{itemize}
\item Models of computation
\item Basic results
\end{itemize}
In order to begin to talk about arithmetic complexity, we'll need to talk about some arithmetic problems.
\section{Problems}
We'll be interested in two problems in particular:
\begin{enumerate}
\item Computing some function $\phi: \mathbb{F}^n \to \mathbb{F}^m$ of the form $\phi = \left( \phi_1, \ldots, \phi_m \right)$, where each $\phi_i \in \mathbb{F}[x_1, \ldots, x_n]$ is a polynomial. \\
Examples include computing the determinant or permanent of an $n \times n$ matrix, which are both functions from $\mathbb{F}^{n \times n} \to \mathbb{F}$. This problem can also be phrased as the following: Given some $x \in \mathbb{F}^n$, compute $\phi(x)$. \\
Note that it's not too easy to see how to express various natural problems, like gcd or division, as problems of this form. This class is fairly restricted. The next class is a bit more general.
\item Solving Polynomial Relations: \\
$\phi: \mathbb{F}^n \times \mathbb{F}^m \to \mathbb{F}$ \\
Given: $x \in \mathbb{F}^n$ find $y$ s.t. $\phi(x,y)=0$.
\begin{itemize}
\item This class covers root finding.
\item A complete problem for this class: Given $p_1, \ldots, p_m \in \mathbb{F}[x_1, \ldots, x_n]$, find a common zero.
\end{itemize}
\end{enumerate}
\section{Blum-Shub-Smale Model of Computation}
\begin{tikzpicture}
\draw[step=1cm,black,very thin] (-4,-1) grid (4,0);
\draw
(0,-3) node[circle, inner sep=0pt, draw]{FSM}
(-4,-3) node[rectangle, inner sep=0pt, draw]{$\alpha_1$}
(0,-2.5) -- (-2.5,-1)
(0,-2.5) -- (0.5,-1)
(0, -2.5) -- (2.5, -1);
\draw [dotted] (-4,-3.5) -- (-4,-4.5);
\draw (-4,-5) node[rectangle, inner sep=0pt, draw]{$\alpha_c$};
\end{tikzpicture}
The Blum-Shub-Smale model of computation is quite similar to that of a Turing Machine. We have a finite state machine that gets to use a tape, where the tape contents are elements of a field rather than bits. The machine can add, subtract, multiply, and divide, and it can branch on 0 (i.e. it can make a query ``Is this 0?'' and branch based on the result). Furthermore, the machine can have a constant number of internal constants $\alpha_1, \ldots, \alpha_c$. Note that for a finite field, this is comparable to a Turing Machine. However, for an infinite field, this model may have more power. \\
\begin{itemize}
\item Example: Complex Numbers
\begin{itemize}
\item Model of computation has infinite precision.
\item But at the end, can only check if something is 0 or not.
\item A related aside: over the reals, we cannot even check inequalities in this model! Doing so could give us a lot more power.
\end{itemize}
\end{itemize}
Given such a machine $M$, let $L(M)$ denote the language of strings from our finite field $\mathbb{F}$ that are accepted. Formally: \\
$L(M) \subseteq \{ \mathbb{F}^n\}_{n \geq 0}$ \\
$ = \{ x | M$ accepts $x\}$ \\
What about $L(M) \cap \{ 0,1\}^*$? Can we say anything about that? In fact, we think that anything taking poly-time in this model is contained in BPP. \\
Below we give a visualization of the kind of computation done by the BSS model. Arithmetic operations do not branch, and we branch when we check if something is equal to 0. \\
\begin{center}
\begin{tikzpicture}
\node[circle, draw=black, align=center, minimum size = 0.5cm]{}
child {
node[circle, draw=black, align=center, minimum size = 0.5cm]{$\phi_1(x) = 0$?}
child{node[circle, draw=black, align=center, minimum size = 0.5cm]{}
child {node[circle, draw=black, align=center, minimum size = 0.5cm]{$\phi_2(x')=0$?}
child {node[circle, draw=black, align=center, minimum size = 0.5cm]{}}
child {node[circle, draw=black, align=center, minimum size = 0.5cm]{}}
}
}
child{node[circle, draw=black, align=center, minimum size = 0.5cm]{}}
};
\end{tikzpicture}
\end{center}
The depth of the computation tree above gives the number of operations you perform. Note that the fan out can be exponential in the depth, as we could branch on every step. Furthermore, note that, if you chose to compute a polynomial, what you get is a circuit computing that polynomial. Finally, note that each step of computation can be represented by a low degree polynomial equation. For example, take the following gate: \\
\begin{center}
\begin{tikzpicture}
\node {z}
child { node[circle, draw=black, align=center, minimum size = 0.5cm]{$*$}
child { node {x}}
child { node {y}}
};
\end{tikzpicture}
\end{center}
This can be represented as the polynomial equation $z-xy = 0$. This will be notable in the later section on Hilbert-Nullstellensatz.
\subsection{P and NP in the BSS Model}
\begin{itemize}
\item BSS-P consists of all boolean functions $\phi_n: \F \to \{ 0,1\}$, $\{ \phi_n \}_{n \geq 0}$ that are computable in polynomial time. \\
\item BSS-NP consists of $\psi_n$ such that $\psi_n = \{ x | \exists y $ s.t. $\phi_{n,m}(x,y)=0\}$, where $\phi_{n,m}: \F^n \times \F^m \to \{ 0,1\}$ is computable in polynomial time in the BSS model.
\end{itemize}
\section{Hilbert-Nulstellensatz (HN)}
\begin{itemize}
\item Input: Polynomials $p_1, \ldots, p_m \in \F[x_1, \ldots, x_n]$. Wlog we can take the $p_i$'s to have degree 2.
\item Accept if $\exists \alpha_1, \ldots, \alpha_n \in \F$ such that $p_i(\alpha_1, \ldots, \alpha_n) = 0$ for all $i$.
\end{itemize}
We assert that this problem is NP$_{\F}$-complete. Furthermore, note that in a large field, the $\alpha_i$'s may be very complicated to represent in bits! In fact, it is open if $NP_{\mathbb{C}} \cap \{ 0,1\}^* \subseteq NP$, though this is expected to be false. However, we do know that NP$_{\mathbb{C}} \cap \{ 0,1\}^* \subseteq $ PSPACE, and that, under the general Riemann hypothesis, NP$_{\mathbb{C}} \cap \{ 0,1\}^* \subseteq AM$ (in other words, NP$_{\mathbb{C}}$ has a 2-round interactive proof).
\subsection{A Notable Tangent: Expressing Problems in HN Form}
Consider the following problem: Given $P_1, \ldots, P_n, Q_1, \ldots, Q_n$ polynomials from $\F^m \to \F$, does there exists $x \in \F^m$ such that $P_i(x) = 0, Q_i(x) \neq 0$? \\
Note that we want the condition $Q_i(x) \neq 0$. However, we can still express this in HN form. Let $Q = \prod_i Q_i$. We can now rephrase our problem as: does there exist $x \in \F^m$ and $y \in \F$ such that $P_i(x)=0$ and $1 - y \cdot Q(x)=0$?
\section{Arithmetic Circuits and Valiant's Classes}
Here, we will just look at the circuits that compute polynomials. Arithmetic circuits are also known as \emph{straight-line programs}.
\begin{definition}[Informal] An arithmetic circuit C over a field $\F$ consists of:
\begin{itemize}
\item \textbf{Input Variables}: $x_1, \ldots, x_n$
\item \textbf{Gates}: Gates of the form $U \leftarrow V \diamond W$, where $\diamond \in \{ +, -, *, \div \}$, and $V$ and $W$ are outputs of previous gates, and $U$ is the output of this gate.
\item \textbf{Output Variables: } Some outputs of gates $y_1, \ldots, y_m$.
\end{itemize}
\end{definition}
\begin{definition}
The class ``Valiant P'', or VP, is as follows. VP = $\{ \phi_n: \F^n \to \F^{m(n)}: $deg$(\phi_n) \leq $poly$(n)$, $\phi_n$ is computed by circuits of size poly$(n)$\}
\end{definition}
Some notes about VP:
\begin{itemize}
\item The restriction of low degree on the polynomial $\phi_n$ does not explicitly prevent the circuit that computes it from computing high degree polynomials in intermediate steps, but it turns out we can assume we have low degree polynomials in intermediate steps as well.
\item This definition excludes the high degree polynomials we can compute in polynomial time, e.g. by repeated squaring.
\item Turns out we can exclude division!
\begin{itemize}
\item It's easy to see that we need at most 1 division in such a computation -- we can keep the numerator and denominator separate, then divide at the end. Intuitively, the reason we can exclude division completely is that we are okay with doing a number of calculations proportional to the degree of the output, so we can substitute a division with the other operations using this computational power.
\end{itemize}
\item Depth does not help. Every function in VP can be computed with a $\log^2 n$ depth circuit.
\item Consider $\phi_i: \F^n \to \F^m$, such that $\phi_1, \ldots, \phi_m \in \F[x_1, \ldots, x_n]$.\\
The complexity of computing these $m$ polynomials is linearly related to the complexity of computing $\hat{\phi}:\F^n \times \F^m \to \F$, where
\[\hat{\phi}(x_1, \ldots, x_n, y_1, \ldots, y_m) = \sum\limits_{j=1}^m y_j \phi_j(x_1, \ldots, x_n) \]
\end{itemize}
Now, we will define the equivalent of NP in the arithmetic complexity world. As intuition for this definition, note that the natural analog to the existential quantifier in the arithmetic world is the sum operation.
\begin{definition} The class ``Valiant NP'', or VNP, is as follows. VNP = $\{ \phi_n: \F^n \to \F s.t. \exists \psi_{n,m}:\F^n \times \F^m \to \F \in VP s.t. \phi_n(x) = \sum\limits_{y \in \{0,1 \}^m} \psi_{n,m}(x,y) \}$.
\end{definition}
This class is motivated by the Permanent function:
\[Perm(M) = \sum\limits_{\sigma \in S_n} \prod\limits_{i=1}^n M_{i \sigma(i)} \]
A priori it is not clear that VNP includes the Permanent, as we are summing over $n!$ terms, while the definition of VNP only has us summing over $2^n$ terms. However, note that $\prod\limits_{i=1}^n \sum\limits_{j=1}^m M_{ij}$ includes all the terms of the permanent, and more! This motivates a smaller, inclusion-exclusion type formula for the permanent. Indeed, such a formula exists, with each of the terms in the sum being in VP, proving that the permanent is in VNP:
\[ Perm(M) = \sum\limits_{T \subseteq [n]} (-1)^{n - |T|} \prod\limits_{i=1}^n \sum_{j \in T} M_{ij}\]
Next lecture, we will prove some of the claims listed in this class, and perhaps do some super-linear lower bounds for arithmetic circuits.
\end{document}