Cortical Computation via Iterative Constructions
Christos Papadimitrou∗

Samantha Petti†

Santosh Vempala†

arXiv:1602.08357v2 [] 15 Jun 2016

June 16, 2016

Abstract
We study Boolean functions of an arbitrary number of input variables that can
be realized by simple iterative constructions based on constant-size primitives. This
restricted type of construction needs little global coordination or control and thus is
a candidate for neurally feasible computation. Valiant’s construction of a majority
function can be realized in this manner and, as we show, can be generalized to any
uniform threshold function. We study the rate of convergence, finding that while
linear convergence to the correct function can be achieved for any threshold using a
fixed set of primitives, for quadratic convergence, the size of the primitives must grow
as the threshold approaches 0 or 1. We also study finite realizations of this process
and the learnability of the functions realized. We show that the constructions realized
are accurate outside a small interval near the target threshold, where the size of the
construction grows as the inverse square of the interval width. This phenomenon, that
errors are higher closer to thresholds (and thresholds closer to the boundary are harder
to represent), is a well-known cognitive finding.

1

Introduction

Cortical computation. Among the many unexplained abilities of the cortex are learning complex patterns and invariants from relatively few examples. This is manifested in
a range of cognitive functions including visual and auditory categorization, motor learning
and language. In spite of the highly varied perceptual and cognitive tasks accomplished, the
substrate appears to be relatively uniform in the distribution and type of cells. How could
these 80 billion cells organize themselves so effectively?
Cortical computation must therefore be highly distributed, require little synchrony (number of pairs of events that must happen in lock-step across neurons), little global control
(longest chain of events that must happen in sequence) and be based on very simple primitives [Papadimitriou and Vempala, 2015b]. Assuming that external stimuli are parsed as
sets of binary sensory features, our central question is the following:
∗

UC Berkeley, christos@berkeley.edu, supported in part by NSF award CCF-1408635 and by Templeton
Foundation grant 3966.
†
Georgia Tech, {spetti3,vempala}@gatech.edu, supported in part by NSF awards CCF-1217793 and
EAGER-1415498.

1

What functions can be represented and learned by algorithms so simple that one could
imagine them happening in the cortex?
Perhaps the most natural primitives are the AND and OR functions on two input variables. These functions are arguably neurally plausible. They were studied as JOIN and
LINK by Feldman and Valiant [2009], Valiant [1994, 2000, 2005], who showed how to implement them in the neuroidal model. An item is a collection of neurons (corresponding to
a neural assembly in neuroscience) that represents some learned or sensed concept. Given
two items A, B, the JOIN operation forms a new item C = JOIN(A, B), which “fires” when
both A and B fire, i.e., C represents A ∧ B. LINK(A, B) captures association, and causes
B to fire whenever A fires. By setting LINK(A, C) and LINK(B, C), we achieve that C
is effectively A ∨ B. While the precise implementation and neural correlates of JOIN and
LINK are unclear, there is evidence that the brain routinely engages in hierarchical memory
formation.
Monotone Boolean functions. Functions constructed by recursive processes based on
AND/OR trees have been widely studied in the literature, motivated by the design of reliable
circuits as in [Moore and Shannon, 1956] and more recently, understanding the complexitytheoretic limitations of monotone Boolean functions. One line of work studies the set of
functions that could be the limits of recursive processes, where at each step, the leaves of a
tree are each replaced by constant-size functions. Moore and Shannon [1956], showed that a
simple recursive construction leads to a threshold function, which can be applied to construct
stable circuits. Valiant [1984] used their 4-variable primitive function (A ∨ B) ∧ (C ∨ D) to
derive a small depth and size threshold function that evaluates to 1 if at least (2 − φ) ≈ 0.38
fraction of the inputs are set to 1 and to zero otherwise. The depth and size were O(log n)
and O(n5.3 ) respectively. Calling it the amplification method, Boppana [1985] showed that
Valiant’s construction is optimal. Dubiner and Zwick [1992] extended the lower bound to
classes of read-once formulae. Hoory et al. [2006] gave smaller size Boolean circuits (where
each gate can have fan out more than 1), of size O(n3 ) for the same threshold function. Luby
et al. [1998] gave an alternative analysis of Valiant’s construction along with applications to
coding. The construction of a Boolean formula was extended by Servedio [2004] to monotone
linear threshold functions, in that they can be approximated on most inputs by monotone
Boolean formulae of polynomial size. Friedman [1986] gave more efficient constructions for
threshold functions with small thresholds.
Savicky gives conditions under which the limit of such a process is the uniform distribution
on all Boolean functions with n inputs [Savicky, 1987, 1990] (see also Brodsky and Pippenger
[2005], Fournier et al. [2009]). In a different application, Goldman et al. [1993] showed how to
use properties of these constructions to identify read-once formulae from their input-output
behavior.
Our work. Unlike previous work, where a single constant-sized function is chosen and
applied recursively, we will allow constructions that randomly choose one of two constantsized functions. To be neurally plausible, our constructions are bottom-up rather than topdown, i.e., at each step, we apply a constant-size function to an existing set of outputs.
In addition, the algorithm itself must be very simple — our goal is not to find ways to
2

realize all Boolean functions or to optimize the size of such realizations. Here we address
the following questions: What functions of n input items can be constructed in this iterative
manner? Can arbitrary uniform threshold functions be realized? What size and depth of
iterative constructions suffices to guarantee accurate computations? Can such functions
and constructions be learned from examples, where the learning algorithm is also neurally
plausible?
Our rationale for uniform threshold functions is two-fold. First, uniform threshold functions are fundamental in computer science and likely also for cognition. Second, the restriction to JOIN and LINK as primitives ensures that any resulting function will be monotone
since negation is not possible in this framework. Moreover, if we require the construction
to be symmetric, it would seem that the only obtainable family of Boolean functions are
uniform thresholds. However, as we will see, there is a surprise here, and in fact we can
get staircase functions, i.e., functions that take value pi on the interval (ai , ai+1 ) where
a0 = 0 < a1 < a2 < · · · < ak < ak+1 = 1 and 0 = p0 < p1 < p2 < · · · < pk−1 < pk = 1.
To be able to describe our results precisely, we begin with a definition of iterative constructions.

1.1

Iterative constructions

A sequence of AND/OR operations can be represented as a tree. Such a tree T with n
leaves naturally computes a function gT : {0, 1}n → {0, 1}. We can build larger trees in a
neurally plausible way by using a set of small AND/OR trees as building blocks. Let C be a
probability distribution on a finite set of trees. We define an iterative tree for C as follows.
IterativeTree(L, m, C, X):
For each level j from 1 to L, apply the following iteration m times:
(level 0 consists of the input items X)
1. Choose a tree T according to C.
2. Choose items at random from the items on level j − 1.
3. Build the tree T with these items as leaves.
The construction of small AND/OR trees is a decentralized process requiring a short sequence of steps, i.e., the synchrony and control parameters are small. Therefore, we consider
them to be neurally plausible.
The iterative tree construction has a well-defined sequence of levels, with items from
the next level having leaves only in the current level. A construction that needs even less
coordination is the following: the probability that an item participates in future item creation
decays exponentially with time. The weight of an item starts at 1 when it is created and
decays by a factor of e−α each time unit. We refer to such constructions as exponential
iterative constructions. An extreme version of this, which we call wild iterative construction,
is to have α = 0, i.e, all items are equally likely to participate in the creation of new items.
Figure 1 illustrates these constructions.
3

ExponentialConstruction(k, C, α):
Initialize the weights of input items to 1.
Construct k items as follows:
1. Choose a tree T according to C.
2. Choose the leafs for T independently from existing items with probability proportional
to the weight of the item.
3. Build the tree T with these items as leaves.
4. Multiply the weight of every item by e−α .

Figure 1: Left: an iterative construction. Middle: a wild construction. Right: an exponential
construction. In the latter two images, the thickness of the outline representing each item
indicates the probability the item will be selected in the construction of the next item.

1.2

Results

We are interested in the functions computed by high-level items of iterative constructions.
In particular, we design iterative constructions so that high-level items compute a threshold
function with high probability.
Definition 1.1 The function f : [0, 1] → [0, 1] is a t-threshold if f (x) = 0 for x < t and
f (x) = 1 for x > t.
For given probability distribution on a set of trees, the output of high-level items of a
corresponding iterative construction depends on the following: (i) the fraction of input
items firing, (ii) the width of the levels, and (iii) the number of levels. For an n item input,
the fraction of input items firing must take the form k/n, k ∈ Z. Throughout the paper,
we assume that the distance between the desired threshold and the fraction of input items
firing is at least 1/n. To address (ii), we first analyze the functions computed by high-level
items of an iterative construction when the width of the levels is infinite, which is equivalent
to the “top down” approach. Then in Section 5, we remove this assumption and analyze the
“bottom-up” construction in which the items at level j −1 are fixed before the items at level j
are created. The following theorems give a guarantee on the probability that an iterative tree
with infinite width levels accurately computes a threshold function in terms of the number
4

√
of levels. To start, we restate Valiant’s result [Valiant, 1984]. Here φ = ( 5 + 1)/2 is the
golden ratio (2 − φ ≈ 0.38).
Theorem 1.2 Let R be the tree that computes (A ∨ B) ∧ (C ∨ D). Then, an item at level
Ω(log n + log k) of an infinite width iteratively constructed tree for R computes a (2 − φ)threshold function accurately with probability at least 1 − 2−k .
In this construction, the iterative tree that computes the 2 − φ threshold function is
built using only one small tree. We show that it is possible to achieve arbitrary threshold
functions if we allow our iterative tree to be built according to a probability distribution on
two distinct smaller trees.
Theorem 1.3 Let 0 < t < 1 and let R = {Pr(T1 ) = t, Pr(T2 ) = 1 − t} where T1 is the tree
that computes (A ∨ B) ∧ C and T2 is the tree that computes (A ∧ B) ∨ C. Then, an item at
level Ω(log n+k) of an infinite width iteratively constructed tree for R computes a t-threshold
function accurately with probability at least 1 − 2−k .
The rate of convergence of this more general construction is linear rather than quadratic.
While both are interesting, the latter allows us to guarantee a correct function on every
input with depth only O(log n), since there are 2n possible inputs.
Definition 1.4 A construction exhibits linear convergence if items at level Ω(log n + k) of
an infinite width iterative tree accurately compute the threshold function with probability at
least 1 − 2−k . A construction exhibits quadratic convergence if items at level Ω(log n + log k)
of an infinite width iterative tree accurately compute the threshold function with probability
at least 1 − 2−k .
The next theorem gives constructions using slightly larger trees with 4 and 5 leaves
respectively (illustrated in Figure 2) that converge quadratically to a t-threshold function
for a range of values of t, with more leaves giving a larger range. Moreover, these ranges
are tight, i.e. no construction on trees with 4 or 5 leaves yields quadratic convergence to a
t-threshold function for t outside these ranges.
2

1−t−t
Theorem 1.5 (A) Let 2 − φ ≤ t ≤ φ − 1 and α(t) = 2t(t−1)
. Let R = {Pr(F1 ) =
α(t), Pr(F2 ) = 1 − α(t)} be the probably distribution on trees in Figure 2. Then, an item
at level Ω(log n + log k) of an infinite width iteratively constructed tree for R computes a
t-threshold function accurately with probability at least 1 − 2−k . Moreover, for t outside this
range, there exists no such construction on trees with four leaves that converge quadratically
to a t-threshold function.
2

3

+t
(B) Let α(t) = −1+5t−4t
and let t be a value for which 0 ≤ α(t) ≤ 1, so 0.26 . t . 0.74.
5t(t−1)
Let R = {Pr(V1 ) = α(t), Pr(V2 ) = 1 − α(t)} be the probably distribution on trees in Figure 2.
Then, an item at level Ω(log n + log k) of an infinite width iteratively constructed tree for R
computes a t-threshold function accurately with probability at least 1 − 2−k . Moreover, for t
outside this range, there exists no such construction on trees with five leaves that converges
quadratically to a t-threshold function.

5

AND

F1

OR

OR

V1

AND

AND

V2

OR
AND

OR

F2

AND

AND
OR

AND

OR
OR

