% Universitat Politecnica de Catalunya % Dept. of LSI % Technical Report LSI-90-49 % November, 1990. % Revised version, April, 1993. \documentstyle[11pt, titlepage]{article} \newcounter{savenumi} \newenvironment{savenumerate}{\begin{enumerate} \setcounter{enumi}{\value{savenumi}}}{\end{enumerate} \setcounter{savenumi}{\value{enumi}}} \newtheorem{theoremfoo}{Theorem} \newenvironment{theorem}{\pagebreak[1]\begin{theoremfoo}}{\end{theoremfoo}} \newtheorem{propositionfoo}[theoremfoo]{Proposition} \newenvironment{proposition}{\pagebreak[1]\begin{propositionfoo}} {\end{propositionfoo}} \newtheorem{lemmafoo}[theoremfoo]{Lemma} \newenvironment{lemma}{\pagebreak[1]\begin{lemmafoo}}{\end{lemmafoo}} \newtheorem{conjecturefoo}[theoremfoo]{Conjecture} \newenvironment{conjecture}{\pagebreak[1]\begin{conjecturefoo}} {\end{conjecturefoo}} \newtheorem{corollaryfoo}[theoremfoo]{Corollary} \newenvironment{corollary}{\pagebreak[1]\begin{corollaryfoo}} {\end{corollaryfoo}} \newtheorem{nttn}[theoremfoo]{Notation} \newenvironment{notation}{\pagebreak[1]\begin{nttn}\rm}{\end{nttn}} \newtheorem{dfntn}[theoremfoo]{Definition} \newenvironment{definition}{\pagebreak[1]\begin{dfntn}\rm}{\end{dfntn}} \newenvironment{proof} {\pagebreak[1]{\narrower\noindent {\bf Proof:\quad\nopagebreak}}}{\QED} \renewcommand{\labelenumi}{\roman{enumi}.} \newcommand{\yyskip}{\penalty-50\vskip 5pt plus 3pt minus 2pt} \newcommand{\blackslug}{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt\hskip 1pt}} \newcommand{\QED}{{\penalty10000\parindent 0pt\penalty10000 \hskip 8 pt\nolinebreak\blackslug\hfill\lower 8.5pt\null} \par\yyskip\pagebreak[1]} \newcommand{\PH}{{\rm PH}} \newcommand{\NP}{{\rm NP}} \newcommand{\coNP}{\mbox{\rm co-{\rm NP}}} \let\paragraph\P \renewcommand{\P}{{\rm P}} \newcommand{\PARITY}{\oplus} \newcommand{\OR}{\vee} \newcommand{\AND}{\wedge} \newcommand{\implies}{\mathrel{\Rightarrow}} \newcommand{\Iff}{\mathrel{\Leftrightarrow}} \newcommand{\PARITYP}{\PARITY\space\space\P} \newcommand{\PP}{{\rm PP}} \newcommand{\pptoph}{\PP^{\PH}} \newcommand{\pptophtoa}{\PP^{\PH^{A}}} \newcommand{\tac}{\rm TAC} \newcommand{\tacnul}{\tac^{(0)}} \newcommand{\tacnulk}{\tac^{(0)}_k} \newcommand{\montac}{\widehat {\tac}} \newcommand{\tc} {\rm TC} \newcommand{\tcnul}{\tc^{(0)}} \newcommand{\montc}{\widehat {\rm TC}} \newcommand{\montcnul}{\montc^{(0)}} \newcommand{\montcnulk}{\montc^{(0)}_k} \newcommand{\montcnulkplusone}{\montc^{(0)}_{k+1}} \newcommand{\ac}{\rm AC} \newcommand{\acnul}{\ac^{(0)}} \newcommand{\notcontainedin} {\not\subseteq} \newcommand{\notcontainedinexp} {\notcontainedin_{exp}} \newcommand{\parity} {\rm parity} \newcommand{\nat}{{\rm I\kern -.16em N}} % These allow switching interline spacing. The size changes ensure that the % change takes effect immediately. \makeatletter \newcommand{\niceonespacing} {\let\CS=\@currsize\renewcommand{\baselinestretch}{11}\tiny\CS} \newcommand{\nicetwospacing}{\let\CS=\@currsize\renewcommand{\baselinestretch} {1.2}\tiny\CS} \newcommand{\nicethreespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch} {1.3}\tiny\CS} \newcommand{\singlespacingplusplus}{\let\CS=\@currsize\renewcommand{\baselinestr etch}{1.35}\tiny\CS} \newcommand{\nicefivespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{ 1.5}\tiny\CS} \newcommand{\nicesixpacing}{\let\CS=\@currsize\renewcommand{\baselinestretch} {1.6}\tiny\CS} \makeatother \tolerance=2000 \textwidth 6.55in \textheight 9.0in \oddsidemargin 0.001in \evensidemargin 0.001in \topmargin -0.4in \nicetwospacing \sloppy \begin{document} \title{A Lower Bound for Monotone Perceptrons\\ {\small (Revised Version)}} \author{ Frederic Green \\{\small Department of Mathematics and Computer Science} \\{\small Clark University} \\{\small Worcester, Massachusetts 01610}} \date{} \maketitle \begin{abstract} It is proved that there is a monotone function in $\ac^{(0)}_4$ which requires exponential size monotone perceptrons of depth 3. This solves the monotone version of a problem which, in the general case, would imply an oracle separation of $\PP^{\PH}$.\\ \end{abstract} \section{Introduction} Recently perceptrons (see definition below) have received some renewed attention because of their relevance to some important issues in structural complexity theory. In \cite{Green} it was shown that perceptrons cannot compute parity unless they are of exponential size \footnote{In \cite{Green} perceptrons were referred to as $\pptoph$-circuits. In \cite{BeiPPvsPH} the connection with perceptrons was first noted, and we adopt this older terminology here.}. This has the consequence that $(\exists A) (\PARITYP \notcontainedin \pptophtoa)$. A result for perceptrons of depth 2 was used by Beigel \cite{BeiPPvsPH} to provide an oracle $A$ such that $\P^{\NP^A} \notcontainedin \PP^A$. Some interesting results for perceptrons were also obtained by Beigel, Reingold and Spielman \cite{BeiPPclosed} as a consequence of the closure under intersection of $\PP$. Further related results and extensions have been obtained by Beigel, Reingold and Spielman~\cite{BRS}, Aspnes, Beigel, Furst and Rudich~\cite{ABFR}, and Tarui~\cite{Tarui}. An interesting open question left by the work of \cite{Green} is whether there is an oracle separating the hierarchy $\pptoph$. More precisely, is there an oracle $A$ such that the following is true: $(\forall d) (\PP^{\Sigma^{p,A}_{d+1}} \notcontainedin \PP^{\Sigma^{p,A}_{d}})$. Indeed, in light of surprising results such as Toda's theorem \cite{Toda} one might wonder if it is possible that $\pptoph$ is a proper hierarchy in any relativized world. One step in this direction was provided by \cite{BeiPPvsPH}, since the result of that paper trivially implies an oracle $A$ such that $\PP^{\NP^A} \notcontainedin \PP^A$. \cite{BeiPPvsPH} also leaves open the possibility that there is an oracle such that the separations between the levels in $\pptoph$ are via levels of the polynomial hierarchy. That is, it is possible that there is an oracle $A$ such that $(\forall d) ({\Sigma^{p,A}_{d+2}} \notcontainedin \PP^{\Sigma^{p,A}_{d}})$ or even $(\forall d) ({\Delta^{p,A}_{d+2}} \notcontainedin \PP^{\Sigma^{p,A}_{d}})$. In this paper we investigate a circuit problem which is motivated by the above questions. The associated circuit problems are also of intrinsic interest. We suspect that certain $\acnul$ boolean functions of depth $d+1$ cannot be computed by even exponentially large perceptrons of depth $d$. In fact this problem can be reduced to a problem about circuits of a specific depth via the H{\aa}stad switching lemma \cite{Hastad}. If we could show the result for $d=3$, it then follows for all $d > 3$ by applying that lemma. Lacking the techniques to prove this in full generality, we concentrate here on monotone perceptrons. Our main result is that certain monotone depth 4 $\acnul$ functions cannot be computed by exponentially large depth 3 {\em monotone} perceptrons. This result represents a refinement of a result due to Yao~\cite{yao} (whose techniques are also adopted). However to explain the relationship with Yao's work and to describe our results more precisely, we must introduce the basic concepts and notation. A threshold gate over the $N$ Boolean inputs $x_1,...,x_N$ with weights $w_i, i=1,...,N$ and threshold $t$ is a Boolean gate which outputs 1 iff $\sum_{i=1}^m w_i x_i \ge t$. Throughout this paper we consider threshold circuits of bounded weight, that is with $w_i$ bounded from above by a constant independent of $N$. A threshold gate is {\em monotone} if all its weights are non-negative. \begin{definition} A {\em perceptron} is a circuit consisting of a single threshold gate whose inputs are the outputs of constant depth boolean circuits over the basis \{ $\AND, \OR$, not \}. We refer to these subcircuits as the {\em AND/OR subcircuits}. A perceptron is {\em monotone} if its threshold gate is monotone and its AND/OR subcircuits contain no negations. \end{definition} \begin{definition} The class of sets recognizable by perceptrons of polynomial size and depth $k$ is denoted $\tac^{(0)}_{\em k}$, and the union over $k$ of these classes is denoted $\tac^{(0)}$. The monotone versions of these classes are denoted (respectively) $\montac^{(0)}_k$ and $\montac^{(0)}$. \end{definition} In general, we denote the monotone version of any circuit class $C$ by ${\widehat {C}}$. When it is unambiguous, we use the same notation for a complexity class and the associated set of circuits. \begin{nttn} Let $A$ and $B$ be classes of circuits. If there is a function computable by circuits in class $A$ which requires circuits in class $B$ of exponential size, we write $A \notcontainedinexp B$. \end{nttn} Yao \cite{yao} has shown the following, \begin{theorem}\label{le:yao-main} {\rm {\bf (Yao)}} For all k, $\montcnulkplusone \notcontainedinexp \montcnulk$. \end{theorem} In fact this theorem was proved in \cite{yao} via the following stronger result, \begin{theorem}\label{le:yao-main-2} {\rm {\bf (Yao)}} For all k, ${\widehat {\ac}}^{(0)}_{2k} {\notcontainedinexp} \montcnulk$. \end{theorem} Since ${\widehat {\ac}}^{(0)}_k \subseteq \montac^{(0)}_k$ and $\montac^{(0)}_k \subseteq \montcnulk$ for any k, the following is immediate, \begin{corollaryfoo}\label{le:yao-tac} For all k, ${\widehat {\ac}}^{(0)}_{2k} {\notcontainedinexp} \montac^{(0)}_k$ and therefore $\montac^{(0)}_{2k} {\notcontainedinexp} \montac^{(0)}_k$. \end{corollaryfoo} In this paper we sharpen Theorem~\ref{le:yao-main-2} and Corollary~\ref{le:yao-tac} for $k=3$, that is, we show \begin{theorem}\label{le:main-1} ${\widehat {\ac}}^{(0)}_4 {\notcontainedinexp} \montac^{(0)}_3$ and therefore $\montac^{(0)}_4 {\notcontainedinexp} \montac^{(0)}_3$. \end{theorem} While this paper was being written, a stronger result due to H{\aa}stad and Goldmann \cite{Hastad2} appeared, which states that for all $k$, ${\widehat {\ac}}^{(0)}_{k+1} \notcontainedinexp {\widehat {\tc}}^{(0)}_k$. The results reported here were obtained independently and differ in some important technical details. A discussion of H{\aa}stad and Goldmann's results and their relationship with this paper is given at the end of this section. To repeat our main motivation more precisely, if Theorem~\ref{le:main-1} could be shown to hold in the {\sl non}-monotone case, i.e., if $\ac^{(0)}_4 {\notcontainedinexp} \tacnul_3$, then an application of the H{\aa}stad switching lemma \cite{Hastad} would establish a separation of the hierarchy $\pptoph$ relative to some oracle. Depth 4 versus depth 3 is critical, since it would be the base case in such a proof. The switching lemma says that, applying a random restriction to the inputs, the lowest levels of AND and OR can be switched with high probability. Suppose for example we originally have AND's at the second lowest level and OR's at the lowest level. Applying a random restriction, with high probability we can then make any AND of OR's into an OR of AND's and reduce the depth by absorbing one layer of OR's with the OR's above it. It is clear that the minimum number of levels of AND's and OR's to which we can reduce via this method is 2. Since neither AND's nor OR's can be ``absorbed" into a threshold gate, the smallest depth perceptron to which we can reduce consists of a threshold gate over depth 2 AND/OR subcircuits. Observe that Corollary~\ref{le:yao-tac} does not immediately imply the second clause of Theorem~\ref{le:main-1}. It is not clear that $\montac^{(0)}_{k+1} \subseteq \montac^{(0)}_k$ implies $\montac^{(0)}_{2k} \subseteq \montac^{(0)}_k$. This is because $\montac^{(0)}$ circuits are not uniform on every level (the root is a threshold while lower levels consists of AND's and OR's). For the same reason, $\montac^{(0)}_{2k} {\notcontainedinexp} \montac^{(0)}_k$ is not known to imply $\montac^{(0)}_{k+1} {\notcontainedinexp} \montac^{(0)}_k$, nor is this known in the non-monotone case. Similarly it is not known if the collapse of $\PP^{\PH}$ translates upwards, i.e., if $\PP^{\Sigma^p_{d+1}} \subseteq \PP^{\Sigma^p_{d}}$ implies $\pptoph \subseteq \PP^{\Sigma^p_{d}}$. The canonical AC$^{(0)}_k$ functions $f_{k,N}$ (see section 2 for definitions), which we use for achieving the separations, are monotone. Upper bounds for monotone perceptrons computing $f_{k,N}$ imply identical upper bounds for non-monotone perceptrons computing arbitrary AC$^{(0)}_k$ languages. Hence it makes sense to look for monotone simulations of $f_{k,N}$ before looking for more general simulations of AC$^{(0)}_k$ functions. Our results show that small monotone perceptrons computing these functions cannot exist. It is necessary to address a result due to Allender \cite{All}, which issues a warning as to the significance of results about monotone threshold circuits. Essentially due to the fact that Toda's theorem \cite{Toda} relativizes, Yao's result (Theorem~\ref{le:yao-main-2} above) does not carry over to the non-monotone case, at least not via exponential lower bounds. Allender showed explicitly that any $\acnul$ circuit can be simulated by a depth-3 {\sl non}-monotone $\tcnul$-circuit of sub-exponential but superpolynomial size. However, the situation with perceptrons may very well be different. It seems quite possible that $\acnul$ is {\sl not} contained in some specific level of $\tacnul$. Thus far there is evidence for this, but only in the known lower bounds for $\tac^{(0)}_2$. Minsky and Papert prove there is an $\ac^{(0)}_2$ function which cannot be computed by any $\tac^{(0)}_2$-circuit with $\sqrt{N}/2$ bottom fan-in, regardless of circuit size or weights (see \cite{MinPap}, section 3.2). Beigel~\cite{BeiPPvsPH} sharpened this result for perceptrons with small weights. We now describe our results in more detail and clarify the relationship between this paper and the one of H{\aa}stad and Goldmann~\cite{Hastad2}. H{\aa}stad and Goldmann prove that for all $k$, ${\widehat {\ac}}^{(0)}_{k+1} \notcontainedinexp {\widehat {\tc}}^{(0)}_k$. They also adopt similar techniques to Yao's, using a more detailed version of his inductive argument. Their theorem clearly implies the main Theorem~\ref{le:main-1} as stated above. However the more precise statement given in the main result, Theorem~\ref{le:main-lower-bound} (section 3), is not implied by their results, and the techniques of the current paper take advantage of the special circuits we have to deal with. Theorem~\ref{le:main-lower-bound} gives a trade-off between the size of the AND/OR subcircuits and the number of these subcircuits, and this leads to a lower bound which is closer to optimal. The upper bound is $2^{(N+1)lgN}$. The lower bound of H{\aa}stad and Goldmann is $2^{cN}$ while the one obtained here is $2^{cNlglgN}$ (see Corollary~\ref{le:opt}). If the AND/OR subcircuits are sufficiently ``small" (namely, $2^{N^{\epsilon}}$ for $\epsilon < 1$), our lower bound is $N^{\alpha N}$ (see Corollary~\ref{le:N-to-the-epsilon}), which is much closer to optimal. For simpler circuits we obtain results that are optimal. In Theorem~\ref{le:one-in-a-box} we present the optimal improvement of Minsky and Papert's result on $\ac^{(0)}_2$ vs. $\tac^{(0)}_2$ in the monotone setting, and Theorem~\ref{le:optimal-lower-bound} gives the optimal lower bound for ${\widehat{\ac}}^{(0)}_3$ vs. ${\widehat {\tac}}^{(0)}_2$. Thus in the context of perceptrons, the current result strengthens quantitatively the main message of the H{\aa}stad and Goldmann paper. Both the H{\aa}stad and Goldmann results and the current results show that in the monotone setting, in some circumstances threshold gates are no more powerful than AND and OR gates. H{\aa}stad and Goldmann show that to compute the canonical depth $k$ AC$^{(0)}$ function we need a depth $k-1$ monotone threshold circuit of exponential size. We show here (at least for $k=4$) that to compute the canonical depth $k$ AC$^{(0)}$ function we need a depth $k-1$ monotone perceptron whose size is almost the same as what we would need if the single threshold gate were replaced by an OR gate. In this sense, the results obtained here explore the limits of Yao's techniques as applied to perceptrons. \section{Preliminaries} We define our notation and conventions and introduce additional necessary concepts. Many of these are from Yao \cite{yao}, sometimes in a slightly different form. Let $f_{k,N}(x_1, x_2,..., x_{N^k})$ denote the canonical $\ac^{(0)}_{\em k}$-function. The defining circuit for $f_{k,N}$ consists of an $\OR$ ($\AND$) as the top gate if $k$ is even (odd), and $k-1$ alternating levels of $\AND$'s and $\OR$'s below that. The fan-in of all gates in the defining circuit is $N$, so that the number of inputs is $N^k$. More precisely, we define $f_{1,N}(x_1,...,x_N) = \bigwedge \limits_{i=1}^N {x_i}$, and \[ f_{k,N}(x_1,...,x_{N^k}) = \left\{ \begin{array}{ll} \bigvee \limits_{i=1}^N {f_{k-1,N}(x_{(i-1)N^{k-1}+1}, x_{(i-1)N^{k-1}+2},..., x_{(i-1)N^{k-1}+N^{k-1}})} & \mbox{if $k$ is even}\\ \bigwedge \limits_{i=1}^N {f_{k-1,N}(x_{(i-1)N^{k-1}+1}, x_{(i-1)N^{k-1}+2},..., x_{(i-1)N^{k-1}+N^{k-1}})} & \mbox{if $k$ is odd.} \end{array} \right. \] Clearly for any $k$, $f_{k,N} \in {\widehat {\ac}}^{(0)}_k$. The notation $f_{k,N}$ will be used both for the function and the defining circuit. Note that the defining circuits for $f_{k,N}$ are ``stratified", that is, the output of any gate can only go to gates on the next highest level. It will be useful to refer to individual gates in $f_{k,N}$, as well as the set of inputs that can affect the output of that gate. Since it will be of central importance, consider $f_{4,N}$. The ``level 1" gate is the top ($\OR$) gate, the ``level 2" gates are the $\AND$-gates with wires leading to the level 1 gate, and so forth. We refer to the set of inputs which can affect a given gate on a given level as a ``block". For example, the first level 2 $\AND$-block for $f_{4,N}$ consists of the inputs $\{x_1, x_2, ..., x_{N^3}\}$, and the $l^{th}$ level 2 $\AND$-block consists of inputs $\{x_{(l-1)N^3+1}, ..., x_{lN^3}\}$. Note that we only apply the terminology of $\AND$ and $\OR$ blocks to the defining circuits of $f_{k,N}$, and not to arbitrary circuits. See Figure 1 for an illustration of these concepts for $f_{4,3}$. The following definition is essentially due to Yao, although he phrases it in terms of probability distributions. \begin{definition} For any function $h : \{0,1\}^N \rightarrow \{0,1\}$, a pair of sets $(p,q)$ is called a {\em separator} if $p$ is a subset of $h^{-1}(1)$ and $q$ is a subset of $h^{-1}(0)$. \end{definition} We use the same separators as in \cite{yao}. $(p_{k,N},q_{k,N})$ denotes the separator for $f_{k,N}$. Let $(x_1,..., x_{N^k})$ denote the inputs to $f_{k,N}$. $p_{1,N}$ consists of the single element in which all of the $x_i$'s, $i \in \{1,...,N\}$ are $1$ (more formally, $p_{1,N} = \{(1,...,1)\}$ where there are $N$ 1's). $q_{1,N}$ consists of all settings of $(x_1,..., x_{N})$ in which exactly one of the $x_i$'s, $i \in \{1,...,N\}$ is $1$ (i.e., $q_{1,N}$ consists of all input settings of the form $(0,...,0,0,1,0,0,...,0)$). The remaining separators are defined inductively. \begin{itemize} \item Even $k$: Define $p_{k,N}$ to include all input settings of the following form. Choose one of the level 2 $\AND$-blocks of $f_{k,N}$. Set the inputs in that block according to an element of $p_{k-1,N}$, and set all others to 0. Define $q_{k,N}$ to include all input settings in which the inputs in each level 2 $\AND$-block are set independently according to some element of $q_{k-1,N}$. \item Odd $k$: Define $p_{k,N}$ to include all settings in which the inputs in each level 2 $\OR$-block are set independently according to some element of $p_{k-1,N}$. Define $q_{k,N}$ to include all input settings of the following form. Choose one of the level 2 $\OR$-blocks of $f_{k,N}$. Set the inputs in that block according to an element of $q_{k-1,N}$, and set all other inputs to 1. \end{itemize} For any set $p$ of input settings and any boolean function $h : \{0,1\}^N \rightarrow \{0,1\}$, $Pr_p(h(x)=1)$ denotes the probability that $h(x)=1$ when the input setting $x$ is chosen randomly and uniformally from the set $p$. We will always use the sets $p_{k,N}$ and $q_{k,N}$ in this context, and we use the phrase ``choosing from $p$" to mean ``choosing an element randomly and uniformally from the set $p$". The $\epsilon$-discriminator method for proving lower bounds on threshold circuits was introduced by Hajnal, Maass, Pudl{\'a}k, Szegedy and Tur{\'a}n in~\cite{HMPST}. For the separator $(p,q)$ and a subcircuit $C$, define the {\sl advantage} $\Delta$ of $C$ as $\Delta = Pr_p(C(x)=1) - Pr_q(C(x)=1)$. If we can find a separator such that the advantage of any circuit of the same type as $C$ is small, then it follows that a circuit consisting of a threshold over subcircuits of this type must be large. This is stated precisely in the following lemma, which is Lemma 3.3 in reference \cite{HMPST}. It is valid for non-monotone as well as monotone circuits. \begin{lemmafoo}\label{le:hmpst}\cite{HMPST} Let $T$ be a threshold circuit with subcircuits $C_1, C_2, ..., C_m$, so that $T$ outputs 1 if and only if $\sum \limits_{i=1}^m {C_i(x)} \ge t$ for some threshold t. Let $T$ compute the boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, and let $(p,q)$ be a separator for $f$. Let $\Delta_i = Pr_p(C_i(x)=1) - Pr_q(C_i(x)=1)$. Then if $\Delta_i \le s^{-1}$ for all $i \in \{1,...,m\}$, then $m \ge s$. \end{lemmafoo} The intuitive reason for choosing the given separator is as follows. $p_{k,N}$ is chosen so that the fewest possible inputs are 1 when $f_{k,N}$ is 1. $q_{k,N}$ is chosen such that the fewest number of inputs are 0 when $f_{k,N}$ is 0. By choosing $p_{k,N}$ in this way we tend to make $Pr_p(C_i(x)=1)$ small, and by choosing $q_{k,N}$ as we have, we tend to make $Pr_q(C_i(x)=1)$ large. Putting the two together conspires to make $\Delta_i$ as small as possible. This strategy makes essential use of the monotonicity of the perceptron. \section{Main Results} In this section we prove Theorem~\ref{le:main-1}, which asserted that ${\widehat {\ac}}^{(0)}_4 {\notcontainedinexp} \montac^{(0)}_3$. We first present two simpler results which illustrate the proof technique and are also interesting in themselves. The first one says that in any $\montac^{(0)}_2$ circuit which computes $f_{2,N}$, the subcircuits (which are single AND or OR gates) must have fan-in $N$ and the circuit size must be $N$, which are both optimal. In the non-monotone case, as stated in the introduction, the best known lower bound on the fan-in is $\sqrt{N}/2$, as proved by Minsky and Papert. It would be interesting to see if the optimal bound in the monotone case extends to the non-monotone case. \begin{theorem}\label{le:one-in-a-box} Let $T$ be a $\montac^{(0)}_2$ circuit which computes $f_{2,N}$. Then the fan-in of at least one of the $\AND$ or $\OR$ gates of $T$ must be at least $N$ and $T$ must consist of at least $N$ gates. \end{theorem} \begin{proof} Each subcircuit (in this case, a single gate) of $T$ can be either an $\OR$, in which case we will refer to it as $D$, or an $\AND$, in which case we will refer to it as $C$. For notational convenience, we drop the $N$ subscript on the seperators, that is, we denote $p_{k,N}$ and $q_{k,N}$ by $p_k$ and $q_k$ respectively. For any $\AND$ or $\OR$ gate $G$ of $T$, define $\Delta = Pr_{p_2}(G=1) - Pr_{q_2}(G=1)$. By Lemma~\ref{le:hmpst}, if $T$ has finitely many gates, for some gate $G$ we must have $\Delta > 0$. This gate may be an $\OR$ or an $\AND$. We consider these two possibilities separately. Case 1 (OR): Let $\Delta = Pr_{p_2}(D=1) - Pr_{q_2}(D=1)$. Suppose that $\Delta > 0$. Observe that $Pr_{q_2}(D=1)=1$ (and therefore $\Delta \le 0$) unless $D$ is of a special form: It has at most one input from each level 2 $\AND$-block. Thus we may suppose $D$ is of this form, and that it gets its inputs from $s$ $\AND$-blocks. Note that since there are $N$ $\AND$-blocks, it follows that $s \le N$. Choosing from $q_2$, the probability that an input from a given level 2 $\AND$-block is zero is ${1 \over N}$. Since the assignments to level 2 $\AND$-blocks are independent in $q_2$, it follows that $Pr_{q_2}(D=0) = {1 \over N^s}$ and therefore, $$Pr_{q_2}(D=1) = 1 - {1 \over N^s}.$$ Now choosing from $p_2$, the probability that an input from a given level 2 $\AND$-block is 1 is ${1 \over N}$. Since $s$ such blocks contribute to $D$, this implies that $Pr_{p_2}(D=1) \le {s \over N}$. Combining these observations, we have, $$ \Delta \le {s \over N} + {1 \over N^s} - 1.$$ For any fixed $N$, the quantity ${s \over N} + {1 \over N^s}$ is increasing for $1 \le s \le N$. If $s = N-1$, note that ${s \over N} + {1 \over N^s} = 1 - {1 \over N} + {1 \over N^{N-1}}$, which implies that $\Delta < 0$. Thus if $\Delta > 0$, it follows that $s \ge N$ and therefore $s=N$, as claimed. Note that this also implies that $\Delta \le N^{-N} \le {1 \over N}$. Case 2 (AND): Let $C$ denote the $\AND$ gate. Define $\Delta = Pr_{p_2}(C=1) - Pr_{q_2}(C=1)$, and again assume $\Delta > 0$. Now $Pr_{p_2}(C=1) = 0$ (and hence $\Delta \le 0$) unless $C$ is of a special form: All of its inputs can come from at most one $\AND$-block. Suppose $C$ is of this form and that the fan-in of $C$ is $s$. Again, $s \le N$. The probability that $C=1$ choosing from $p_2$ is independent of $s$: $$ Pr_{p_2}(C=1) \le {1 \over N}.$$ For this same $C$, it is easy to see that $Pr_{q_2}(C=1) = 1 - {s \over N}$. Therefore, $$ \Delta \le {1 \over N} - (1 - {s \over N}).$$ Similar to case 1, we find that if $\Delta > 0$, then $s=N$, as claimed. Note that again we have established that $\Delta \le {1 \over N}$. In both cases, we have the inequality $\Delta \le {1 \over N}$, which, by Lemma~\ref{le:hmpst}, implies that the size of the circuit must be at least $N$. \end{proof} We further illustrate the technique of the main theorem by proving optimal lower bounds for $\montac^{(0)}_2$ versus ${\widehat {\ac}}^{(0)}_3$. The proof is simpler in detail but follows the same broad outline as the proof of Theorem~\ref{le:main-lower-bound} which follows. The $N^N$ lower bound is optimal because in the defining circuit for $f_{3,N}$ we can use the distributive law to switch the two upper AND and OR levels, yielding $N^N$ AND gates, and then collapse the lower two levels of AND's, to yield an OR of $N^N$ AND's each of fan-in $N^2$. \begin{theorem}\label{le:optimal-lower-bound} If $N > 2$, any depth 2 monotone perceptron $T$ computing $f_{3,N}(x)$ requires $N^N$ gates. \end{theorem} \begin{proof} We use the same notations and conventions as in the previous proof. We consider each case for a subcircuit of $T$ ($\OR$, which we denote as $D$, or $\AND$, which we refer to as $C$) separately. Since in the defining circuit for $f_{3,N}$ the only $\OR$'s are at level 2, we lose no precision in referring to the set of inputs that affect these gates as $\OR$-blocks. Defining $\Delta = Pr_{p_3}(G=1) - Pr_{q_3}(G=1)$, it suffices, by Lemma~\ref{le:hmpst}, to show that $\Delta \le N^{-N}$. Case 1 (OR): Let $\Delta = Pr_{p_3}(D=1) - Pr_{q_3}(D=1)$. Observe that $Pr_{q_3}(D=1)=1$ (and therefore $\Delta \le 0$) unless $D$ is of a special form: All of its inputs come from at most one $\OR$-block, and furthermore there can be at most one input from each level 3 $\AND$-block. Suppose $D$ is of this form, and that its inputs come from $s$ $\AND$-blocks ($s \le N$). For such a gate, it is not hard to see that $$Pr_{q_3}(D=0) = {1 \over N} \cdot {1 \over N^s} = {1 \over N^{s+1}}$$ and therefore, $$Pr_{q_3}(D=1) = 1 - {1 \over N^{s+1}}.$$ Now choosing from $p_3$, the probability that there are inputs from a given level 3 $\AND$-block that are 1 is ${1 \over N}$. Since $s$ such blocks contribute to $D$, this implies that $Pr_{p_3}(D=1) \le {s \over N}$. Combining these observations, we have, $$ \Delta \le {s \over N} + {1 \over N^{s+1}} - 1.$$ Arguing exactly as in case 1 of Theorem~\ref{le:one-in-a-box}, if $\Delta \ge 0$, it follows that $s = N$. Hence, $\Delta \le N^{-N-1} < N^{-N}$, as claimed. Case 2 (AND): Let $C$ denote the $\AND$ gate. Let $\Delta = Pr_{p_3}(C=1) - Pr_{q_3}(C=1)$. Now $Pr_{p_3}(C=1) = 0$ (and hence $\Delta \le 0$) unless $C$ has inputs from at most one level 3 $\AND$-block of any $\OR$-block. Suppose $C$ is of this form and that the fan-in of $C$ is $s$. Then, $$ Pr_{p_3}(C=1) \le {1 \over N^s}.$$ For this same $C$, it is easy to see that $Pr_{q_3}(C=1) \ge 1 - {s \over N}$. Therefore, $$ \Delta \le {1 \over N^s} - (1 - {s \over N}).$$ Similar to case 1, we find that if $\Delta \ge 0$, then $s \ge N$. Hence $\Delta \le N^{-N}$, as claimed. \end{proof} As in the proof of Theorem~\ref{le:one-in-a-box}, a crucial result in the proof of the previous theorem is the lower bound $N$ on the fan-in $s$ of the $\AND$ or $\OR$-gates of the perceptron. It should be noted that the lower bound on fan-in is tight if the perceptron is a threshold of $\OR$'s, although in that case the bound on size is not tight since then the optimal bound would be $N^{N+1}$, as demonstrated in case 1 of the proof of Theorem~\ref{le:optimal-lower-bound}. Similarly, the lower bound on size is tight if the perceptron is a threshold of $\AND$'s, although in that case the bound on fan-in is not tight since then the optimal bound would be $N^2$. Again it would be interesting to see if the Minsky and Papert lower bound on the fan-in, $\sqrt{N}/2$, can be improved to $N$ in the non-monotone case. We now turn to the main result. We derive a trade-off between the size of the AND/OR subcircuits and the number of such subcircuits. We first give the lower bound on the number of gates when the maximum size of an AND/OR subcircuit is given by any function $u(N)$ bounded from above by $N^{const \cdot N}$. Later we consider various possibilities for $u(N)$. \begin{theorem}\label{le:main-lower-bound} Let $0 < \delta < 1$ be a constant and $u:\nat \rightarrow \nat$ be any function such that $u(N) \le N^{\delta N}$ for all $N$. There exist constants $N_0 > 0$ and $0 < \beta < 1$ such that the following is true. Let $T$ be any depth 3 perceptron which computes $f_{4,N}(x)$ where $N \ge N_0$ and the largest of the AND/OR subcircuits of $T$ has $u(N)$ gates. Then the number of AND/OR subcircuits in $T$ is at least $$min(N^{\beta N}, ({Nlg(N) \over lg(N u(N))})^{\beta N}).$$ \end{theorem} \begin{proof} Let $N_0$ be chosen such that $N_0^{(1-\delta)N_0} > N_0^3$ and let $\beta$ be such that $\beta + \delta \le 1-{2 \over N_0}$. Assume throughout the following that $N > N_0$. Each subcircuit of $T$ can be either an $\OR$-of-$\AND$'s, in which case we refer to it as $D$, or an $\AND$-of-$\OR$'s, in which case we refer to it as $C$. We consider each of these cases separately. For any subcircuit $G$ of $T$, let $\Delta = Pr_{p_4}(G=1) - Pr_{q_4}(G=1)$. By Lemma~\ref{le:hmpst}, it suffices to show that either $\Delta \le N^{-\beta N}$ or $\Delta \le ({ lg(N u(N)) \over Nlg(N)})^{\beta N}$. Also as in the proofs of Theorems~\ref{le:one-in-a-box} and~\ref{le:optimal-lower-bound}, drop the $N$ subscript on the separators, denoting $p_{k,N}$ and $q_{k,N}$ by $p_k$ and $q_k$ respectively. Case 1 (OR-OF-AND's): In this case $\Delta = Pr_{p_4}(D=1) - Pr_{q_4}(D=1)$. Let the $\AND$-gates of $D$ be denoted $C_i$. Let $c \le N$ be the number of level 2 $\AND$-blocks from which $D$ takes its inputs. Let $D_l$ ($l \in \{1,...,c\}$) denote the function obtained from $D$ when we restrict all inputs in $f_4$ to be 0 except those in level 2 $\AND$-block $l$. It is clear that for input settings in $p_4$, $D=1 \Iff {\bigvee \limits_{l=1}^c}{(D_l=1)}$. We thus have $$Pr_{p_4}(D=1) = Pr_{p_4}({\bigvee \limits_{l=1}^c}{(D_l=1)}).$$ Using the fact that the $D_l$'s are mutally exclusive and the fact that $Pr_{p_4}(D_l=1) = {1 \over N}Pr_{p_3}(D_l=1)$, this implies, \begin{eqnarray*} Pr_{p_4}(D=1) & = & {\sum \limits_{l=1}^c}{ Pr_{p_4}(D_l=1)}\\ & = & {1 \over N}{\sum \limits_{l=1}^c}{ Pr_{p_3}(D_l=1)} \end{eqnarray*} Now ${\bigvee \limits_{l=1}^c}{(D_l=1)} \implies D=1$ because $D$ is monotone. Hence $Pr_{q_4}({\bigvee \limits_{l=1}^c}{(D_l=1)}) \le Pr_{q_4}(D=1)$, so that we have \begin{eqnarray*} Pr_{q_4}(D=1) & \ge & 1 - Pr_{q_4}({\bigwedge \limits_{l=1}^c}{(D_l=0)})\\ & = & 1 - {\prod \limits_{l=1}^c}{Pr_{q_3}(D_l=0)} \end{eqnarray*} where the equality holds because the $D_l$'s are independent in $q_4$ (for each $l$, $D_l$ depends only on inputs from a level 2 $\AND$-block, and in $q_4$ these inputs are assigned independently according to $q_3$). Thus we find that \begin{eqnarray}\label{le:delta-inequality} \Delta \le {1 \over N}{\sum \limits_{l=1}^c}{ Pr_{p_3}(D_l=1)} + {\prod \limits_{l=1}^c}{Pr_{q_3}(D_l=0)} - 1. \end{eqnarray} Let $C^l_i$ denote the function that $C_i$ computes when all inputs except those in level 2 $\AND$-block $l$ are 0. Like $C_i$, $C^l_i$ is also an $\AND$-gate. Fix an $l$ and consider assignments to level 2 $\AND$-block $l$ chosen from $p_3$. Observe that the only way in which we can have $Pr_{p_3}(C^l_i=1) \ne 0$ is that in which the set of inputs to $C^l_i$ is a subset of a level 2 $\AND$-block, and furthermore the subset can be partitioned into groups of inputs, each group from at most one of the level 4 $\AND$-blocks of a level 3 $\OR$-block of $f_4$. Suppose $Pr_{p_3}(C^l_i=1) \ne 0$ and that $C^l_i$ has inputs from exactly $k^l_i$ such $\AND$-blocks. (Refer to Figure 2 for clarification.) The probability that any one of these $\AND$-blocks is on is $1 \over N$, and hence for any $C^l_i$ such that $Pr_{p_3}(C^l_i=1) \ne 0$, we have, \begin{eqnarray*} Pr_{p_3}(C^l_i = 1) = {1 \over N^{k^l_i}}. \end{eqnarray*} Let $s_l$ denote the number of $C^l_i$'s, i.e., $s_l$ is the fan-in of $D_l$. Thus \begin{eqnarray*} Pr_{p_3}(D_l=1) & = & Pr_{p_3}({\bigvee \limits_{i=1}^{s_l}}{(C^l_i=1)})\\ & \le & {\sum \limits_{i=1}^{s_l}}{Pr_{p_3}(C^l_i=1)}\\ & \le & {\sum \limits_{i=1}^{s_l}}{1 \over N^{k^l_i}}\\ & \le & {s_l \over N^{k^l_{min}}} \end{eqnarray*} where $k^l_{min} = {\rm min}_i ({k^l_i})$. By hypothesis, $s_l \le u(N)$. Therefore, \begin{eqnarray*} Pr_{p_3}(D_l=1) \le {u(N) \over N^{k^l_{min}}}. \end{eqnarray*} Then since $c \le N$, we find \begin{eqnarray}\label{le:star} {1 \over N} {\sum \limits_{l=1}^c}{Pr_{p_3}(D_l=1)} \le {\rm max}_l Pr_{p_3}(D_l=1) \le {u(N) \over N^{k_m}} \end{eqnarray} where $k_m = {\rm min}_l ({k^l_{min}})$. Now for any $l$ and $i$, $Pr_{q_3}(D_l=0) \le Pr_{q_3}(C^l_i=0)$. For any assignment in $q_3$, $C^l_i$ can be 0 only if one of its inputs from a level 4 $\AND$-block is 0. Thus for any $i$ such that $Pr_{p_3}(C^l_i=1) \not = 0$, we have $Pr_{q_3}(C^l_i=0) \le {k^l_i \over N}$. Therefore \begin{eqnarray}\label{le:starstar} \prod \limits_{l=1}^c Pr_{q_3}(D_l=0) \le {k_m \over N}. \end{eqnarray} Putting this together with eq.~\ref{le:star} and eq.~\ref{le:delta-inequality}, \begin{eqnarray}\label{le:delta-inequality2} \Delta \le {u(N) \over N^{k_m}} + {k_m \over N} - 1. \end{eqnarray} Consider two possibilities for the size of $k_m$. First suppose $k_m \ge {lg(u(N)) \over lg(N)} + 1$. (Note that since $k^l_{min}$ is defined only if $Pr_{p_3}(D_l=1) \ne 0$, the inequality $k_m \ge {lg(u(N)) \over lg(N)} + 1$ really means that for all $l$, either $Pr_{p_3}(D_l=1)=0$ or $k^l_{min} \ge {lg(u(N)) \over lg(N)} + 1$.) Then ${lg(u(N)) \over lg(N)} + s \le k_m \le {lg(u(N)) \over lg(N)} + s + 1$, for some integer $s$ with $1 \le s \le N-{lg(u(N)) \over lg(N)}$. Then by eq.~\ref{le:delta-inequality2}, \begin{eqnarray*} \Delta \le {1 \over N^s} + {1 \over N} \left({lg(u(N)) \over lg(N)} +s+1 \right) - 1. \end{eqnarray*} If $\Delta \ge 0$ it follows that, ${1\over N^s} \ge 1-{1\over N}({lg(u(N)) \over lg(N)}+s+1)$, which, by the upper bound on $u(N)$, yields \begin{eqnarray*} {1 \over N^s} \ge 1 - \delta - {s+1 \over N}. \end{eqnarray*} If $s = (1-\delta)N -2$, the above inequality implies $N^{(1-\delta)N} \le N^3$, which contradicts the choice of $N$. Again, as noted in the proof of Theorem~\ref{le:one-in-a-box}, ${1 \over N^s} + {s \over N}$ is an increasing function of $s$ for $1 \le s \le N$, and therefore $s \ge (1-\delta)N - 1$, which implies $s \ge \beta N$, by the choice of $\beta$. Therefore, $$ \Delta \le {1 \over N^s} \le N^{-\beta N},$$ as desired. Now consider the case $k_m < {lg(u(N)) \over lg(N)} + 1$. We show that $\Delta \le ({lg(N u(N)) \over Nlg(N)})^{\beta N}$. For suppose that for $\sigma$ values of $l$ ($1\le \sigma \le N)$, $Pr_{p_3}(D_l=1) \ne 0$ and $k^l_{min} < {lg(u(N)) \over lg(N)} + 1 = {lg(Nu(N)) \over lg(N)}$. Wlog suppose this is true for $1 \le l \le \sigma$. The best upper bound we can put on $Pr_{p_3}(D_l=1)$ for $1 \le l \le \sigma$ is 1. For the remaining $N-\sigma$ values of $l$, $$ Pr_{p_3}(D_l=1) \le {u(N) \over N^{k^l_{min}}} \le {u(N) \over N^{{lg(u(N)) \over lg(N)}+1}} = {1\over N}.$$ Therefore, $$ {1 \over N} {\sum \limits_{l=1}^c}{Pr_{p_3}(D_l=1)} \le {\sigma \over N} + {N - \sigma \over N^2}.$$ Combining these observations with eqs.~\ref{le:delta-inequality} and~\ref{le:starstar}, we find that \begin{eqnarray*} \Delta & \le & {\sigma \over N} + {N-\sigma \over N^2} + {lg(u(N)) \over N lg(N)} + {1 \over N} - 1\\ & \le & {1 \over N}(1-{1\over N})\sigma + {1 \over N}(2 + \delta N - N). \end{eqnarray*} Thus if $\Delta \ge 0$, it follows that, $$ \sigma \ge (1-\delta)N - 2.$$ Since $c \ge \sigma$, applying eq.~\ref{le:delta-inequality} again we then have, \begin{eqnarray*} \Delta & \le & \prod \limits_{l=1}^c Pr_{q_3}(D_l=0)\\ & \le & \prod \limits_{l=1}^{\sigma} {\mbox {\rm min}}_i Pr_{q_3}(C^l_i = 0)\\ & \le & \prod \limits_{l=1}^{\sigma} {k^l_{min} \over N}\\ & \le & \left( {lg(N u(N)) \over Nlg(N)} \right)^{\sigma}\\ & \le & \left( {lg(N u(N)) \over Nlg(N)} \right)^{(1-\delta)N-2}. \end{eqnarray*} Using the choice of $\beta$, this implies that $\Delta \le \left( {lg(N u(N)) \over Nlg(N)} \right)^{\beta N}$, as desired. (End case 1). Case 2 (AND-OF-OR'S): Similar to case 1, we let $\Delta = Pr_{p_4}(C=1) - Pr_{q_4}(C=1)$. Let the $\OR$-gates of $C$ be denoted $D_i$. Let $C_l$ denote the function obtained from $C$ when we restrict all inputs in $f_4$ to be 0 except those in $\AND$-block $l$ ($l \in \{1,...,c\}$, where $c \le N$ is the number of level 2 $\AND$-blocks from which $C$ takes its inputs). The same considerations as in case 1 yield \begin{eqnarray*} Pr_{p_4}(C=1) & = & Pr_{p_4}({\bigvee \limits_{l=1}^c}{(C_l=1)})\\ & = & {\sum \limits_{l=1}^c}{ Pr_{p_4}(C_l=1)}\\ & = & {1 \over N}{\sum \limits_{l=1}^c}{ Pr_{p_3}(C_l=1)}\\ & \le & {\rm max}_l (Pr_{p_3}(C_l=1)). \end{eqnarray*} (Note that the final inequality is the first departure with the argument of case 1.) Denote the $l$ for which $Pr_{p_3}(C_l=1)$ is a maximum by $l'$. Thus $Pr_{p_4}(C=1) \le Pr_{p_3}(C^{l'}=1)$. For the quantity $Pr_{q_4}(C=1)$ we again follow an argument similar to that of case 1 to obtain, \begin{eqnarray*} \Delta & \le & Pr_{p_3}(C^{l'}=1) + {\prod \limits_{l=1}^c}{Pr_{q_3}(C_l=0)} - 1\\ & \le & Pr_{p_3}(C^{l'}=1) + Pr_{q_3}(C^{l'}=0) - 1\\ & \le & Pr_{p_3}(C^{l'}=1) - Pr_{q_3}(C^{l'}=1) \end{eqnarray*} (The alert reader will wonder why a similar strategy was not followed in case 1, since it appears to be simpler here. The reason is that the product in the second term on the LHS of eq.~\ref{le:delta-inequality} is crucial to the argument in case 1, but not here.) A dual version of the argument for case 1, now simplified since we are using the distribution $p_3$, gives the desired bound on $\Delta$. (End case 2). \end{proof} The restriction $N^{\delta N}$ on the size of the AND/OR subcircuits in Theorem~\ref{le:main-lower-bound} is ``optimal" in the following sense. The proof would not work if $\delta = 1$. Allowing $\delta = 1$ means we allow the $\AND$ and $\OR$ gates of $T$ to have fan-in $N^N$ (that is, we may take $u(N)=N^N$). This fan-in is just large enough that the circuit $T$ could compute $f_4$: simply expand the lowest two levels of $f_4$ (this gives $N^N$ gates for each $\OR$-gate expanded), collapse the resulting two adjacent levels of $\AND$'s, and set the threshold to 1 (so the threshold gate is an $\OR$-gate). If the upper bound on $u(N)$ is realized then trivially we have circuits whose size is close to optimal (that is, $N^{\delta N}$). This is also true if $u(N)$ is sufficiently small. \begin{corollaryfoo}\label{le:N-to-the-epsilon} Let $\epsilon$ be any constant such that $0 < \epsilon < 1$. There exist constants $0 < \alpha < 1$ and $N_0$ such that for any $N > N_0$, if T is any depth 3 perceptron which computes $f_{4,N}$ and the size of the AND/OR subcircuits of T is at most $2^{N^{\epsilon}}$, the size of T is at least $N^{\alpha N}$. \end{corollaryfoo} \begin{proof} In Theorem~\ref{le:main-lower-bound}, consider any $u(N) \le 2^{N^{\epsilon}}$. It is easy to see, for some $0 < \epsilon' < 1$ and for sufficiently large $N$, it holds that $$ \left( {N lg(N) \over lg(N u(N)) } \right) \ge N^{\epsilon'}.$$ This implies that the number of gates of T is at least $N^{\epsilon' \beta N}$, from which the result follows by taking $\alpha = \epsilon' \beta$. \end{proof} For intermediate subcircuit sizes (that is, between $2^{N^{\epsilon}}$ and $N^{\delta N}$), we have not been able to obtain bounds that are as close to optimal. The best one can do using Theorem~\ref{le:main-lower-bound} is given in the following. \begin{corollaryfoo}\label{le:opt} Let $0 < \delta < 1$ be a constant. There exists a constant $N_0 > 0$ and a constant $\alpha$, $0 < \alpha < 1$ such that the following is true. Let $T$ be any depth 3 perceptron which computes $f_{4,N}(x)$ where the number of inputs is $N^4$ ($N \ge N_0$) and the fan-in of any of the $\AND$ or $\OR$-gates of $T$ is bounded from above by $N^{\delta N}$. Then the number of gates in $T$ is at least $2^{\alpha N lg(lg(N))}$. \end{corollaryfoo} \begin{proof} Let $u(N)$ be as in Theorem~\ref{le:main-lower-bound}. If $u(N) \ge 2^{Nlg(lg(N))}$, we are done. If $u(N) < 2^{Nlg(lg(N))}$, then it is not hard to see that if $\beta <1$, there is a constant $\alpha < 1$ such that for sufficiently large $N$ $$\left( {Nlg(N) \over lg(N u(N))} \right)^{\beta N} \ge 2^{\alpha N lg(lg(N))}.$$ Applying Theorem~\ref{le:main-lower-bound}, the result follows. \end{proof} \section{Acknowledgements} I wish to thank the Departament de Llenguatges i Sistemes Inform{\`a}tics, Barcelona, where this paper was originally written, for their hospitality. Conversations on this subject with Arthur Chou and Richard Beigel are gratefully acknowledged. The author is greatful to two anonymous referees for comments which greatly improved the paper. \begin{thebibliography}{1} \bibitem{All} E.~Allender, ``A note on the power of threshold circuits", {\em Proceedings of the 30th IEEE Symposium on Foundations of Computer Science} (1989) 580-584. \bibitem{ABFR} J.~Aspnes, R.~Beigel, M.~Furst and S.~Rudich, ``The Expressive Power of Voting Polynomials", in {Proceedings of the 23rd Annual ACM Symposium on Theory of Computing}, ACM Press (1991) 402-409. \bibitem{BeiPPclosed} R.~Beigel, N.~Reingold, and D.~Spielman, ``PP is closed under intersection", in {\em Proceedings of the 23rd Annual ACM Symposium on Theory of Computing}, IEEE Computer Society Press (1991) 1-9. Also, {J. Comp. Syst. Sci.}, to appear. \bibitem{BRS} R.~Beigel, N.~Reingold, and D.~Spielman, ``The Perceptron Strikes Back", in {\em Proceedings of the Sixth Annual Conference on Structure in Complexity Theory}, IEEE Computer Society Press (1991) 286-291. \bibitem{BeiPPvsPH} R.~Beigel, ``Perceptrons, PP, and the Polynomial Hierarchy", in {\em Proceedings of the Seventh Annual Conference on Structure in Complexity Theory}, IEEE Computer Society Press (1992) 14-19. \bibitem{Green} F.~Green, ``An oracle separating $\PARITYP$ from $\pptoph$", {\em Information Processing Letters} {\bf 37} (1991) 149-153. \bibitem{Hastad} J.~H{\aa}stad, ``Computational limitations for small-depth circuits", The MIT press, Cambridge 1987. \bibitem{Hastad2} J.~H{\aa}stad and M.~Goldmann, ``On the Power of Small-Depth Threshold Circuits", {\em Computational Complexity} {\bf 1} (1991) 113-129. \bibitem{HMPST} A.~Hajnal, W.~Maass, P.~Pudl{\'a}k, M.~Szegedy, and G.~Tur{\'a}n, "Threshold circuits of bounded depth", in {\em Proceedings 28th Annual IEEE Symposium on Foundations of Computer Science}, IEEE Computer Society Press (1987) 99-110. \bibitem{MinPap} M.~L.~Minsky and S.~A.~Papert, ``Perceptrons" (expanded edition), MIT Press, Cambridge, 1988. \bibitem{Tarui} J.~Tarui, ``Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy", in {8th Annual Symposium on Theoretical Aspects of Computer Science}, Springer-Verlag LNCS 480, (1991) 238-250. \bibitem{Toda} S.~Toda, ``On the computational power of $\PP$ and $\PARITYP$", in {\em Proceedings 30th IEEE Symposium on Foundations of Computer Science}, IEEE Computer Society Press (1989) 514-519. \bibitem{yao} A.~C.-C.~Yao, ``Circuits and local computation", in {\em Proceedings of the 21st ACM Symposium on Theory of Computing}, ACM Press (1989) 186-196. \end{thebibliography} \end{document}