Figure 2: For .38 . t . 0.62, there exists a probability distribution on F1 and F2 that yields
an iterative tree that converges quadratically to a t-threshold function. For .26 . t . 0.74,
there exists a probability distribution on V1 and V2 that yields an iterative tree that converges
quadratically to a t-threshold function.
As the desired threshold t approaches 0 or 1, we show that an iterative tree that computes
the t-threshold function must use increasingly large trees as building blocks.
Theorem 1.6 Let t be a threshold, 0 < t < 1 and let s = min{t, 1 − t}. Then, the construction of an iterative tree whose level Ω(log n + log k) items compute a t-threshold function
with probability at least 1 − 2−k must be defined over a probability distribution on trees with
at least √12s leaves.
This raises the question of whether it is possible to have quadratic convergence for any
threshold. We can extend the constructions described in Theorem 1.5 by using analogous
trees with six and seven leaves to obtain quadratic convergence for thresholds in the ranges
0.15 . t . 0.85 and 0.11 . t . 0.89 respectively. However, it is not possible to generalize
this construction beyond this point, as we discuss in Section 4. Instead, to achieve quadratic
convergence for thresholds near the boundaries, we turn to the following construction, which
asymptotically matches the lower bound of Theorem 1.6. We define Ak as a tree on 2k leaves
that computes (x1 ∨ x2 ∨ · · · ∨ xk ) ∧ (xk+1 ∨ xk+2 ∨ · · · ∨ x2k ) and Bk as a tree on 2k leaves
that computes (x1 ∧ x2 ∧ · · · ∧ xk ) ∨ (xk+1 ∧ xk+2 ∧ · · · ∧ x2k ).
Theorem 1.7 For any 0 < t ≤ 2 − φ, there exists k and a probability distribution on Ak
and Ak+1 that yields an iterative tree with quadratic convergence to a t-threshold function.
Similarly for any φ − 1 ≤ t < 1, there exists k and a probability distribution on Bk and Bk+1
that yields an iterative tree with quadratic convergence to a t-threshold function.
There is a trade-off between constructing iterative trees that converge faster and requiring minimal coordination in order to build the subtrees. Building a specified tree on a small
number of leaves requires less coordination than building a specified tree on many leaves.
Therefore, as t approaches 0 or 1, constructing an iterative tree with quadratic convergence
becomes less neurally plausible because the construction of each subtree requires much coordination. These results are in line with behavioral findings [Rosch, 1978, Rosch et al.,
6

1976] and computational models [Arriaga and Vempala, 2006, Arriaga et al., 2015] about
categorization being easier when concepts are more robust.
In Section 4, we characterize the class of functions that can be achieved by iterative
constructions allowing building block trees of any size. We show that it is possible to achieve
an arbitrarily close approximation of any staircase function in which each step intersects the
line y = x. This result is described more precisely in Theorem 4.10.
In the following section we turn to finite realizations of iterative trees. The above theorems analyze the behavior of an iterative construction where the width of the levels is infinite.
We assumed that for any input the number of items turned on at given level of the tree is
equal to its expectation. Imagining a “bottom up” construction, we note that the chance
that the number of items firing at a given level deviates from expectation is non-trivial. Such
deviations percolate up the tree and effect the probability that high-level items compute the
threshold function accurately. The smaller the width of a level, the more likely that the
number of items on at that level deviates significantly from expectation, rendering the tree
less accurate. How large do the levels of an iteratively constructed tree need to be in order
to ensure a reasonable degree of accuracy?
Theorem 1.8 Consider a construction of a t-threshold function with quadratic convergence
described in Theorem 1.5 or Theorem 1.7 in which each level ` has m` items and the fraction
of input items firing
 is at least ε from the threshold t. Then, with probability at least 1 − γ,
items at level Ω log γ1 + log 1ε will accurately compute the threshold function for m1 =


P
Ω ln(1/γ)
and ` m` = O(m1 ).
ε2
As a direct corollary, by setting ε = O(1/n) and γ = 2−n−1 , we realize a t-threshold
construction of size O(n3 ) for any t, matching the best-known construction which was for a
specific threshold [Hoory et al., 2006]. The finite-width version of Theorem 1.3 is given in
Section 5.
The exponential iterative construction also converges to a t-threshold function for appropriate α. We give the statements here for the wild iterative construction (with no weight
decay) and the general exponential construction.
Theorem 1.9 Consider a wild construction on n inputs for the t-threshold function given in
1
) max{ ε12 , δ12 } where ε is the distance between t and the fracTheorem 1.3 in which n > log( 8εδ

tion of inputs firing. Then, there is an absolute constant c such that for k = Ω n δ1c + ε1c ,
the k th item accurately computes the t-threshold function with probability at least 1 − δ.
Theorem 1.10 Consider an exponential construction on n inputs for the t-threshold funcmin{ε2 ,δ 2 }
tion given in Theorem 1.3 in which α = b 2048e
4 log(4/εδ) c and n > 1/α. Then for

k=Ω



log εδ1
n
log
,
min{ε2 , δ 2 }
εδ

with probability at least 1 − δ, the k th item will compute the t-threshold function.
Finally, in Section 6, we give a simple cortical algorithm to learn a uniform threshold
function from a single example, described more precisely by the following theorem.
7



Theorem 1.11 Let X ∈ {0, 1}n such that ||X||1 = tn, L = Ω log γ1 + log 1ε , and ε =
q

ln(1/γ)
Ω
. Then, on any input in which the fraction of input items firing is outside
m
[t − ε, t + ε], items at level L of an iterative tree produced by LearnThreshold(L, m, X) will
compute a t-threshold function with probability at least 1 − γ.
The next section provides the groundwork for these theorems, and the proofs are in
Sections 3, 4, 5, 6. We discuss several open questions and directions for future research in
Section 7.

2

Polynomials of AND/OR Trees

Let gT : {0, 1}n → {0, 1} be the Boolean function computed by an AND/OR tree T with n
leaves. We define fT as the probability that T evaluates to 1 if each input item is independently set to 1 with probability p.
fT (p) = Pr (gT (X) = 1 | X ∼ B(n, p)) .
We analogously define fC (p) for probability distributions on trees; let fC be the probability that a tree chosen according to C evaluates to 1 if each input item is independently
set to 1 with probability p. Let λT be the probability of T in distribution C. We have
X
fC (p) =
λT fT (p).
T ∈C

In an iterative construction for the probability distribution C, an item at level k evaluates
to 1 with probability fC (pk−1 ) where pk−1 is the probability that an item at level k − 1
evaluates to 1. In the case where the width of the levels is infinite, the fraction of inputs
firing any level is exactly equal its expectation. Therefore, the probability that items at level
(k)
k evaluate to 1 is fC (p) where p is the probability an input is set to 1. This follows directly
from the recurrence relation:
(k)
(k−1)
fC (p) = fC (fC (p)).
In the remainder of this section, we collect properties of polynomials of AND/OR trees
to be used in the analysis of iterative trees.
We call a polynomial achievable if it can be written as fT for some AND/OR tree T . We
call a polynomial achievable through convex combinations if it can be written as fC for some
probability distribution on AND/OR trees C. Table 1 lists all achievable polynomials with
degree at most five. Note that A is closed under the AND and OR operations. If a, b ∈ A,
then a · b ∈ A and a + b − a · b ∈ A. The set of polynomials achievable through convex
combinations is the convex hull of A.
Lemma 2.1 Let A be the set of achievable polynomials. Let A(x) = a0 + a1 x + · · · + an xn
be a polynomial in A. Then,
1. a0 = 0
8

2. an = −1 or 1
Pn
3.
i=0 ai = 1
4. If A(x) has degree d, then A(x) is the polynomial for a tree on d leaves.
Proof. We proceed by induction on the degree of A(x). For d = 1, A(x) = x is the only
polynomial in A and all the above properties hold. Next assume all the properties hold for
polynomials of degree less than d. Let A(x) be an achievable polynomial of degree d. Then
the root of the tree for A, which we call TA , is either an AND or an OR operation. In the
former case, A = B · C and in the latter case A = B + C − B · C where B, C ∈ A and B
has degree k and C has degree d − k for 0 < k < d. In either case, the first three properties
follow trivially from the inductive hypothesis. For item (4), let TB and TC be trees that
correspond to B and C respectively. Then TB and TC have k and d − k leaves respectively.
Since TA is TB adjoined with TC with an AND or OR operation, TA has d leaves.

Lemma 2.2 Let f ∈ A be an achievable polynomial of degree d, f = a0 +a1 x+a2 x2 +. . . ad xd .
Then |a` | ≤ d` .
Proof. Proceed by induction. The only achievable polynomial of degree 1 is f (x) = x, so
0
the statement clearly holds. Next, assume |a`0 | ≤ d` holds for all l0 < l. Let f be a degree
d achievable polynomial. We may assume f = g + h − gh or f = gh where g and h are
achievable polynomials with degree k and d − k respectively where k ≤ 2` . First consider
the case when f = g + h − gh, meaning the root of the tree corresponding to f is an OR
operation. Observe
|a` (f )| = a` (g) + a` (h) −
≤ k ` + (d − k)` +

l−1
X

ai (g)al−i (h)

i=1
l−1
X

k i (d − k)l−i

i=1
`

≤ ((d − k) + k)
= d` .

Next consider the case when f = gh, meaning the root of the tree corresponding to f is
an AND operation. Observe that
|a` (f )| =

l−1
X

ai (g)al−i (h) ≤

i=1

l−1
X

k i (d − k)l−i < d` .

i=1


We observe a relationship between the polynomial of a tree and the polynomial of its
complement. We define the complement of the AND/OR tree T to be the tree obtained from
T by switching the operation at each node.

9

Lemma 2.3 Let A and B be complementary AND/OR trees and let fA and fB be the corresponding polynomials. Then fB (1 − p) = 1 − fA (p) for all 0 < p < 1.
Proof. Proceed by induction on the number of leaves of the tree. For a tree on one leaf,
the statement holds trivially. Without loss of generality, assume that the root of tree A
is an AND operation. Then fA (x) = a1 (x)a2 (x) and fB (x) = b1 (x) + b2 (x) − b1 (x)b2 (x)
where the trees corresponding to a1 and b1 are complements and the trees corresponding to
a2 and b2 are also complements. By the inductive hypothesis, a1 (p) = 1 − b1 (1 − p) and
a2 (p) = 1 − b2 (1 − p). Observe
1 − fA (p) = 1 − a1 (p)a2 (p)
= 1 − (1 − b1 (1 − p))(1 − b2 (1 − p))
= b1 (1 − p) + b2 (1 − p) − b1 (1 − p)b2 (1 − p)
= fB (1 − p).

Pn

Let fA be a polynomial achievable through convex combinations,
fA = i=1 λi fAi . Let
Pn
Ai and Bi be complementary AND/OR trees. Let fB = i=1 λi fBi . We say that fA and fB
are complementary polynomials.
Corollary 2.4 Let fA and fB be complementary polynomials. Then
1. For all 0 < p < 1, fB (1 − p) = 1 − fA (p)
2. If p is a fixed point of fA then 1 − p is a fixed point of fB
(k)

(k)

3. For all 0 < p < 1, fB (1 − p) = 1 − fA (p).
Definition 2.5 We say that t in an attractive fixed point of f if there exists ε > 0 such
that for all x ∈ [0, 1] such that |x − t| < ε, |t − f (f (x))| < |t − f (x)|. We say that t in
a non-attractive fixed point of f if there exists ε > 0 such that for all x ∈ [0, 1] such that
|x − t| < ε, |t − f (f (x))| > |t − f (x)|. Equivalently, t is a non-attractive fixed point if
f 0 (t) > 1, and an attractive fixed point if f 0 (t) < 1.
For the function illustrated in Figure 3, 0 and 1 are attractive fixed points and 1/2 is a nonattractive fixed point. For the function illustrated in Figure 4, 0 and 1 are non-attractive
fixed points and 1/2 is an attractive fixed point.
Lemma 2.6 Let f ∈ A be an achievable polynomial corresponding to a tree T with at least
one AND or OR operation. Then
1. The function f has an attractive fixed point at 0, a non-attractive fixed point at 1, and
no fixed points in (0, 1) if and only if there is a path from the root to a leaf in T in
which each node represents an AND operation.
2. The function f has an non-attractive fixed point at 0, an attractive fixed point at 1,
and no fixed points in (0, 1) if and only if there is a path from the root to a leaf in T
in which each node represents an OR operation.
10

3. The function f has attractive fixed points at 0 and 1, and precisely one non-attractive
fixed point α in (0, 1) if and only if there is no path from the root to a leaf in T in
which each node represents an AND operation and there is no path from the root to a
leaf in T in which each node represents an OR operation. Moreover, α is irrational.
[Moore and Shannon, 1956] prove a stronger version of (3). They show that any polynomial
f corresponding to an arbitrary circuit of AND and OR operations can have at most one
fixed point on (0, 1). We present a similar version of their argument for the setting when f
is corresponds to a tree.
Proof. It suffices to prove necessity for each statement.
(1) Let p2 = a1 , . . . , ak = f be the polynomials computed by the nodes of some AND
path. Since each ai corresponds to a tree with an AND root, ai = ai−1 gi where gi is the
polynomial corresponding
to the subtree of the node that does not intersect that AND path.
Qk
2
Thus, f = ak = p
i=2 gi . For 0 < p < 1,
k
Y
f (p)
=p
gi (p) < p < 1.
p
i=2

Therefore, f has no fixed points on (0, 1). To see that 0 is an attractive fixed point, note
that f (p) < p for any p ∈ (0, 1), Thus, f (f (p)) < f (p). Similarly, 1 is a non-attractive fixed
point because 1 − f (f (p)) > 1 − f (p) for all p ∈ (0, 1).
(2) Follows from (1) and Lemma 2.3.
(3) First we show that if the tree has no path of OR operations, then the corresponding
polynomial f will not have a linear term by proving the contrapositive. The root of a tree
corresponding to a polynomial with a linear term must be an OR operation since if the root
were an AND operation, the corresponding polynomial would the product of two non-zero
polynomials with no constant terms. Given that the root has a linear term and computes
g + h − gh for some achievable polynomials g and h, it follows that g or h has a linear term.
We iteratively apply this argument for the appropriate subtrees and conclude that there is
a path of OR operations.
Since f has no linear term, for small ε, f (ε) = O(ε2 ). Therefore, there is an ε neighborhood around zero such that f (p) < p. It follows that f (f (p)) < f (p), so 0 is an attractive
fixed point. The fact that 1 is also an attractive fixed point follows from Lemma 2.3. Since
there is no AND path for T , there is no OR path in the complementary tree. Thus, 0 is an
attractive fixed point of f c , so 1 is an attractive fixed point of f .
Next, we show that there exists some fixed point of f on (0, 1). Since 0 and 1 are
attractive fixed points, there exists ε1 , ε2 > 0 such that f (ε1 ) < ε1 and f (1 − ε2 ) > 1 − ε2 .
By the intermediate value theorem, f must cross the line y = x. Thus, there exists some
α ∈ (ε1 , 1 − ε2 ) ⊂ (0, 1) such that f (α) = α.
To prove that α is a non-attractive fixed point and that α is the unique fixed point on
(0, 1), it suffices to show that for any fixed point α ∈ (0, 1), f 0 (α) ≥ 1. We use an argument
(p))
for p ∈ (0, 1). Proceed by
inspired by [Moore and Shannon, 1956] to prove f 0 (p) ≥ f (p)(1−f
p(1−p)
induction on the size of the tree. Clearly, the statement holds for the leaves which compute

11

the polynomial p. Let g, h be the polynomials associated to the two subtrees joined at the
root of T . If the root is an AND operation, f = gh, and we have
f 0 = gh0 + g 0 h ≥

gh(2 − g − h)
gh(1 − gh)
f (1 − f )
gh(1 − h) hg(1 − g)
+
=
≥
=
.
p(1 − p)
p(1 − p)
p(1 − p)
p(1 − p)
p(1 − p)

The final inequality uses the fact that since (1 − g)(1 − h) ≥ 0, 2 − g − h ≥ 1 − gh. If the
root is an OR operation, f = g + h − gh and we have
f 0 = g 0 + h0 − gh0 − g 0 h = h0 (1 − g) + g 0 (1 − h) ≥

=

h(1 − h)(1 − g) + g(1 − g)(1 − h)
p(1 − p)

(1 − h − g + gh)(g + h)
(1 − h − g + gh)(g + h − gh)
f (1 − f )
≥
=
.
p(1 − p)
p(1 − p)
p(1 − p)

Finally, we prove that α is irrational. Suppose for contradiction that α = m/n where
m, n ∈ Z and are relatively prime. Let k + 3 be the degree of f . We may write
k



X
m
m
m
f (p) = g(p)(1 − p) p −
p=
ai pi+1 −p2 + 1 +
p−
,
n
n
n
i=0

P
where g(p) = ki=0 ai pi and ak 6= 0. Let bi be the coefficient of the term pi in f . Since f is
achievable, by Lemma 2.1, each bi ∈ Z, b0 = 0, and bk+3 is 1 or −1. We show by induction
−m
that for all i ai = nti for some ti ∈ Z.
note
 First −m
 that b1 = n a0 . Since b1 ∈ Z, a0 = nt0
m
where t0 ∈ Z. Similarly,
b2 = 1 + n a0 + n a1 , so a1 = nt1 for some t1 ∈ Z. We have

−m
b3 = −a0 + 1 + m
a
+
a2 , so a2 = nt2 for some t1 ∈ Z. Assume that a` = nt` for all
1
n
n
` < j − 1. We have



−m
m
aj−2 +
aj−1 .
bj = −aj−3 + 1 +
n
n

Since aj−3 and aj−2 are integer multiples of n, it follows that −aj−3 + 1 + m
aj−2 is integer.
n
Since bj is integer, aj−1 = tj−1 n for some tj−1 ∈ Z. We have shown that a0 , . . . ak are integer
multiples of n. We have bk+3 = −ak . Since ak is a non-zero integer multiple of n, it follows
that bk+3 is not -1 or 1, a contradiction.

Finally, we make some observations about the polynomials associated with the specific
family of trees we use in many of our constructions.
Definition 2.7 Let Ak be a tree on 2k leaves that computes (x1 ∨ x2 ∨ · · · ∨ xk ) ∧ (xk+1 ∨
xk+2 ∨ · · · ∨ x2k ). Let Bk be a tree on 2k leaves that computes (x1 ∧ x2 ∧ · · · ∧ xk ) ∨ (xk+1 ∧
xk+2 ∧ · · · ∧ x2k ).
Lemma 2.8 Let fAk and fBk be the polynomials corresponding
 to Ak and Bk respectively.

1
1
Then fAk has a unique fixed point in the interval k2 , k(k−1) and fBk has a fixed point in


1
, 1 − k12 .
the interval 1 − k(k−1)
The proof of Lemma 2.8 will use the following elementary inequality.
12

Lemma 2.9 For x ∈ (0, 1), and any integer k ≥ 0, 1 − kx < (1 − x)k < 1 − kx +

k
2

 2
x.

Proof.[of
Lemma
 2.8.] It suffices to show that g(x) = fAk (x) − x has a zero on the inter
1
1
val k2 , k(k−1) . We will show that g(1/k 2 ) < 0 and g(1/(k(k − 1))) > 0 and apply the
intermediate value theorem. Using Lemma 2.9, for x = 1/k 2 ,
(1 − (1 − x)k )2 − x < (1 − (1 − kx))2 − x = k 2 x2 − x = 0.
Similarly, for x = 1/(k(k − 1)),
2
k(k − 1)x2
(1 − (1 − x) ) − x > 1 − 1 − kx +
−x
2

2
1
1
1
=
−
−
k − 1 2k(k − 1)
k(k − 1)

2
1
1
1
=
1−
−
2
(k − 1)
2k
k(k − 1)


1
1
1
1
1
=
> 0.
1 − + 2 − (1 − ) = 2
2
(k − 1)
k 4k
k
4k (k − 1)2

1
It follows from Corollary 2.4 that fBk has a fixed point in the interval 1 − k(k−1)
,1 −
Uniqueness follows from Lemma 2.10.
k 2





1
k2



.


Lemma 2.10 Let 0 ≤ α ≤ 1 and f = αfBk + (1 − α)fBk+1 where fBk is the polynomial
f (p)−p
corresponding to Bk . Let t be the fixed point of f in (0, 1). Then g(p) = p(1−p)(p−t)
≥ 1t for
all p ∈ [0, 1].
Proof. By definition
g(p) =

α(1 − 2pk−1 + p2k−1 ) + (1 − α)(1 − 2pk + p2k+1 )
f (p) − p
=
.
p(1 − p)(p − t)
(1 − p)(t − p)

Since 1 and t are fixed points of f (p), (1 − p) and (t − p) divide f (p) − p. Therefore, we
may write g = a0 + a1 p · · · + a2k−1 p2k−1 polynomial. We claim that all coefficients of g are
positive. Note that
(t − p)

2k−1
X

ai p i =

i=0

α(1 + p · · · + pk−2 − pk−1 − pk · · · − p2k−2 ) + (1 − α)(1 + p · · · + pk−1 − pk − pk+1 · · · − p2k ).

13

Observe
ai =
ai =
ai =
ai =
ai =

1
t
ai−1 + 1
t
ai−1 + 1 − 2α
t
ai−1 − 1
t
ai−1 − (1 − α)
t

for i = 0
for 1 ≤ i ≤ k − 2
for i = k − 1
for k ≤ i ≤ 2k − 2
for i = 2k − 1.

Note that 1t = a0 < a1 < · · · < ak−2 , so ai > 0 for all 0 ≤ i ≤ k − 2. Next observe
that a2k−1 = 1 − α since comparing the coefficients of the p2k terms on both sides gives
−a2k−1 = −(1 − α). It follows that a2k−2 = t(1 − α) + 1 − α. For all k ≤ i ≤ 2k − 2,
ai−1 = tai + 1. Therefore ai > 0 for all k − 1 ≤ i ≤ 2k − 3.
Since all coefficients of g are positive, all derivatives are increasing. In particular the
first derivative of g(p) is increasing on the interval (0, 1). Therefore g(p) ≥ g(0) = 1t for all
p ∈ [0, 1].

Lemma 2.11 Let fAk and fBk be the polynomials corresponding to Ak and Bk respectively.
For t ≤ 2 − φ, there exists
 some kand α such that fA = αfAk + (1 − α)fAk+1 has fixed point
t−fA (p)
. Similarly, for t ≥ φ − 1, there exists some k and α such
t. Moreover, t−p ≥ 1 + p(1−p)
t


B (p)
that fB = αfBk + (1 − α)fBk+1 has fixed point t. Moreover, t−ft−p
≥ 1 + p(1−p)
.
t
Proof. By Corollary 2.4, it suffices to prove the theorem for
 φ − 1 ≤ t < 1. By Lemma 2.8,
1
, 1 − k12 . Let bk be the fixed point fBk .
fBk has a single fixed point in the range 1 − k(k−1)
Note that for 0 < p < 1,
fBk+1 (p) < fBk (p).
It follows that bk < bk+1 . We obtain an increasing sequence φ − 1 = b2 , b3 , b4 . . . that
converges to 1. Let k be the value for which bk ≤ t < bk+1 . Let f = αfBk + (1 − α)fBk+1
where α is chosen so that f has fixed point

 t.
f (p)−p
Next we show that t − f (p) ≥ (t − p) 1 + p(1−p)
. By Lemma 2.10, g(p) = p(1−p)(p−t)
≥ 1t
t
for 0 ≤ p ≤ 1. Therefore


p(1 − p)
t − f (p) = (t − p)(1 + p(1 − p)g(p)) ≥ (t − p) 1 +
.
t


14

3

Convergence of iterative trees to threshold functions

In the previous section, we showed that if the width of each level is infinite, then items at level
(k)
k of an iterative tree evaluate to 1 with probability fC (p) when each input is independently
set to 1 with probability p. In this section, we demonstrate ways of selecting C so that
(k)
fC (p) converges to a t-threshold function.
By an abuse of notation, we say that f (p) converges to a t-threshold function if

0≤p<t
 0
(k)
1
t<p≤1
lim f (p) =
k→∞

p
p = t.
Moreover, we say that f converges quadratically to a t-threshold function if the corresponding
iterative construction exhibits quadratic convergence. The function depicted in Figure 3
converges to a 1/2-threshold function.
1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

Figure 3: A function f that converges to a 1/2-threshold function.
f (p), f (5) (p), f (10) (p), f (30) (p).

0.4

0.6

0.8

1.0

Left to right:

We now prove that the construction described in Theorem 1.3 converges to a t-threshold
function.
Proof. [of Theorem 1.3.] Let fR be the polynomial that describes the iterative construction
in which T1 and T2 are selected with probability t and 1 − t respectively. Since, fT1 (p) =
2p2 − p3 and fT2 (p) = p + p2 − p3 ,
fR (p) = tfT1 (p) + (1 − t)fT2 (p) = (1 − t)p + (1 + t)p2 − p3 .
Since fR (p) − p = p(1 − p)(p − t), the fixed points of fR are 0, t, and 1. We claim that fR
exhibits linear convergence to a t-threshold function.
Let p be the probability that an input item fires. It suffices to consider the case when
p ≤ t−1/n. By Corollary 2.4, convergence to 1 for p ≥ t+ n1 follows from the complementary
construction.
First we show that the probability an item at level Ω(log n) fires is less than 2t . By
definition p − f (p) = p(1 − p)(t − p). Observe that for t/2 < p ≤ t − 1/n
t − f (p)
p − f (p)
t(1 − t)
=1+
= 1 + p(1 − t) ≥ 1 +
.
t−p
t−p
2

15

It follows that for all ` either f (`) (p) < 2t or
`
`


t(1 − t)
t(1 − t) 1
(`)
.
t − f (p) ≥ 1 +
(t − p) ≥ 1 +
2
2
n
For ` = log1+ t(1−t) tn
, f ` (p) < 2t .
2
2
Next, we show that at Ω(k) additional levels, the probability an items fires is less than
−k
2 . For p < 2t ,
 


t t
.
f (p) = p(1 − p)(p − t) + p = p(1 − (1 − p)(t − p)) ≤ p 1 − 1 −
2 2
It follows



 `


 `
t t
t t
t
f (p) < 1 − 1 −
p< 1− 1−
.
2 2
2 2 2
(l)

1
Thus, for l = log(1−(1− t ) t ) t2k−1
, f ` (p) < 2−k . We have shown that when the input items
2 2
fire with probability p ≤ t − 1/n, items level Ω(k + log n) will evaluate to 1 with probability
less than 2−k .


3.1

Quadratic convergence from iterative trees with small building blocks

In this section we show that using trees with four or five leaves as building blocks, we
can construct an iterative tree that converges quadratically to a t-threshold function for
restricted values of t. We begin with a lemma that provides sufficient conditions for quadratic
convergence.
Lemma 3.1 Let f be a function corresponding to an iterative construction on n inputs that
satisfies the following conditions:
• On the interval [0, 1], f has precisely three fixed points: 0, t, and 1.
• (Linear Divergence) There exists constants u, v satisfying 0 < u < t and t < v < 1 and
constants c1 , c2 > 1 such that
1. t − f (p) ≥ c1 (t − p) for p ∈ [u, t − n1 ], and
2. f (p) − t ≥ c2 (p − t) for p ∈ [t + n1 , v].
• (Quadratic Convergence) For the constants u, v as above, there exists constants c3 , c4
such that c3 u < 1 and c4 (1 − v) < 1 and
1. f (p) < c3 p2 for p ∈ (0, u), and
2. 1 − f (p) < c4 (1 − p)2 for p ∈ (v, 1).
Then f exhibits quadratic convergence to a t-threshold function, meaning items at level
Ω(log n+log k) of the corresponding infinite width iterative construction compute a t-threshold
function with probability at least 1 − 2−k .
16

Proof. Let p be the probability an input item fires. First we consider the case when p ≤ t− n1 .
By the linear divergence assumption, t − f (p) ≥ c1 (t − p) for p ∈ [u, t − n1 ]. It follows that
f (`) (p) < u or
t − f (`) (p) ≥ c`1 (t − p) ≥ c`1 (1/n).
Thus for ` = logc1 n(t − u), f (`) (p) ≤ u. Therefore, level Ω(log n) items fire with probability
at most u. Next we show that given a level in which items fire with probability at most
u, the items at Ω(log k) levels higher in the iterative tree fire with probability at most 2−k .
Let p0 be the probability an item fires at the first level for which the probability an item
fires is below u. By the quadratic convergence assumption, f (p0 ) < c3 (p0 )2 for p0 ∈ (0, u).
It follows that for ` > log2 (logc3 (1/2)) + log2 (k) − log2 (1 + logc3 (t − 1/n)) + 1, f (`) (p0 ) ≤
`
`
`
`
c2 −1 (p0 )2 ≤ c2 −1 u2 < 2−k . We have shown that in expectation items at Ω(log n + log k)
fire with probability less than 2−k when p ≤ t − n1 . A similar argument applies for p ≥ t + n1 .

Remark 3.2 Let f be a function corresponding to an iterative construction with fixed point
t. Then there exists u and v for which the quadratic convergence condition of Lemma 3.1
holds if and only if f 0 (0) = 0 and f 0 (1) = 0.
Proof. Quadratic convergence to 0 is observed if and only if there exists some positive
constant u sufficiently close to 0 for which all x < u, f (x) = O(x2 ). Writing f (x) according to
its Taylor series expansion about 0 implies that such behavior occurs if and only if f 0 (0) = 0.
Similarly, the observing the Taylor series expansion about 1 allows us to conclude that
quadratic convergence to 1 is observed if and only if f 0 (1) = 0.

Next, we prove that the construction given in Theorem 1.5A converges quadratically to
a t- threshold function.
Proof. [of Theorem 1.5A.] Since 2 − φ ≤ t ≤ φ − 1, 0 ≤ α(t) ≤ 1 and the probability
distribution R is well-defined. By construction, fF1 (p) = 4p2 −4p3 +p4 and fF2 (p) = 2p2 −p4 ,
so
1 − 2t 4
1 + t − 3t2 2 −2 + 2t + 2t2 3
p +
p +
p.
fR (p) =
t(1 − t)
t(1 − t)
t(1 − t)
We apply Lemma 3.1. First note that 0, t, and 1 are fixed points. Let p be the fraction of
input items firing. It suffices to show convergence to 0 when p ≤ t − n1 . By Corollary 2.4,
convergence to 1 for p ≥ t + n1 follows from the complementary construction.
f (p)−p
First we show linear divergence from t. Let g(p) = p(1−p)(p−t)
= 1t + p(2t−1)
. We claim
(1−t)t
1
1
1
1
2t−1
1
g(p) ≥ 1 for 0 ≤ p ≤ 1. If t ≥ 2 , then g(p) ≥ t > 1. If t < 2 , then g(p) ≥ t + (1−t)t = 1−t
≥ 1.
Observe that for any constant 0 < u < t and u < p ≤ t − 1/n
t − f (p) = t − (p + p(1 − p)(p − t)g(p)) ≥ (t − p) (1 + p(1 − p)) ≥ (t − p) (1 + u(1 − t)) .
Thus c1 = 1 + u(1 − t) satisfies the first linear divergence condition.
Next, we show quadratic convergence. Let u = 1/5. Observe that
f (p) ≤ 4p2 − 4p3 + p4 < 4p2 .
17

Since (1/5)4 < 1, taking c3 = 4 satisfies the first condition of quadratic convergence. Thus,
we may apply Lemma 3.1 to conclude that items at level Ω(log n + log k) in the limit of the
iterative construction compute a t-threshold function with probability at least 1 − 2−k .
It remains to show that no construction using trees with four leaves will yield quadratic
convergence to a t-threshold function for t outside the range 2 − φ ≤ t ≤ φ − 1. A t-threshold
function with quadratic convergence must satisfy the following five constraints: (i) f (0) = 0,
(ii) f (1) = 1, (iii) f (t) = t, (iv) f 0 (0) = 0, (v) f 0 (1) = 0. Solving these equations gives the
function
1 − 2t 4
1 + t − 3t2 2 −2 + 2t + 2t2 3
p +
p +
p.
f (p) =
t(1 − t)
t(1 − t)
t(1 − t)
Suppose that f can realized by a convex combination of degree four polynomials. Then the
leading coefficient of f must be between −1 and 1 since all achievable polynomials have
1−2t
leading coefficient −1 or 1. Thus, 0 ≤ t(1−t)
≤ 1, which implies that 2 − φ ≤ t ≤ φ − 1. 
Proof. [of Theorem 1.5B.] By construction fV1 (p) = p2 + p3 − p5 and fV2 (p) = 6p2 − 9p3 +
5p4 − p5 , so
fR (p) =

1 + t − 2t2 − t3 2 −2 + t + t2 + 2t3 3 1 − t2 − t3 4
p +
p +
p − p5 .
t(1 − t)
t(1 − t)
t(1 − t)

We apply Lemma 3.1. First note that 0, t, and 1 are fixed points. Let p be the fraction of
input items firing. It show convergence to 0 when p ≤ t − n1 . By Corollary 2.4, convergence
to 1 for p ≥ t + n1 follows from the complementary construction.
2 +t−1
f (p)−p
First we show linear divergence from t. Let g(p) = p(1−p)(p−t)
= 1t − tt(t−1)
p + p2 =
1
t

2

2

+t−1
+t−1
+ p(− tt(t−1)
+ p). We claim that g(p) ≥ 1 for 0 ≤ p ≤ 1. If − tt(t−1)
+ p ≥ 0, then
2

2

+t−1
+t−1
1
g(p) ≥ 1t ≥ 1. If − tt(t−1)
+ p < 0, then g(p) ≥ 1t − tt(t−1)
+ 1 = 1−t
≥ 1. Thus as in the
proof of part A, c1 = 1 + u(1 − t) satisfies the first linear divergence condition. Next we show
quadratic convergence. Let u = 1/7. Note that

f (p) ≤ p2 (6 − 9p + 5p2 − p3 ) < 6p2 .
Since 6(1/7) < 1, taking c3 = 6 satisfies the first condition of quadratic convergence. Thus,
we may apply Lemma 3.1 to conclude that in expectation items at level Ω(log n + log k) of
the iterative construction compute a t-threshold function with probability at least 1 − 2−k .
It remains to show that no construction using trees with five leaves will yield quadratic
convergence to a t-threshold function for t outside the range 0.26 . t . 0.74. A t-threshold
function with quadratic convergence must satisfy the following five constraints: (i) f (0) = 0,
(ii) f (1) = 1, (iii) f (t) = t, (iv) f 0 (0) = 0, (v) f 0 (1) = 0. Such a function will have the form:
zd,t (p) =

1 + t − (3 + d)t2 + dt3 2 −2 + (2 + d)t + (2 + d)t2 − 2dt3 3
p +
p
(1 − t)t
(1 − t)t
1 − (2 + 2d)t + dt2 + dt3 4
+
p + dp5 .
(1 − t)t

Since each achievable polynomial has leading coefficient −1 or 1, if zd,t (p) can written as a
convex combination of achievable polynomials of degree five, then
zd,t (p) = βz−1,t (p) + (d + β)z1,t (p),
18

where z−1,t (p) and z1,t (p) are convex combinations of achievable polynomials of degree five
with leading coefficient −1 and 1 respectively and 0 ≤ β ≤ 1. Thus, it suffices to determine
the values of t for which z−1,t (p) is achievable through convex combinations and the values
of t for which z1,t (p) is achievable through convex combinations.
2 +t3
. If the function z−1,t (p) is achievable through convex
Claim: Let α(t) = −1+5t−4t
5t(t−1)
combinations then 0 ≤ α(t) ≤ 1, meaning 0.26 . t . 0.74.
Notice that achievable polynomials of degree five with leading coefficient −1 have coefficient a3 ≥ −9 (see Table 1). It follows that
−2 + t + t2 + 2t3
≥ −9
t(1 − t)

and 2(−1 + 5t − 4t2 + t3 ) ≥ 0,

so α(t) ≥ 0. Next, note that the coefficient a4 of z−1,t (p) must be non-negative (see Table
1). It follows that
1 − t2 − t3
≥ 0 and
t(1 − t)

− 1 + 5t − 4t2 + t3 ≤ 5t − 5t2 ,

so α(t) ≤ 1.
Claim: Let γ(t) = 1−2t−t2 +t3 and β(t) = 1−3t2 +t3 . If the function z1,t (p) is achievable
through convex combinations, then γ(t) ≤ 0 and β(t) ≥ 0, meaning .445 . t . .653
Assume z−1,t (p) is achievable through convex combinations. Notice that for degree five
achievable polynomials with a1 = 0 and a5 = 1, −4 ≤ a4 ≤ −2. It follows that
−4 ≤

1 − 4t + t2 + t3
≤ −2,
(1 − t)t

so γ(t) ≤ 0 and β(t) ≥ 0.
Now consider t . 0.26 or t & 0.74. By the above claims, z−1,t (p) and z1,t (p) are not achievable through convex combinations. It follows that zd,t (p) is not achievable through convex
combinations, meaning no construction on trees with five leaves that converges quadratically
to a t-threshold function for t . 0.26 or t & 0.74.

Using a similar technique as in the proof above, it is possible to show that the analogous
constructions on six and seven leaves yield iterative constructions that converge quadratically
to threshold functions for thresholds in the ranges 0.15 . t . 0.85 and 0.11 . t . 0.89
respectively. However, it is not possible to generalize such a construction beyond this point.
Instead, we observe the emergence of a staircase functions, which will be discussed in Example
4.4.

3.2

Quadratic convergence for arbitrary thresholds.

In this section we show that as t approaches 0 or 1, increasingly large building blocks trees are
needed to construct an iterative tree that converges quadratically to a t- threshold function.
Further, we give a construction that exhibits quadratic convergence for arbitrary thresholds
near 0 and 1. We begin by proving Theorem 1.6, which can be restated as follows: Let f be
19

an achievable polynomial with fixed points 0, t, and 1 that exhibits quadratic convergence
to a t-threshold function. Then, f has degree at least √12s where s = min{t, 1 − t}.
Proof. [of Theorem 1.6.] Let f be an achievable polynomial with fixed points 0, t, and
1 that exhibits quadratic convergence. Then for ε sufficiently small, f (ε) = O(ε2 ), which
1
implies a1 = 0. For x < 2d
, we have


1
2
2
d
2 2
3 3
d d
2 2
< 2d2 x2 .
f (x) = a2 x + a3 x + · · · + ad x ≤ d x + d x + . . . d x < d x
1 − dx
Since t is a fixed point of f , f (t) = t. Thus, t < 2d2 t2 . It follows that d > √12t . By
Lemma 2.3, if there exists an achievable polynomial with fixed point t, then there also exists
a complementary achievable polynomial with fixed point 1 − t. Thus, d > √ 1 .

2(1−t)

We now prove that a nearly matching iterative construction exists. To achieve quadratic
convergence to thresholds near 0 or 1, we average trees of the form Ak and Ak+1 or Bk and
Bk+1 respectively.
Proof. [of Theorem 1.7.] By Corollary 2.4, it suffices to prove the theorem for 1 − φ ≤ t < 1.
The complement of a construction that achieves quadratic convergence to a t-threshold
function yields quadratic convergence for to a (1 − t)-threshold function. By Lemma 2.11,
(p)
≥
there exists k and α such that f = αfBk + (1 − α)fBk+1 has fixed point t. Moreover, t−f
t−p


p(1−p)
1+ t
.
We apply Lemma 3.1 to prove that f converges to a t-threshold function. Let p be the
probability an input item is on. First suppose that p ≤ t − n1 . We show linear divergence
away from t. For any constant 0 < u < t, and u ≤ p ≤ t − n1 by Lemma 2.11 we have




p(1 − p)
u(1 − t)
t − f (p) ≥ (t − p) 1 +
≥ (t − p) 1 +
.
t
t
Thus, c1 = 1 + u(1−t)
is a valid choice for c1 in Lemma 3.1.
t
1
is a valid starting point for quadratic convergence
Next, we claim that u = 1 − k−1
2
towards 0. We write f (p) = p (αdk (p) + (1 − α)dk+1 (p)) where dk (p) = 2pk−2 − p2k−2 . Let
d(p) = αdk (p) + (1 − α)dk+1 (p). Note that d(p) is increasing on the interval (0, u) since each
dk increases on this interval. For p < u,
2k − 4
= u > uk > pk .
2k − 2
It follows that d0k (p) = pk−3 ((2k − 4) − (2k − 2)pk ) > 0. Thus, dk is increasing on the interval
(0, u). Thus, c3 = d(u) is a valid choice for c3 in Lemma 3.1.
It remains to show that for p ≥ t + n1 we observe linear divergence from t then quadratic
convergence to 1. We show linear divergence away from t. For any constant t < v < 1, and
t + n1 ≤ p ≤ 1 by Lemma 2.11 we have




p(1 − p)
t(1 − v)
f (p) − t ≥ (p − t) 1 +
≥ (p − t) 1 +
.
t
t
20

Thus, c2 = 1 + t(1−v)
is a valid choice for c2 in Lemma 3.1.
t
1
We claim that v > 1 − 8(k+1)
2 is a valid starting point for quadratic convergence to 1. By
Corollary 2.4, fAk (1 − p) = 1 − fBk (p). It follows
1 − f (p) = α − αfBk (p) + (1 − α) − (1 − α)fBk+1 (p) = αfAk (1 − p) + (1 − α)fAk+1 (1 − p).
Recall from the proof of Theorem 1.6, f (x) < 2dx2 where d is the degree of x. Therefore,
fAk (1 − p) < 8k 2 (1 − p)2 < 8(k + 1)2 (1 − p)2 and fAk+1 (1 − p) < 8(k + 1)2 (1 − p)2 .
Since (1 − v)8(k + 1)2 < 1, c4 = 8(k + 1)2 is a valid choice for c4 in Lemma 3.1.

4



Convergence of iterative constructions to staircase
functions

In this section, we explore the possible functions that can be achieved by sampling from the
high-level items of iterative constructions with no restrictions on the size of building block
trees.
Definition 4.1 The function f is a staircase function if f (x) = pi on the interval (ai , ai+1 )
where a0 = 0 < a1 < a2 < · · · < ak < ak+1 = 1, 0 = p0 < p1 < p2 < · · · < pk−1 < pk = 1.
We will show in Theorem 4.10 that any staircase function in which each step intersects the
line y = x, or more precisely ai ≤ pi ≤ ai+1 for all 0 ≤ i ≤ k, can be approximated by a
high-level of an iterative tree.
This result may seem to suggest that the high-level items of these constructions are
pseudorandom. However, this is not the case. The output of a high-level item is highly
influenced by which of tree it is the root of. The distribution of items firing at a given
high-level behaves according to the staircase function, rather than each item individually
behaving according to the staircase function.
We begin by giving a couple of examples of staircase functions arising from probability
distributions of small trees. The first example is a one step staircase.
Example 4.2 Consider the iterative construction that selects a tree that computes A∧B∧C
with probability α and a tree that computes A ∨ B ∨ C with probability 1 − α. Let f (p) =
α(1 − (1 − p)3 ) + (1 − α)p3 be the corresponding polynomial. For α ∈ (1/3, 2/3), f converges
to an (3α − 1) one step staircase function, i.e. takes value 3α − 1 on (0, 1). For α = 1/2 and
inputs in which the fraction of inputs firing is not 0 or 1, approximately half the high-level
items will fire. Figure 4 illustrates f for α = 1/2.

Lemma 4.3 Consider the iterative construction that selects a tree that computes A ∧ B ∧ C
with probability α and a tree that computes A ∨ B ∨ C with probability 1 − α where α ∈
(1/3, 2/3). Let f (p) = α(1 − (1 − p)3 ) + (1 − α)p3 be the corresponding polynomial. Then
3α − 1 is the only fixed point of f on (0, 1) and it is an attractive fixed point.
21

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

Figure 4: An iterative construction for the above function converges a 1/2 one step staircase
function. Left to right: f (p), f (5) (p), f (10) (p), f (30) (p).
Proof. The only fixed points of f (p) are the roots of f (p) − p, which are 0, 1, 3α − 1. To
prove that 3α − 1 is an attractive fixed point, we show that f 0 (3α − 1) < 1. We compute
f 0 (p) = 3α(1 − p)2 + 3(1 − α)p2 . For α ∈ (1/3, 2/3), we have
f 0 (3α − 1) = 3 − 9α + 9α2 < 1.

We remark that roughly log(1/δ) + log(1/ε) levels are needed (and suffice) to get within
δ of α = 1/2 where ε is the distance of the input from 1/2. We omit the proof, which is
similar to other proofs of finite bounds in this paper.
In the above construction, a randomly sampled high-level item fires with probability
approximately half. However, whether a fixed high-level item fires is not pseudorandom.
Given that half of the items at level k − 1 fire, an item at level k that is the root of an
A ∧ B ∧ C building block tree fires with probability 1/8. An item at level k that is the root
of a A ∨ B ∨ C building block tree fires with probability 7/8.
Another simple example of a staircase function is the generalization of the construction
given in Theorem 1.5.
Example 4.4 For k ≥ 4, the function h = (fAk + fBk )/2 converges to a three step staircase
function. The function h has a non-attractive fixed point s ∈ (0, 1/2), a non-attractive
fixed point t ∈ (1/2, 1), and an attractive fixed point at 1/2. Figure 5 illustrates h6 (p).
Therefore, for inputs in the interval (s, t), approximately half the high-level items return 0
and half return 1. For inputs in the intervals [0, s] and [t, 1], high-level items return 0 and 1
respectively with high probability.

Lemma 4.5 Let k ≥ 4. Consider an iterative construction in which Ak and Bk are each
selected with probability 1/2. Let h = (fAk + fBk )/2 be the corresponding polynomial. Then
1/2 is an attractive fixed point of h.
Proof. Let h = (fAk + fBk )/2. It suffices to show h0 (1/2) < 1 for k ≥ 4. We compute
h0 (p) = k pk−1 + (1 − p)k−1 − k p2k−1 + (1 − p)2k−1 . It follows for k ≥ 4 that

h0 (1/2) = k 2−(k−2) − k2−(2k−2) =

k
2k−2


1 − 2−k < 1.


22

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

Figure 5: For k ≥ 4, the function (fAk + fBk )/2 converges to a three step staircase function.
Left to right: f (p), f (5) (p), f (10) (p), f (30) (p).
Finally, we show that it is possible to approximate any staircase function. The proof will
rely on Lemma 4.6 and Lemma 4.7, which describe the scope of achievable polynomials for
a single tree.
Lemma 4.6 Let t be a fixed point of some achievable polynomial f with attractive fixed
points 0 and 1, 0 < t < 1. Then, for any δ, ε > 0 there exists an achievable polynomial g
such that f (x) < δ for x ∈ [0, t − ε] and f (x) > 1 − δ for x ∈ [t + ε, 1].
Proof. First we claim that if f is achievable, then f (k) is also achievable. Let f be the
polynomial corresponding to a tree T . Define T 1 to be the tree T modified so that each of
the leaves is replaced with a copy of T . Let T k be the tree T k−1 modified so that each of the
leaves is replaced with a copy of T . Note that f (k) is the polynomial for T k .
Let f be the polynomial for which t is a fixed point. It suffices to show that there exists
some k such that f (k) (x) < δ for x ∈ [0, t − ε] and f (k) (x) > 1 − δ for x ∈ [t + ε, 1]. Since
t is the only fixed point and 0 is an attractive fixed point, for p ∈ [δ, t − ε], f (p) < p. Let
m = minp∈[δ,t−ε] p − f (p). Then for all `, f (`) (p) ≤ t − ε − `m or f (`) (p) < δ. Let x ∈ [0, t − ε].
e, f (k) (x) ≤ f (k) (t − ε) ≤ δ. A similar argument proves the case when
Then for k = d t−ε
m
x ∈ [t + ε, 1].

The following lemma says that with a single tree, the set of achievable fixed points is dense
in (0, 1). A weaker version of this lemma in which the building blocks of the constructions
are arbitrary circuits rather than trees is given by [Moore and Shannon, 1956]. Our proof is
inspired by their argument.
Lemma 4.7 The set of fixed points of achievable polynomials is dense in [0, 1].
The proof will rely on the following claims.
Claim 4.8 Let f, g be achievable polynomials such that g ≤ p and f has fixed point r,
0 < r < 1. Let x = g −1 (r). Then for all sufficiently small ε > 0, there exists k such that the
fixed point of f (k) (g(p)) is in (x, x + ε).
Proof. Note that for any k, f (k) (g(x)) = r < x. Therefore, to prove that there is a fixed
point in (x, x + ε), it suffices to show that f (k) (g(x + ε)) > x + ε. Since g is increasing,
g(x + ε) = r + δ for some δ > 0. By the same arguement in the second paragraph of the
proof of Lemma 4.6, there exists k such that f (k) (r + δ) > α for any α. Taking α = x + ε,
we have x + ε < f (k) (r + δ) = f (k) (g(x + ε)).

23

Claim 4.9 Let Tj be the tree that computes (x1 ∨ x2 ∨ · · · ∨ xj ) ∧ xj+1 and let g(p, j) =
p(1 − (1 − p)j ) be the corresponding polynomial. Then
1. For all ε > 0 and fixed p ∈ (0, 1), there exists j such that p − g(p, j) < ε.
2. For all p > 2 − φ ≈ .38 and j ≥ 2, p − g(p, j) ≥ g −1 (p, j) − p.
3. For j ≥ 2, h(p) = p − g(p, j) is decreasing on (.38, 1).
Proof. Statement (1) follows from the limit computation
lim p − g(p, j) = lim p(1 − p)j = 0.

j→∞

j→∞

For (2) we first observe that for p ∈ [2 − φ, 1],
g 0 (p, j) = 1 − (1 − p)j + pj(1 − p)j−1 = 1 − (1 − p)j−1 (1 − p(1 + j)) > 1
where g 0 (p, j) denotes the derivative with respect to p. For p ∈ [2 − φ, 1],
p − g(p)
> min g 0 (k) > 1.
g −1 (p) − p k∈[2−φ,1]
Finally, for (3), note that h0 (p) = 1 − g 0 (p, j) < 0 for p ∈ [2 − φ, 1].



Proof.[of Lemma 4.7]. To prove that the set of achievable fixed points is dense in (0, 1), it
suffices to show that for all ε > 0, there exists a set of achievable fixed points S such that
for all x ∈ (1/2, 1), there exists s ∈ S such that |x − s| < ε. Corollary 2.4 will imply density
in (0, 1/2).
We construct S as follows. Let f0 = fB2 . Recall f0 has fixed point p0 = 2 − φ ≈ .38. Let
g(p) = p(1 − (1 − p)j ) where j is chosen according to Claim 4.9.1 so that p0 − g(p0 ) < ε/2.
We define pi and fi inductively, where fi is an achievable polynomial with fixed point pi .
(k)
Let xi+1 = g −1 (pi ). By Claim 4.8, there exists k such that the fixed point of fi (g(xi+1 )) is
(k)
less than xi+1 + ε/2. Define fi+1 = fi (g(p)) and pi+1 to be the corresponding fixed point.
Apply Claim 4.9, we observe
pi+1 − pi < xi+1 +

ε 4.9.2
ε 4.9.3
ε 4.9.1
ε
− pi = g −1 (pi ) − pi +
≤ pi − g(pi ) +
≤ p0 − g(p0 ) +
≤ ε.
2
2
2
2

It follows that S = {p0 , p1 , . . . } satisfy the desired property that every point in (1/2, 1) is
within ε of some pi ∈ S.

Theorem 4.10 For any 0 = p0 < p1 < · · · < pk = 1, 0 = a0 < a1 < . . . ak < ak+1 = 1,
δ, ε > 0 such that ε < ai+1 −ai for all i, there exists a probability distribution on a set of trees
such that for 0 ≤ i ≤ k the corresponding polynomial f has the property that |f (x) − pi | < δ
for all x ∈ (ai + ε, ai+1 − ε).

24

Proof. We define a probability distribution of a set of trees, the existence of which are
guaranteed by Lemma 4.7 and Lemma 4.6. For 1 ≤ i ≤ k, let ti be an achievable fixed point
in (ai − ε/2, ai + ε/2). Let fi be an achievable function with fixed point ti the property that
fi (x) < δ for x ∈ [0, ti − ε/2] and fi (x) > 1 − δ for x ∈ [ti + ε/2, 1]. It follows that
fi (x) < δ
Pi−1
for x ∈ [0, ai − ε] and fi (x) > 1 − δ for x ∈ [ai + ε, 1]. Let α1 = p1 and αi = pi − j=1 αj for
P
2 ≤ i ≤ k. Let f (x) = kj=1 αj fj .
We show f is the desired function by computing f (x) for x ∈ (ai + ε, ai+1 − ε). Note that
fj (x) < δ for j ≤ i − 1 and fj (x) > 1 − δ for j ≥ i. Observe
pi − δ ≤ pi (1 − δ) ≤ f (x) =

i
X

αj f j +

j=1

k
X

αj fj ≤ pi + δ(1 − pi ) ≤ pi + δ.

j=i+1

Thus, |f (x) − pi | < δ for all x ∈ (ai + ε, ai+1 − ε).



Theorem 4.10 implies that any staircase function for which ai ≤ pi ≤ ai+1 for all 0 ≤ i ≤
k, can be approximated by the distribution of items at a high-level of an iterative tree. The
condition that ai ≤ pi ≤ ai+1 for all 0 ≤ i ≤ k guarantees the heights of each step are fixed
points, and therefore the stairs are maintained when f is iterated.

5

Finite iterative constructions of threshold trees

In the above section, we analyzed the behavior of iterative trees in the limit with respect to
level width. We assumed that for any input the number of items turned on at level l of the
tree is equal to its expectation, mf (l) (p) where m is the width of level l and p is the fraction
of the inputs turned on. In a “bottom up” construction in which the items of one level are
fixed before the next level is built, we note that the chance that the number of items that fire
at a given level deviates from expectation is non-trivial. In this section, we give a bound on
the width of the levels required to achieve a desired degree of accuracy for finite realizations
of iterative constructions.
Remark 5.1 We can use a transition matrix to directly compute the probability that a
high-level item of an iterative construction fires given the width of the levels. Let f be the
function corresponding to the construction, p be the fraction of input items firing, and m
the width of the levels. Define s ∈ R1×(m+1) , A ∈ R(m+1)×(m+1) , and t ∈ R1×(m+1)
 
m
si =
f (p)i (1 − f (p))m−i ,
i

Ai,j

 m−j
   j 
i
m
i
1−f
,
=
f
m
m
j

ti = i

for i, j = 0, 1, . . . m. Then the probability that an item at level L fires is sAL−1 tT .
We will use the following concentration inequalities.
Lemma 5.2 (Chernoff ) Let Y1 , Y2 , . . . Ym be independent with 0 ≤ Yi ≤ 1 and Y =
Then, for any δ > 0,

 2
−δ E(Y )
Pr(Y − E(Y ) ≥ δE(Y )) ≤ exp
.
2+δ

25

Pn

i=1

Yi .

Lemma 5.3 Let X be a sum of n binomial random variables with mean µ. Then, for k ≥ nµ,
n  
X
n i
Pr(X ≥ k) =
µ (1 − µ)n−i < exp (−nH(µ, k/n))
i
i=k

where H(p, q) = q log(q/p) + (1 − q) log((1 − q)/(1 − p)).
For ease of notation, all statements in this section about the probability of Xi+1 taking
some values refers to the probability of Xi+1 taking some values given Xi .
The following lemma describes linear divergence for finite width constructions.
Lemma 5.4 Consider the construction of a t-threshold function in which each level ` has
m` items and the fraction of input items firing is at least ε below the threshold t. Let d be
f (p)−p
the minimum value of p(1−p)(p−t)
on the interval [0, 1]. Then, with probability at least 1 − γ,
the fraction of inputs firing at level Ω( 1ε ) will be less than any fixed constant u when
m` =

1
)
8 ln( u(1−t)γ

d2 u(1 − t)2 1 +


c1 `−1 2
ε
2

where c1 is the linear divergence constant.
Proof. Let Xi be the fraction of items firing at level i. Then E(Xi ) = f (Xi−1 ). In
expectation, the sequence X1 , X2 , X3 , . . . converges to 0. We will show that with probability
at least 1 − γ, the sequence obeys the half-progress relation Xi+1 ≤ Xi +f2(Xi ) and therefore
XL < u for L = Ω( 1ε ).
Write f (p) − p = p(1 − p)(p − t)g(p) where g is a polynomial in p. Let d be the minimum
value obtained by g on the interval [0, 1]. First we compute probability that Xi+1 > Xi +f2(Xi )
given Xi by applying Lemma 5.2. Observe




Xi + f (Xi )
Xi − f (Xi )
Pr Xi+1 >
= Pr Xi+1 − E(Xi+1 ) >
2
2
 

2
Xi −f (Xi )
mf (Xi ) 
 − 2f (Xi )
≤ exp 

i −f (Xi )
2 + X2f
(Xi )


(Xi (1 − Xi )(Xi − t)g(Xi ))2 m
= exp −
2(Xi + 3(Xi + Xi (1 − Xi )(Xi − t)g(Xi )))


Xi (1 − Xi )2 (t − Xi )2 d2 m
≤ exp −
8
Let εi = t − Xi and α =

u(1−t)2 d2
.
8


Pr Xi+1

Then for u ≤ Xi ≤ t − ε,


Xi + f (Xi )
>
< exp −αmε2i .
2

Next we compute the probability that i is the first value for which the half-progress
relation is not satisfied given Xi > u. If the half-progress relation is satisfied meaning
26

Xi+1 > Xi +f2(Xi ) , then εi+1 ≥ εi β where β = 1 + u2 (1 − t). It follows that if the half-progress
relation is satisfied for all j < i, then εi+1 ≥ εβ i . Thus,



Xi + f (Xi )
≤ exp −αmε2 β 2i .
Pr i is the first value for which Xi+1 >
2
By linear divergence, there exists L = Ω(log( 1ε )) such that if the sequence satisfies the halfprogress relation for all i < L, then XL < u. We bound the probability that this does not
happen. Let m` =

1
8 ln( u(1−t)γ
)

d2 u(1−t)2 β i ε2

1
. For ease of notation, let c = ln u(1−t)γ
< 1. Observe

Pr(XL > u) ≤
=

L
X
i=0
L
X

exp −αm` ε2 β 2i
exp −cβ i





i=0

≤

L
X

exp (−c(1 + iu(1 − t)))

i=0

< exp (−c)

L
X

e−iu(1−t))

i=0

exp (−c)
<
1 − exp (−u(1 − t))
exp (−c)
<
= γ.
u(1 − t)

Theorem 5.5 Consider the construction of a t-threshold function with linear convergence
given in Theorem 1.3 in which each level ` has m` items and the fraction of input items
firing is at least ε from the threshold t. Then, with probability at least 1 − γ, items at level

1
1
1
1
1
Ω(log γ + log ε )) will accurately compute the threshold function for m = Ω ln( γ )( γ + ε2 ) .
Proof. Let Xi be the fraction of items firing at level i. Then E(Xi ) = f (Xi−1 ). By
Corollary 2.4, it suffices to consider the case when the fraction of inputs firing is less that
t − ε. As proved in Theorem 1.3, in expectation, the sequence X1 , X2 , X3 , . . . convergences
to 0. We will show that with probability at least 1 − γ2 , the sequence drops below γ2 . First
we apply Lemma 5.4. Recall that the polynomial corresponding to this construction is
f (p) = p + p(1 − p)(p − t) and therefore d in the statement of Lemma 5.4 is 1. Let u be a
8 ln(

4

)

u(1−t)γ
constant 0 < u < t, m ≥ u(1−t)
and L = Ω( 1ε ). Thus, XL < u with probability at least
2 ε2
1 − γ4 .
Next we show that given XL < u the probability that the sequence continues to obey the
half-progress relation (as defined in Lemma 5.4) and drops below γ2 is at least 1 − γ4 . Let
2
2
α = (1−u) 8(t−u) . Given a fixed value Xi < u,



Xi + f (Xi )
Pr Xi+1 >
< exp −αmXi2 .
2

27

We compute the probability that N + i is the first value for which the half-progress relation
is not satisfied given XL < u. If Xi < u and the half-progress relation is satisfied at i then
Xi+1 ≤ Xi (1 − β) where β = 21 (1 − u)(t − u). It follows that if the half-progress
  relation
is satisfied for all j < i, then XN +i ≤ (1 − β)i u. Let L0 =

4
(1−u)(t−u)

log2

2u
γ

. If for all

L0

L ≤ i ≤ L + L0 , the half-progress relation is satisfied then XL+L0 < u(1 − β) < γ2 . We
16
16 ln ( (1−u)(t−u)γ
)
bound the probability that this does not happen. Let m ≥ (1−u)
. For ease of
2 (t−u)2 γ
 
8
. Observe
notation, let c = ln βγ


Pr XL+L0

L0

γ X
>
≤
exp (−mXi α)
2
i=0


L0
X
2cXi
=
exp −
γ
i=1
0

≤

L
X



0
exp −c(1 − β)−(L −i)

i=0
0

=

L
X

exp −c(1 − β)i



i=0
0

βL
X

1
≤
exp −cei
β
i=0

2exp (−c)
β
γ
= .
4

≤

Therefore, with probability at least 1 − γ2 , items at level Ω(log γ1 + log 1ε )) of an iterative


γ
1
1
1
construction with width m fire with probability at most 2 for m = Ω ln( γ )( γ + ε2 ) . Thus,
the iterative construction accurately computes the threshold function with probability at
least (1 − γ2 )2 > 1 − γ.

We give a tighter bound for the accuracy of the finite width construction for functions
with quadratic convergence. We now prove Theorem 1.8, which can be restated as follows:
in order to accurately compute, with probability at least 1 − γ, a t-threshold function for
inputs
in which the fraction of inputs firing is within ε of t , the width of the levels must be

ln(1/γ)
Ω
.
ε2
Proof.[of Theorem 1.8.] Let Xi be the fraction of items firing at level i. Then E(Xi ) =
f (Xi−1 ). By Corollary 2.4, it suffices to consider the case when the fraction of inputs firing
is less that t − ε. As proved in Lemma 3.1, in expectation, the sequence X1 , X2 , X3 , . . .
convergences to 0. We will show that with probability at least 1 − γ, the sequence reaches 0.
First we apply Lemma 5.4. Recall from the proof of Theorem 1.5, that the minimum
f (p)−p
value of g(p) = p(1−p)(p−t)
is 1 on the interval [0, 1]. Therefore for such constructions d in
28

the statement of Lemma 5.4 is 1. For constructions described in Theorem 1.7, the minimum
f (p)−p
is 1t on the interval [0, 1], as proved in Lemma 2.11. Therefore for
value of g(p) = p(1−p)(p−t)
such constructions d in the statement of Lemma 5.4 is 1/t. Let u be the constant 0 < u < t
8 ln(

4

)

u(1−t)γ
1
in quadratic convergence as in Lemma 3.1, m` ≥ d2 u(1−t)2 (1+(c
`−1 ε2 and L = Ω( ε ). Thus,
1 /2)
XL < u with probability at least 1 − γ2 .
Next, we bound the probability given XL < u, that XL+r = 0. We say that Xk+1 regresses
if Xk+1 ≥ u. For m ≥ ul and c3 as in Lemma 3.1, we apply Lemma 5.3 and obtain

Pr(Xk+1

 
m
X
m
≥ Xk ) =
f (p)i (1 − f (p))m−i
i
i=d ue ne






p
1−p
≤ exp −m p log
+ (1 − p) log
f (p)
1 − f (p)






p − f (p)
1
+ (1 − p) log 1 −
≤ exp −m p log
cp
1 − f (p)


 3 


1
p − f (p)
≤ exp −m p log
+ (1 − p) −
c3 p
1 − f (p)





1
− p(1 − p)
≤ exp −m p log
c3 p



1
≤ exp −mp log
c3 pe
`
≤ (c3 ue)

It follows that
Pr(XL , XL+1 , . . . XL+r do not regress) ≥ 1 − r(c3 ue)` .
Next we bound the probability that given Xk < u, Xk+1 = 0.
Pr(Xk+1 = 0|Xk ≤ u) = (1 − f (Xk ))m ≥ (1 − u2 )m ≥ 1 − mu2 = 1 − lu.
Therefore
Pr(XL+r = 0|XL , XL+1 , . . . XL+r do not regress) ≥ 1 − (lu)r .
n
n
 oo
 

1
4
Let l = r = max c3 e, min 2u , log2 γ
. It follows log2 γ4 < l log2 lu1 and therefore
`
4
< lu1 . We now compute
γ
γ
Pr(XL+r = 0) ≥ 1 − r(c3 ue)` − (lu)r ≥ 1 − 2(lu)` ≥ 1 − .
2
We have shown that given XL < u, Pr(XL+r > 0) ≤ γ2 . Therefore,
 1 with probability at
ln( γ )
least 1 − γ, items at level Ω(log γ1 + log 1ε )) do not fire for m = Ω
.

ε2

29

5.1

Exponential and wild constructions

In this section, we analyze exponential constructions, where items are chosen with probabilities proportional to their weights, and the latter decay exponentially with time, by a factor
of e−α . The wild construction is the special case of the exponential construction in which
the α = 0, i.e. the weights of the items do not decay with time. Here we analyze the wild
and exponential constructions for the probability distribution given in Theorem 1.3, which
converges linearly to a t−threshold function. Analogous results, up to constants, hold for
the constructions with quadratic convergence.
Throughout this section, we use the following notation. We define Xk to be the probability an item chosen according to the weights at the beginning of the k + 1 iteration is 1.
We define
i−1
X
di =
e−jα
j=0

Wk = ne−αk +

k−1
X

e−jα .

j=0

Additionally, we use the following concentration inequality.
Lemma 5.6
P (Hoeffding) Let X1 , . . . , Xn be independent random variables with Xi ∈ [ai , bi ],
and X = ni=1 Xi . Then for t > 0,


2t2
.
Pr[X > E[X] + t] ≤ exp − Pn
2
i=1 (ai − bi )
The following two lemmas lay the foundation for the proofs of Theorem 1.9 and 1.10,
which prove convergence for the wild and exponential constructions respectively.
Lemma 5.7 Consider an exponential construction corresponding to a t-threshold function
given in Theorem 1.3. Let Xk be the probability an item chosen according to the weights
at the beginning of the k + 1 iteration is 1, and let ε = t − Xk . Let Ai be the event that
Xk+i ≤ Xk + 2ε . Then
 2 2
s
s
^
Y
−ε βi
Pr[ Ai ] ≥
1 − exp
2di
i=1
i=1
P
where βi = ne−(k+i)α + k+i−1
e−jα = Wk+i − di .
j=i
Proof. Note
Pr[

s
^

Ai ] = Pr[As |

i=1

s−1
^
j=1

s−1
^

Ai ]Pr[

j=1

Aj ] =

s
Y
i=1

Vi−1

Pr[Ai |

i−1
^

Aj ].

j=1

We now bound Pr[Ai | j=1 Aj ]. Let y1 , . . . yi be random variables where yj takes value
P
if the (k + j)th item fires. Let Y = ij=1 yj . We compute
Xk+i =

Wk Xk e−iα + dY
.
Wk+i
30

e−(i−j)α
d

The statement Xk+i ≥ Xk +

ε
2

is equivalent to the following statements, with d = di :

Y ≥

Y ≥ Xk +

ε ε
+
2 2

ε Wk+i
Wk+i − Wk e−iα
Xk +
d
2 d
!
P
ne−(k+i)α + k+i−1
e−jα
ε εβi
j=i
= Xk + +
d
2
2d

Note that E[Y ] ≤ Xk + 2ε . We have
i−1
^





ε εβi
εβi
Pr[Ai |
Aj ] = Pr Y ≥ Xk + +
≤ Pr Y − E[Y ] ≥
2
2d
2d
j=1
Note that 0 ≤ yi ≤

e−(i−j)α
.
d

Applying Hoeffding, we obtain

!

 2
εβi
εβi
1
Pr Y − E[Y ] ≥
≤ exp −2
2d
2d
d(1/d2 )
 2 2
−ε βi
= exp
.
2d


It follows that
Pr[

s
^

i=1

Ai ] ≥

s
Y


1 − exp

i=1

−ε2 βi2
2di


.


Lemma 5.8 Consider an exponential construction corresponding to a t-threshold function
given in Theorem 1.3. Let Xk be the probability an item chosen according to the weights at
the beginning of the k + 1 iteration is 1, and let ε = t − Xk . Assume Xk+i ≤ Xk + 2ε for all
1 ≤ i ≤ s. Then

s 
Y
ε(1 − t)
E[Xk+s ] ≤ Xk
1−
.
2W
k+i
i=1
Proof. For Xk+i−1 ≤ Xk + 2ε , we use the definition of f to compute


ε(1 − t)
f (Xk+i−1 ) = Xk+i−1 − Xk+i−1 (1 − Xk+i−1 )(t − Xk+i−1 ) ≤ Xk+i−1 1 −
.
2
We compute


Wk+i−1 Xk+i−1 e−α + f (Xk+i−1 )
ε(1 − t)
E[Xk+i ] =
≤ Xk+i−1 1 −
.
Wk+i
2Wk+i

31

We are now ready to prove Theorem 1.9 and Theorem 1.10 which describe the number of items needed to guarantee high accuracy in the wild and exponential constructions
respectively.
Proof.[of Theorem 1.9.] Assume that initial fraction of inputs firing is below the target
threshold. The other case follows similarly. We divide the analysis into phases in each of
which the total number of items double; in phase j, 2j n new items are created. Let Xk be
the fraction of the first k items and the n inputs that fire. First we show that with high
probability, Xk+i < Xk + 2ε holds for the entire phase, meaning for all 1 ≤ i ≤ n + k. We
call this event Aj where j denotes the phase. Lemma 5.7 for α = 0 states

(n+k)
−ε2 (n+k)
−ε2 (n+k)
Pr[A] ≥ 1 − e 2
≥ 1 − (n + k)e 2 .
We bound the probability that Aj does not occur for some phase
"
#
 2 j 
 2 
X
X
_
ε2n
−ε n
δ
j
Pr
Aj ≤
Pr[Aj ] ≤
(2 n)exp −
< 2nexp
< .
2
2
4
j
j
j
Next, we compute the expected progress of the sequence of Xk0 s corresponding to the
final items in each phase. Setting α = 0, Lemma 5.8 states

s




ε(1 − t)
ε(1 − t)s
ε(1 − t)
E[Xk+s ] ≤ Xk 1 −
≤ Xk 1 −
= Xk 1 −
.
2(n + k + s)
4(n + k + s)
8
We now show that with high probability, the actual progress made by each phase is close
th
to its expectation. Let zP
1 , . . . zk be indicator random variables where zi = 1 if i the (k + i)
s
item fires, and let Z = i=1 zi . We apply the Hoeffding bound and obtain




εXk (1 − t)
2sεXk (1 − t)
Pr Xk+s − E[Xk+s ] >
= Pr Z − E[Z] >
16
16
 2

2 2
−ε (1 − t) Xk s
< exp
.
128
(1−t)
. Thus,
Let Bj be the event that X2j+1 n − E[X2j+1 n ] ≤ εXk16
#
"
 2

X
X
_
−ε (1 − t)2 Xk2 2j n
δ
Bj ≤
Pr
Pr[B j ] ≤
exp
< .
128
4
j
j
j

We have shown, with probability at least 1 − 2δ , the events Aj and Bj hold until the
fraction of items firing is less that 2δ . At this point, an item does not fire and therefore
correctly computes the threshold function with probability 1 − 2δ .
To bound the total number of items, we compute the number of phases needed to achieve
Xk < 2δ . We divide the analysis into two parts, when  = t − Xk < Xk and Xk < t − Xk .
In the first part, ε = t − Xk grows by a constant factor in each phase, while in the second
part Xk decays by a constant factor in each phase. So the total number of phases needed
32

is O (log(1/δ) + log(1/ε)). The total number of items therefore is O n( δ1c +
absolute constant c.

1
)
εc



for some


Proof.[of Theorem 1.10.] As before, we assume without loss of generality that the initial
fraction of inputs firing is below the threshold. We divide the analysis into phases where s is
the number of items created in a phase, k is the number of items created prior to the start
of the phase, and n is the number of inputs. Let Xk be the probability an item selected
according to the probability distribution in the (k +1)st iteration fires. We will set the length
of a phase s = b1/αc.
First we compute the probability that, Xk+i < Xk + 2ε holds for the entire phase, meaning
for all 1 ≤ i ≤ s. We call this event Aj where j denotes the phase. Recall the definition of
βi given in Lemma 5.7. For 1 ≤ i ≤ s = 1/α and n > 1/α, we have
−(k+i)α

βi,k = ne

+

k+i−1
X

e

−jα

−(k+i)α

= ne

−iα

+e

k−1
X

k−1

−jα

e

−(k+i)α

≥ ne

j=i

j=i

1 X −jα
1
+
e
≥ 2
e j=0
eα

1
where the final inequality follows from the observations that if k < α1 then ne−(k+i)α ≥ eα
,
P
k−1 −jα
di
1
1
1−e−1
1
≥ eα . Note that di < ds = 1−e−α < α , so βi,k > e . Lemma
and if k ≥ α , then j=0 e
5.7 implies that
 2 2 
 2 2 !
 2
!
s
s
s
Y
X
X
−ε βi,k
ε βi,k
ε βi,k
Pr[Aj ] ≥ 1− 1−exp
≥ 1−
exp −
≥ 1−
exp −
.
2di
2di
2e
i=1
i=1
i=1

Therefore


 2


s
  X
ε2
ε βi,k
1
Pr Aj ≤
exp −
≤ exp − 3
.
2e
α
2e α
i=1

Next, we compute the probability that the progress made in a phase is close to its
expectation. We ignore the progress made in the first log n phases. Let Bj be the event that
ε X (1−t)
where k = j−1
, s = α1 , and εj = t − Xk , given Aj and j ≥ log n.
Xk+s − E [Xk+s ] ≤ j k32
α
First note that
k+i−1
X
2
−(k+i)α
Wk+i = ne
+
e−jα ≤ ne−kα + .
α
j=0
Lemma 5.8 implies that


s


s 
Y
εj (1 − t)
εj (1 − t)s
εj (1 − t)
≤ Xk 1 −
≤ Xk 1 −
.
E[Xk+s ] ≤ Xk
1−
2Wk+i
2(ne−kα + α2 )
4(ne−kα + α2 )
i=s/2

For j ≥ log n phases, we have k ≥ log n/α and therefore,


εj (1 − t)
E[Xk+s ] ≤ Xk 1 −
.
16
We now show that with high probability, the actual progress made by each phase is close
−(s−i)α
to its expectation. Let z1 , . . . zs be indicator random variables where zi = e ds
if i the
P
s
th
(k + i) item fires, and let Z = i=1 zi . Note
Xk+s − E[Xk+s ] =

ds
(Z − E[Z]) .
Wk+s

33

We apply the Hoeffding bound, noting that

Ps



i=1

e−(s−i)α
ds

2

≤

1
,
αd2s

and obtain





 
εXk (1 − t)
Wk+s εXk (1 − t)
Pr B j = Pr Xk+s − E[Xk+s ] >
= Pr Z − E[Z] >
32
32ds

 2
2
2 2
α
−ε (1 − t) Xk Wk+s
< exp
512

 2
−ε (1 − t)2 Xk2
< exp
512e4 α
 2

−ε (1 − t)2 Xk2 2048e4 log( εδ4 )
= exp
512e4 min{ε2 , δ 2 }
(δε)4
<
256
The third step uses the fact that Wk+s ≥ αε1 2 .
Next we compute the total number of phases needed before Xk < δ/3 given Aj holds for
all phases and assuming Bj holds after the first log n phases. For each phase after the first
log n phases, we have


εj (1 − t)
Xk+s ≤ 1 −
Xk .
32
We use the observation that if y ≥ x1 , then (1 − x)y ≤ 1e . Observe that


ε(1 − t)
t 1−
32

32
d ε(1−t)
e

≤

t
t
< .
e
2

32
Thus, after d ε(1−t)
e phases, the current Xk is less than t/2. Similarly we compute
log 3t
3t

d 64t(1−t)
 log 2δ
2δ e
δ
t
t/2(1 − t)
t 1
= .
1−
≤
2
32
2 e
3

log 3t/2δ
and conclude that after an additional d 64 t(1−t)
e phases the current Xk is less than δ/3. We
may assume ε + δ < t < 1 − ε − δ. The following is an upper bound on the total number of
phases needed to have a failure probability less than δ/3:

T = log n +

32 96
+ 2.
ε2
δ

It suffices to show that (i) the probability Aj holds for the first T phases is at least 1−δ/3
and (ii) the probability Bj holds for the latter T − log n phases is at least 1 − δ/3. We show
(i) in two parts. First we analyze the probability of some event Aj in the for the first log n
phases. We have
"log n # log n
!
_
X1
−ε2 maxi {βi, j−1 }
α
Pr
Aj ≤
exp
.
α
2e
j=1
j=1

34

 2
ε
. For j = 1, βi,0 ≥ ne . For j > 1, note βi, j−1 ≥
For ease of notation, let a = exp − 2e
α
We rewrite the above expression.
"log n #


log n
_
n
1 X
1
1
n
n
1
−
a
e2 α .
Pr
A j ≤ a e + a e2 α
a ej = a e + a e2 α
≤
3a
1 − a1/e
j=1
j=2
Observe

ε2
exp − 3
2e α




n
ej

+ e21α .

 2

ε 2048e4 log 4/εδ
(εδ)1024e
= exp − 3
≤
.
2e min{ε2 , δ 2 }
256

Next we compute
"
Pr

T
_
j=1

#
Aj




ε2
T − log n
exp − 3
≤ 3+
α
2e α




2048e4 log εδ4
32 96
(εδ)1024e
≤ 3+
+
ε2
δ2
min{ε2 , δ 2 }
256
δ
< .
3


Statement (ii) follows from the calculation:
" T
# 

_
32 96 (εδ)4
δ
Pr
Bj ≤
+ 2
< .
2
ε
δ
256
3
j=log n
We have shown after T = Ω(log(n/εδ) phases the next item will fire with probability less
than δ. Since each phase has 1/α new items, the total new items created to achieve this is



log εδ1
n
Ω
log
.
min{ε2 , δ 2 }
εδ

Finally, we note the lemmas and theorems in this section hold up to modification of
constants for wild and exponential constructions corresponding to constructions given in
Theorem 1.5 and Theorem 1.7, which exhibit quadratic convergence in the iterative tree
setting. However, unlike in the leveled iterative construction, in the exponential and wild
constructions we do not see asymptotically faster convergence than the corresponding linear
constructions, even in the quadratic regime. In our analysis of the latter constructions, we
track the probability that the sequence of Xk0 s goes to zero faster than iterating on curve
g(p) that is a weighted average of f (p) and the function p. Regardless of whether f (p)
has quadratic behavior, g(p) has a linear term, implying g(p) exhibits linear convergence.
Since this yardstick function g(p) exhibits linear convergence, this analysis will not yield
asymptotically improved results for functions with quadratic convergence.

35

6

Learning

So far we have studied the realizability of thresholds via neurally plausible simple iterative
constructions. These constructions were based on prior knowledge of the target threshold.
Here we study the learnability of thresholds from examples. It is important that the learning
algorithm should be neurally plausible and not overly specialized to the learning task. We
believe the simple results presented here are suggestive of considerably richer possibilities.
We begin with a one-shot learning algorithm. We show that given a single example of
a string X ∈ {0, 1}n with kXk1 = tn, we can build an iterative tree that computes a tthreshold function with high probability. Let T1 and T2 be the building block trees in the
construction given in Theorem 1.3. The simple LearnThreshold algorithm, described below,
has the guarantee stated in Theorem 1.11, which follows from Theorem 1.3.
LearnThreshold(L, m, X):
Input: Levels parameter L, a string X ∈ {0, 1}n such that kXk1 = tn, width parameter m.
Output: A finite realization of iterative tree with width m.
For each level j from 1 to L, apply the following iteration m times:
(level 0 consists of the input items X)
1. Pick a random input item i.
2. If Xi = 1 then let T = T1 , else let T = T2 .
3. Pick 3 items from the previous level.
4. Build T with these items as leaves.

7

Discussion

We have seen that very simple, distributed algorithms requiring minimal global coordination
and control can lead to stable and efficient constructions of important classes of functions.
Our work raises several interesting questions.
1. What are the ways in which threshold functions are applied in cognition? Object
recognition is one application of threshold functions in cognition. For instance, suppose
we have items representing features such as “trunk,” “grey,” “wrinkled skin,” and “big
ears,” and an item representing our concept of an “elephant.” If a certain threshold of
items representing the features we associate with an elephant fire, then the “elephant”
item will fire. This structure lends itself to a hierarchical organization of concepts that
is consistent with the fact that as we learn, we build on our existing set of knowledge.
For example, when a toddler learns to identify an elephant, he does not need to re-learn
how to identify an ear. The item representing “ear” already exists and will fire as a
result of some threshold function created when the toddler learned to identify ears.
36

Now the item representing “ear” may be used as an input as the toddler learns to
identify elephants and other animals.
2. What is an interesting model and neurally plausible algorithm for learning threshold
functions of k relevant input items? In this scenario, the input is a set of sparse binary
strings of length n representing examples in which at least tk of k relevant items are
firing. The output is an iterative tree that computes a t-threshold function on the
k relevant items. We can formulate the previously described example of learning to
identify an elephant as an instance of this problem. Each time the toddler sees an
example of an elephant, many features associated with elephant will fire in addition
to some features that are not associated with elephants. There may also be features
associated with an elephant that are not present in the example and therefore not firing.
A learning algorithm must rely on information about the items that are currently firing
to learn both the set of relevant items and a threshold function on this set of items.
It might also be beneficial to utilize prediction, as e.g., done by Papadimitriou and
Vempala [2015a].
3. To what extent can general linear threshold functions with general weights be constructed/learned by cortical algorithms?
4. A concrete question is whether the construction of Theorem 1.7 is optimal, similar to
the optimality of the constructions in Theorem 1.5.
5. A simple way to include non monotone Boolean functions with the same constructions
as we study here, would be to have input items together with their negations (as in
e.g., [Savicky, 1990]). What functions can be realized this way, using a distribution on
a small set of fixed-size trees?

References
Rosa I. Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine Learning, 63(2):161–182, 2006. doi: 10.1007/
s10994-006-6265-7. URL http://dx.doi.org/10.1007/s10994-006-6265-7.
Rosa I. Arriaga, David Rutter, Maya Cakmak, and Santosh S. Vempala. Visual categorization
with random projection. Neural Computation, 27(10):2132–2147, 2015. doi: 10.1162/
NECO\ a\ 00769. URL http://dx.doi.org/10.1162/NECO_a_00769.
Ravi B. Boppana. Amplification of probabilistic boolean formulas. In Foundations of
Computer Science, 1985., 26th Annual Symposium on, pages 20–29, Oct 1985. doi:
10.1109/SFCS.1985.5.
Alex Brodsky and Nicholas Pippenger. The boolean functions computed by random boolean
formulas or how to grow the right function. Random Structures & Algorithms, 27(4):490–
519, 2005. ISSN 1098-2418. doi: 10.1002/rsa.20095. URL http://dx.doi.org/10.1002/
rsa.20095.
37

M. Dubiner and U. Zwick. Amplification and percolation [probabilistic boolean functions]. In
Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on, pages
258–267, Oct 1992. doi: 10.1109/SFCS.1992.267766.
Vitaly Feldman and Leslie G. Valiant. Experience-induced neural circuits that achieve high
capacity. Neural Computation, 21(10):2715–2754, 2009. doi: 10.1162/neco.2009.08-08-851.
Hervé Fournier, Danièle Gardy, and Antoine Genitrini. Balanced and/or trees and linear
threshold functions. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, ANALCO ’09, pages 51–57, Philadelphia, PA, USA, 2009. Society for Industrial and
Applied Mathematics. URL http://dl.acm.org/citation.cfm?id=2791158.2791166.
Joel Friedman. Constructing O(nlogn) size monotone formulae for the k th threshold function
of n boolean variables. SIAM Journal on Computing, 15(3):641–654, 1986.
Sally A Goldman, Michael J Kearns, and Robert E Schapire. Exact identification of readonce formulas using fixed points of amplification functions. SIAM Journal on Computing,
22(4):705–726, 1993.
Shlomo Hoory, Avner Magen, and Toniann Pitassi. Monotone circuits for the majority
function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, pages 410–425. Springer, 2006.
Michael Luby, Michael Mitzenmacher, and Mohammad Amin Shokrollahi. Analysis of random processes via and-or tree evaluation. In SODA, volume 98, pages 364–373, 1998.
Edward F Moore and Claude E Shannon. Reliable circuits using less reliable relays. Journal
of the Franklin Institute, 262(3):191–208, 1956.
Christos H. Papadimitriou and Santosh S. Vempala. Cortical learning via prediction. In
Proc. of COLT, 2015a.
Christos H. Papadimitriou and Santosh S. Vempala. Cortical computation. In Proc. of
PODC, 2015b.
E. Rosch. Principles of categorization. In Eleanor Rosch and Barbara Lloyd, editors, Cognition and Categorization. Lawrence Elbaum Associates, 1978.
Eleanor Rosch, Carolyn B. Mervis, Wayne D. Gray, David M. Johnson, and Penny Boyesbraem. Basic objects in natural categories. COGNITIVE PSYCHOLOGY, 8:382–439,
1976.
Petr Savicky. Boolean functions represented by random formulas. Commentationes Mathematicae Universitatis Carolinae, 28(2):397–398, 1987.
Petr Savicky. Random boolean formulas representing any boolean function with asymptotically equal probability. Discrete Mathematics, 83(1):95 – 103, 1990. ISSN 0012-365X. doi:
http://dx.doi.org/10.1016/0012-365X(90)90223-5. URL http://www.sciencedirect.
com/science/article/pii/0012365X90902235.
38

Rocco A. Servedio. Monotone boolean formulas can approximate monotone linear threshold
functions. Discrete Applied Mathematics, 142(13):181 – 187, 2004. ISSN 0166-218X.
doi: http://dx.doi.org/10.1016/j.dam.2004.02.003. URL http://www.sciencedirect.
com/science/article/pii/S0166218X04000174. Boolean and Pseudo-Boolean Functions.
Leslie G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms,
5(3), 1984.
Leslie G. Valiant. Circuits of the mind. Oxford University Press, 1994. ISBN 978-0-19508926-4.
Leslie G. Valiant. A neuroidal architecture for cognitive computation. J. ACM, 47(5):
854–882, 2000. doi: 10.1145/355483.355486.
Leslie G. Valiant. Memorization and association on a realistic neural model. Neural Computation, 17(3):527–555, 2005. doi: 10.1162/0899766053019890.

39

8

Appendix
Degree
5
Degree
1
2
3

4

Polynomials in A
(0,1)
(0, 0, 1)
(0, 2, -1)
(0, 0, 0, 1)
(0, 1, 1, -1)
(0, 0, 2, -1)
(0, 3, -3, 1))
((0, 0, 0, 0, 1)
(0, 1, 0, 1, -1)
(0, 0, 1, 1, -1)
(0, 2, 0, -2, 1)
(0, 0, 0, 2, -1)
(0, 1, 2, -3, 1)
(0, 0, 3, -3, 1)
(0, 4, -6, 4, -1)
(0, 0, 2, 0, -1)
(0, 0, 4, -4, 1))

Polynomials in A
(0, 0, 0, 0, 0, 1)
(0, 1, 0, 0, 1, -1)
(0, 0, 1, 0, 1, -1)
(0, 2, -1, 1, -2, 1)
(0, 0, 0, 1, 1, -1)
(0, 1, 1, 0, -2, 1)
(0, 0, 2, 0, -2, 1)
(0, 3, -2, -2, 3, -1)
(0, 0, 0, 0, 2, -1)
(0, 1, 0, 2, -3, 1)
(0, 0, 1, 2, -3, 1)
(0, 2, 1, -5, 4, -1)
(0, 0, 0, 3, -3, 1)
(0, 1, 3, -6, 4, -1)
(0, 0, 4, -6, 4, -1)
(0, 5, -10, 10, -5, 1)
(0, 0, 0, 2, 0, -1)
(0, 1, 2, -2, -1, 1)
(0, 0, 0, 4, -4, 1)
(0, 1, 4, -8, 5, -1)
(0, 0, 1, 1, 0, -1)
(0, 0, 3, -1, -2, 1)
(0, 0, 2, 1, -3, 1)
(0, 0, 6, -9, 5, -1)

Table 1: Achievable polynomials for AND/OR trees. The polynomial a0 + a1 x + a2 x2 +
a3 x3 + a4 x4 + a5 x5 is denoted by (a0 , a1 , a2 , a3 , a4 , a5 ).

40

