Products and Help Bits in Decision Trees.
We investigate two problems concerning the complexity of evaluating a function f on k distinct inputs by  k parallel decision-tree algorithms.In the product problem, for some fixed depth bound  d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best depth-d decision tree is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth-d algorithms are all correct is at most pk, which is the trivial lower bound. We show that if we replace the restriction to depth d by "expected depth d," then this result need not hold.In the  help-bits problem, before the decision-tree computations begin, up to k-1 arbitrary binary questions (help-bit queries) can be asked about the k-tuple of inputs. In the second stage, for each possible (k-1)-tuple of answers to the help-bit queries, there is a k-tuple of decision trees where the ith tree is supposed to correctly compute the value of the function on the ith input, for any input that is consistent with the help bits. The complexity here is the maximum depth of any of the trees in the algorithm.  We show that for all k sufficiently large, this complexity is equal to degs(f), which is the minimum degree of a multivariate polynomial whose sign is equal to f.
Introduction
Pick your favorite computation model and complexity
measure, e.g. boolean circuit size, communication
complexity, decision tree depth, interactive proof
length, tensor rank, etc. Any attempt to understand
such a model and complexity measure requires understanding
the ways that an "unreasonable" computation
can be more efficient than a "reasonable" one.
Of course, what is "reasonable" changes as our understanding
of the model improves.
Suppose we are given several unrelated instances of
a problem to solve. The "reasonable" approach is to
solve each instance separately; intuitively, any computation
that is useful for solving one instance is irrelevant
to any of the others. To what extent is this
intuition valid in a given model? The following question
is the most common way of formalizing this.
The Direct-sum problem: Suppose that the complexity
of computing some function f is c. Is it true
that computing f twice, on two unrelated inputs requires
complexity 2c? How about computing f on k
unrelated inputs?
This question was first studied in the context of
Boolean circuits [Ulig, Paul, GF]. Subsequent work
has concerned bilinear circuits [J, Bsh], Boolean circuits
[FKN], and communication complexity [KRW].
In this paper we consider two related problems of a
similar flavor:
The Product Problem: Let f be a function and
suppose that for any complexity c computation, the
fraction of inputs on which it correctly computes f
is at most p. Suppose that we have two independent
computations, each taking as input an ordered pair a; b
of inputs to f , where the first computation is trying
to compute f (a) and the second is trying to compute
f (b). If each of the two computations has complexity
at most c, can the fraction of input pairs a; b on which
both are correct exceed What about the analogous
question for k independent computations and k
inputs?
If the first computation only uses the input a and
the second only uses the input b, then the p 2 upper
bound is trivial. Intuition suggests that there is no
advantage in having each computation access the others
input. A variant of this problem, in which we seek
to compute f on the two inputs by a single computation
was studied recently in [IRW].
The Help-bit Problem: Suppose that the complexity
of computing the boolean function f is c. Suppose
that one wishes to compute f on two inputs a and b,
and is allowed for free one "help-bit", i.e. an arbitrary
function of the two inputs. Is it possible to choose
this help-bit function so that, given the help-bit, f (a)
and f (b) can each be computed by a computation of
complexity less than c, and if so, by how much? How
about computing f on k inputs with
The help-bit problem was introduced (to our knowl-
edge) in the context of constant depth circuits in [Cai],
and was also studied in the context of boolean circuits
in [ABG]. The point here is that if we have k inputs,
then with k help bits we can use them to obtain the
value of f on each of the inputs, and no further computation
is necessary. With only
can for instance obtain the value of f at
but then we still need complexity c to compute f on
the last input. Is there a more effective use of the help
bits?
In this paper we consider these problems in the context
of the boolean decision tree complexity - perhaps
the simplest computational model. The cost of a computation
(decision tree) is simply the number of input
variables that are read (the depth of the decision tree);
a more precise definition is given in Section 2. While
it is an easy exercise to see that "direct-sum" holds
for decision tree depth, the other two problems are
more difficult. Our answer for the product problem is
a qualified "Yes":
Theorem 1 Let f be an n-variable boolean function
and suppose that any depth d decision tree computes
f correctly on a fraction at most p of the inputs. Let
decision trees that each access a set of
nk variables corresponding to a k-tuple a 1 ; a 2 ; . ; a k
of inputs to f . If each of the T i have depth at most
d, then the fraction of k-tuples a 1 ; a 2 ; . ; a k on which
each T i correctly outputs f (a i ) is at most p k .
The theorem seems completely obvious; however,
the reader might test her intuition on the following
variation. Suppose that, in the above Theorem we
change the complexity measure from "depth" to "av-
erage depth" , i.e, the average over all inputs of the
depth of the leaf reached by the input. This modified
statement of the Theorem seems similarly obvi-
ous, but, as we will see, it is false.
The recent work of [IRW], which was done independently
of ours, includes a (substantially different)
proof of a weaker variant of this theorem, namely that
a single depth d tree that tries to compute all k functions
can be correct on at most a p k fraction of the
inputs. Our result shows that even if we use k parallel
decision trees then we can't do better than this.
For the help bit problem, the answer is more com-
plicated. Nathan Linial [Lin] has shown that the complexity
of computing f on two inputs with one help
bit is at least deg(f ), the degree of the (unique) multi-linear
real polynomial that is equal to f . Since almost
all boolean functions on n-variables have deg(f
this says that help bits don't help for most functions.
This result does not seem to extend to k - 3. In
fact, for sufficiently large k our results imply that it is
false. We manage to prove a lower bound that holds
for all k, and is always tight when k, the number of
instances to be solved, is sufficiently large. We need
the following definitions. If f is an n-variate boolean
function, we say that the n-variate real polynomial p
sign-represents f if for all inputs a,
(here we are taking our Boolean set to be f\Gamma1; 1g).
The sign-degree of f , deg s (f ), is the minimum degree
of a polynomial that sign represents f .
Theorem 2 Let f be an n-variate boolean function,
and suppose that the optimal decision tree that computes
f has depth d. Then for all k - 1, any solution
to the help bit problem for f for k inputs and
help bits requires depth at least deg s (f ). Furthermore,
for all sufficiently large k, there is a decision tree algorithm
bits whose depth is deg s (f ).
In the case that f is equal to the product of n
variables (which corresponds to the parity function
for f0; 1g-valued variables), deg s (f and so, the
lower bound implies that help-bits don't help in this
case. Actually, this function and its negative are the
only functions with deg s (f the ordinary
decision tree complexity of most boolean functions is
n, this means that for large enough k, the complexity
of k instances given bits is less than
the ordinary decision tree complexity for most func-
tions. In particular, if f is the majority function, then
deg s (f and the lower bound is vacuous, while
the upper bound says that for k sufficiently large, it is
possible to ask questions so that, given the
answers, the value of the function on any one of the
k inputs can be computed by probing just one vari-
able. This remarkable savings is not typical, it was
recently shown [RR] that almost all functions satisfy
In the next section, we review the decision tree
model. In Section 3 we give a general formulation
for the product problem in decision trees, and prove
a generalization (Theorem 3.1) of Theorem 1. In Section
4, we discuss the help bits problem and prove
Theorem 2. Most proofs are in the appendices.
While some of the techniques we develop apply only
to the decision tree model, some of them may be applied
to other models as well, and in fact suffice for
obtaining many of the known results in the boolean
circuit model. We sketch these applications in the
last section.
Preliminaries
In this section we present some basic definitions and
notation. Most of the notions discussed here are
very familiar, but in some cases our notation is non-standard

2.1 Boolean functions
For purposes of this paper it will be convenient to use
our Boolean domain, instead of f0; 1g.
If X is a set, a boolean assignment to X is a map
ff from X to B. The set of boolean assignments to
X is denoted B X . We refer to the elements of X as
variables. We will consider probability distributions
over the set of assignments. For a specified distribution
D, a random assignment chosen according to D
is denoted by placing a ~ above the identifier, e.g., ~
ff.
A boolean function over the variable set X and range
R, or (X;R)-function is a function from B X to R. In
this paper, the range R is always equal to B k for some
integer k.
2.2 Decision Trees
All trees in this paper are rooted, ordered, binary
trees. For such a tree T every internal node v has
exactly two children, and the two children are distinguished
as the (-1)-child and (+1)-child of v. The
depth dT (v) of a node v is, as usual, the number of
edges along the path from v to the root and the depth
dT of T is the maximum depth of any node in T .
Formally, a decision tree over the variable set X
with range R or (X;R)-decision tree is a triple (T ;
where T is a rooted binary tree, p is a map that associates
to each internal node v a variable in the
set X , and a is a map that associates each leaf v to
an element a v of R. The label p v is called the query
associated to v, and node v is said to probe variable
We will generally say that T is an (X;R)-decision
tree, keeping the maps p and a implicit. The set of
(X; R)-decision trees over X is denoted T (X; R), or
simply T .
Let T be an (X;R)-decision tree. If ff is any assignment
in B X , the computation of T on ff, is the unique
path s from the root of T to some leaf
start from the root v 0 and
inductively define define v as the ff(p v i )-
child of v i . The output of the computation is the label
a l T (ff) . Thus T can be viewed as a boolean function
over X with range R. Trivially, every (X;R)-function
f is computed by some (X;R)-decision tree.
The usual cost function for the computation performed
by T on ff is the length (number of internal
nodes) of the computation path, denoted C(T ; ff). The
worst case complexity C(T ) is the maximum over ff
of C(T ; ff). C(f ), the decision tree depth of f , is the
minimum of C(T ) over all decision trees that compute
f . For a distribution D on assignments, the distributional
complexity CD (T ) is the average of C(T ; ~
ff) with
respect to the distribution D.
For a given (X; R)- function f , and a complexity
bound b (with respect to some complexity measure),
we are interested in how well f can be approximated
by a tree of complexity at most b. The closeness of
approximation is defined with respect to a probability
distribution D on boolean assignments to X . Thus for
each (X;R)-decision tree T , the agreement probability
q D (f ; T ) of T with f relative to D, is the probability
that T with respect to the random
assignment ~
ff chosen according to D. The decision
tree approximation problem for (f; D;U) where f is an
(X; R)-function, D is a distribution over boolean assignments
to X , and U is a set of decision trees is to
determine q D (f ; U), which is defined to be the maximum
agreement probability q D (f
Of particular interest is the case that U is the set
T d (X; R) of decision trees of depth at most d.
Finally, a decision forest F over X and ranges
is an ordered sequence
where T i is an (X;R i )-decision tree. F computes a
boolean function from B X to R . \Theta R k .
3 The Product Problem
disjoint sets of vari-
ables, and let respectively, distributions
over assignments to
assignment fi for
X will be viewed as a k-tuple
is an assignment for X i . Let D denote the distribution
over assignments to X given by ProbD ( ~
product distribution
. \Theta D k .
Now suppose that we have k decision tree approximation
problems
each
be the optimal agreement probability for U i with
f i relative to D i . It will be convenient sometimes
to view f i as a function of the entire variable
set X that ignores all variables except those in
We consider the problem of simultaneously approximating
by a decision forest
. The simultaneous
agreement probability q D (f
for denotes the prob-
ability, for ~
ff chosen according to D, that (T 1
For is a family of (X; R i )-
trees, q D (f denotes the
maximum of q D (f
choices of trees with
Now, since f i only depends on X i and D chooses
the assignments ~
ff k to
dependently, it would
seem that q D (f should just
be the product of the probabilities q This is
clearly the case if each tree T i only queries variables
in X i . However (as shown by the examples in below),
if T i is allowed to query variables outside of X i , then
this need not be the case. Intuitively, it would seem
that variables outside of X i could not help to approximate
f i and indeed this is trivially true, if we are only
trying to approximate f i . But when we seek to approximate
all of the functions simultaneously, it is no
longer obvious that such "cross-queries" are irrelevant.
Nevertheless, one might expect that for "reason-
able" classes U of decision trees, the optimal
simultaneous agreement probability is attained
by a sequence of trees querying
variables only in X i , and is thus equal to the product
of the individual optimal agreement probabilities.
The main result of this section is to prove this in the
case that for each i, U i is the set of trees of some fixed
depth d i .
Theorem 3.1
be as above. Let d 1 ; d 2 ; . ; d k be
nonnegative integers. Then
Y
Note that Theorem 1 is a special case of the above.
Before giving the proof we present two examples to
show that multiplicativity fails for some natural alternative
choices of the classes U
Example 3.1 Theorem 3.1 fails if we replace the
class T d i by the class S i
of trees that are restricted
to query at most d i variables from X i along any path,
but can query variables outside X i for free. Consider
the following trivial example. Let
g. The distribution D 1 assigns x 1 to
1 with probability 1/2, and D 2 assigns x 2 to 1 with
probability 1/2. The functions f 1 and f 2 are given by
means that we do not allow T 1 to look at any variables
in X 1 and we do not allow T 2 to look at any variable in
ever, we can achieve simultaneous agreement probability
better than 1/4. Let T 1 be the tree that queries x 2
and outputs x 2 and T 2 be the tree that queries x 1 and
outputs x 1 . Then, the probability that both T 1 and f 1
agree and T 2 and f 2 agree is just the probability that
are assigned the same value, which is 1/2.
A somewhat more subtle example is given by:
Example 3.2 For a distribution D over B X , let T D
d
be the class of trees whose expected depth with respect
to D is d, i.e., T 2 T d if the average number of variables
queried, with respect to ~
ff chosen from D is at
most d. Then the above theorem is false if we replace
. To see this, let X be a set of four vari-
ables, and f be the parity function on X. Let U be
the uniform distribution over assignments to X and
3. First we show that the maximum agreement
probability with f attained by a decision tree S of expected
depth at most 3, is equal to 3/4. Agreement
probability 3/4 is attained by the tree S that queries
a particular variable x, and if it is 0, then it returns
0, and otherwise it queries the remaining three variables
and returns the parity of them. To see that this
is best possible, note that if T is any decision tree al-
gorithm, then for each leaf l in T of depth less than
4, T will agree with f on exactly half of the inputs
that reach l. Thus, if p i is the probability that a random
input ~
ff ends up at a leaf of depth i, then the
agreement probability q D (f ; T ) can be bounded above
by it suffices to show that p 4 - 1=2.
Now or 1. If
then the expected depth of the
tree is at least 4p 4 which means
that
Now let be copies of
f; U on disjoint variable sets. We show that it
is possible to choose decision trees each of expected
depth at most 3, whose agreement probability
exceeds be the S described
above and let x 1 denote the variable in X 1 probed first
by T 1 . Let T 2 be the following tree: first probe x 1
(in it is 0, output 0. If it is one, then read
all four variables in X 2 and output their parity. The
expected depth of this tree is 3, since half the paths
have depth one and half the paths have depth five.
let us consider the probability of the event A
that both T 1
1). The conditional probability of A given x
1/4. If x must agree with f 1 , and T 2
must agree with f 2 . Thus the probability of simultaneous
agreement is
What happens in the above example is that the
variable x 1 acts as a shared random coin that partially
coordinates the two computations so that they
are more likely to be simultaneously correct.
Proof of Theorem 3.1 Fix a sequence T
of decision trees with T i of depth at most d i . For
I ' denote the event
the event that all of the trees
indexed by I evaluate their respective functions cor-
rectly. We seek to prove that Prob[C([k])] is bounded
above by
The proof is by induction on k, and for fixed k by
induction on the k-tuple d 1 . The result
is vacuous if
So assume that k - 2. Consider first the case that
We may assume that d
the k th party must guess the value of f k (~ff k ) without
looking at any variables, so T k consists of a single leaf
labeled -1 or 1. Now, by conditioning on the value of
the vector ~
ff k , the probability, P   that C([k]) holds
can be written:
Now let fl be the assignment of ~
ff k that maximizes
the probability in the last expression. For each i between
define the tree U i by contracting
using ~ ff fl. Then we may rewrite the
last term as Prob[(U 1
f
Each tree U i has depth at most d i , and so we may
bound the first factor by
which by the
induction hypothesis equals
the desired result follows.
Now we assume that d i ? 0 for all i. Define a
directed graph on f1; 2; :::; kg with an edge from i to
if the first variable probed by T i is an input to f j .
Since this directed graph has out-degree one, it has a
directed cycle. Let j - 1 be the length of the cycle.
Let us rename the set of indices in the cycle by the set
in such a way that for each
the first probe of T i is a variable, denoted x i+1 , in
and the first probe of T j is a variable, denoted
The intuition behind the rest of the proof is that
is possible to replace each tree T i by
trees of the same depth in which the first probe in T i is
decreasing the probability of simultaneous
agreement.
For
i denote the function obtained from
f i by fixing x i
i be the distribution
on the set obtained from D i by conditioning
on x i
the event that (~ff 1
can write the probability that all of the T i compute
correctly by conditioning on b as follows:
We seek to upper bound this expression by:
Y
To do this we show:
Claim. For each b 2 B [j] , the conditional probability
of C([k]) given A(b) is at most:
Y
Y
Assuming the claim for the moment, we can then
substitute into the expression (1) to obtain the following
bound on the probability that all of the trees are
correct:
Y
Y
The sum can be rewritten as:
Y
which is equal to:
Y
Now, the i th term in this product corresponds to
the probability of correctly computing f i if we first
probe x i and then, depending on the outcome, use
the optimal depth d tree to evaluate the residual
function. Thus, we can upper bound this term by
the expression (3) is upper
bounded by the expression (2) as required.
it suffices to prove the claim. Define f A(b)
i to
be the function f b i
and to be f i otherwise.
Similarly, the distribution D A(b)
i is equal to D b i
and to D i otherwise. Observe that by the mutual
independence of ~
given A(b) is the product distribution of D A(b)
between 1 and k.
Let T A(b)
i be the tree obtained from contracting
under the assumption that A(b) holds. Then the
conditional probability that T
A(b) is equal to the probability (with respect to the
product distribution on D A(b)
. Now for each i the depth of T A(b)
i has at most
and is at most d i for i ? j, so we
may apply induction to say that the probability with
respect to the product distribution on D A(b)
i that for
all i, T A(b)
i is at most:
Y
(f A(b)
Y
(f A(b)
which is equal to the expression in the claim. This
proves the claim and the Theorem.
Remark. The proof of the Theorem can be extended
to a more general model of decision tree computation.
For this model, in the case of a single function we
are given a function f from an arbitrary domain S to
R, and want to compute f (s) for an unknown input
S. We are further given a set Q of admissible
queries, where each query q 2 Q is a partition of S
into sets (S q
r ). The response to query q is
the index i such that s 2 S q
. The nodes of a decision
tree are labeled by queries, and the branches out of
the node correspond to the answers to the query. For
a collection of functions f i on disjoint domains S i , the
formulation of the product problem generalizes to this
model. The statement and proof of the Theorem now
go through assuming: (1) That the any allowed query
depends only on variables from one function and (2)
The distributions D i are independent.
4 Help Bits
In the help bits problem, We have k boolean
functions disjoint variable sets
Given an unknown assignment ff to
the variables of the set
to evaluate f i (ff i ) for all i, by a decision forest. We
are allowed to ask, "for free", an arbitrary set of l
binary questions about the assignment ff. The answer
to these l questions is a vector a 2 B l . For
each such a we will have a decision forest F a =
(T a
k ), where we require that F a (ff) agrees
with assignment ff that
is consistent with a.
Thus, such an algorithm is specified by l arbitrary
boolean functions h (the help bits) on variable
set X , together with 2 l decision forests. The complexity
of the algorithm is the maximum depth of any
of the 2 l k decision trees in these forests. In general,
the decision tree T a
i that computes f i (ff i ) for ff consistent
with a is allowed to probe variables outside of X i .
This is conceivably useful, because together with the
help bits, such probes could imply information about
the variables in X i . For instance if one of the help
bit functions is (f i (ff i ) \Theta ff j (x)) where x is a variable
in X j , then by probing the variable x, we can deduce
only probes variables in X i we say that
it is pure. If each of the 2 l k decision trees are pure,
the algorithm is pure.
In this paper, we will restrict attention to the case
that, for some variable set X and boolean function
f over X , each of the X i are copies of X and the
functions f i are copies of f . The help bits problem
H k;l (f ) is to evaluate k copies of f given l help bits.
to be the complexity of the optimal
algorithm that solves it. We also define the problem
pure (f ) to be the same as H k;l (f ) except that we
require that the algorithm be pure. Define C k;l
pure (f ) to
be the complexity of the optimal pure algorithm. Our
goal is to obtain bounds on C k;l (f ) and C k;l
pure (f ). The
main result of this section (which is a slight refinement
of Theorem 2), is:
Theorem 4.1 For any boolean function f on n variables
and any positive integer k,
pure (f
If k is sufficiently large, then
pure (f
We first reformulate the problems H k;l (f ) and
pure (f ). Given functions f
and a decision forest F , we say that F covers the
assignment ff of X , with respect to f 1
d) be the
minimum number of forests, each consisting of trees
of depth at most d, needed to cover all inputs with respect
to f . Let - k
pure (f; d) be the corresponding minimum
when we restrict to forests that are pure.
Proposition 4.1 Let f be a boolean function and
k; l; d be nonnegative integers. Then:
1. C k;l (f ) - d if and only if - k (f; d) - 2 l ,
2. C k;l
pure (f) - d if and only if - k
pure (f; d) - 2 l .
In other words, dlog 2 - k (f; d)e is the minimum l such
that H k;l can be solved with trees of depth d, and
pure (f; d)e is the minimum l such that H k;l
pure
can be solved with trees of depth d.
Proof. We prove the first assertion; the proof of
the second is completely analogous. If C k;l (f
then the 2 l forests given by the algorithm are also a
cover and - k (f; d) - 2 l . Now suppose - k (f; d) - 2 l .
Then there is a collection of 2 l forests that cover all
assignments of X. Index these forest as F z where
z ranges over B l . Order the forests lexicographi-
cally, and define A(z) to be the set of assignments
that are covered by F z but not covered by F y for
any y - z. Then the sets partition
the set of all assignments of X . Now define the
help bit functions h l so that for each ff,
is the unique index z such
that ff 2 A(z). Then these functions together with
solves H k;l .
So we now concentrate on obtaining bounds on
d) and - k
pure (f; d). For this we need yet another
definition. A randomized (X;R)-decision tree
algorithm is a probability distribution Q over (X;R)-
decision trees. Such an algorithm is said to approximate
f with probability p if for each assignment ff, if ~
is a random decision tree chosen according to Q, then
the probability that ~
f(ff) is at least p. We
define p(f; d) to be the maximum p such that there
is a distribution Q over the set of decision trees of
depth at most d that approximates f with probability
p. It is easy to see that p(f; d) - 1=2. and that if
the ordinary decision tree complexity of f ,
then p(f; d) = 1. The following result relates - (f; d)
to p(f; d).
Lemma 4.1 For any boolean function f on n variables
and k; d - 0, we have:p(f; d) k - (f; d) - pure (f; d) - d
nk
d) k e
Proof. The middle inequality is trivial. For the last
inequality, we use a standard probabilistic argument
to show that there is family of at most d k
p(f;d) e pure
forests of depth at most d that cover all of the assign-
ments. Let Q be the distribution over (Y; R)-decision
trees of depth at most d that approximates f with
probability p(f; d). For be the corresponding
distribution over the set of (X
trees;
Consider the distribution . \Theta Q k over
forests. Suppose we select t forests ~
according
to P . For a given assignment ff and j - t,
the probability that ~
covers ff is at least p(f; d) k .
Thus the probability that none of the forests cover ff
is at most (1 \Gamma p(f; d)) t , and the probability that there
exists an assignment ff that is covered by none of the
forests is at most 2 nk
e then this expression is at most
1, so there is a positive probability that the forest covers
all assignments, and so there must be a collection
of t forests of depth d that cover all assignments.
Now we turn to the lower bound on - (f; d). For
this, we need the following relationship between p(f; d)
and the agreement probability q -
D (f; d) with respect to
a particular distribution -
D on assignments.
Lemma 4.2 For any (Y; R)-boolean function f and
integer d - 0, there exists a distribution -
D on assignments
to Y such that q -
This is a variant of a fundamental observation of
Yao [Y1], and follows from the min-max theorem for
two person zero sum games.
D be the distribution of the lemma. Suppose
that is a family of forests that
cover all assignments ff to X. Consider the distribution
P over all assignments ff which is the product
. \Theta -
D i is the copy of
D on X i . Then, by Theorem 3.1, for any forest F i ,
the probability that it covers ~
ff is at most p(f; d) k .
Then the expected number of assignments covered by
t is at most tp(f; d) k . Since F 1
covers all assignments, this expectation must be at
least 1, so t - 1=p(f; d) k .
As an immediate corollary of the above lemma and
proposition 4.1 we get the following bounds on the
complexity of the help bits problem:
Corollary 4.1 For any boolean function f on n variables
and integers k; l; d - 0:
1. If 2 l - 1=p(f; d) k then C k;l (f ) ? d.
2. If 2 l - nk=p(f;d) k then C k;l
pure (f
Next we need to connect the quantity p(f; d) to the
sign-degree deg s (f ).
Proposition 4.2 For
any boolean function f , p(f; d) ? 1=2 if and only if
Proof. Let d ? deg s (f ). Then there is an n-variate
polynomial of degree at most d such
that g(ff) ? 0 if and only if f (ff) = 1. By shifting
the polynomial by a small constant we may assume
that g(ff) is never 0. We may assume without loss of
generality that the sum of the absolute values of the
coefficients of g is 1. Consider the following randomized
decision tree algorithm: choose a monomial of g
at random, where the probability a given monomial is
chosen is the absolute value of its coefficient. Probe
the variables of the monomial and output the product
of the values. It is easily seen that for any assignment
ff, the probability of correctly evaluating f (ff) minus
the probability of incorrectly evaluating f(ff) is equal
to jg(ff)j ? 0 (here we use that our domain is f\Gamma1; 1g).
Thus for any ff this algorithm correctly evaluates f (ff)
with probability exceeding 1/2.
Now suppose p(f; d) ? 1=2. There must exist
a randomized decision tree algorithm Q on depth d
trees that evaluates f (ff) correctly with probability
exceeding 1/2. Now, it is well known, and easy to
see (by induction on d, looking at the two subtrees
of the root) that if T is a decision tree of depth d
on variables fx 1 ; . ; xng then there is a polynomial
degree d such that gT
all assignments ff. Define the polynomialg(x 1
to be the sum of Q(T )(g T \Gamma 1=2) where the sum is
over all trees of depth d and Q(T ) is the probability
that T is selected under the distribution Q. Then
1=2. By the
choice of Q, this latter term is positive if and only
Theorem 4.1 now follows easily.
Proof of Theorem 4.1. By Corollary 4.1,
would follow from 2
This holds for all sufficiently large
k since p(f; deg s (f
Also, by Corollary 4.1, to show C
pure
deg s (f suffices to show
all k, which follows immediately from the fact,
by Proposition 4.2, that p(f; deg s (f
Remark 1. It is interesting to note that, for k large
enough, it is possible to construct to obtain an optimal
algorithm in which all of the decision trees have a
particularly simple form. The randomized algorithm
in the proof of Proposition 4.2 uses only decision trees
that correspond to computing monomials of g. Using
this randomized algorithm in the proof of the upper
bound of lemma 4.1 the decision trees used in the help-
bits algorithm are all of the same form.
Remark 2. As noted in the introduction, if f is the
majority function the deg s (f so the decision
trees used in the optimal algorithm for H
large k all have depth 1. In the case that f is the majority
function on three variables, Manuel Blum gave
the following constructive protocol to solve H
Enumerate the subsets of [k] having size at least 2k=3.
The number of these sets is 2 ck for some c ! 1. Fix an
encoding of these sets by ck bits. Now given k separate
inputs to the majority-of-3 function, and imagine
the inputs arranged in a k \Theta 3 array. In each row, at
least two of the three entries agree with the majority
value, so there is a column in which at least 2k=3 of
the entries agree with the function value on that col-
umn. For the help bits, we ask for the lowest index of
such a column (requiring 2 bits) and then the set S
of rows for which this column gives the function value
(requiring ck bits.) Armed with this information, the
value of the function on row r is equal to the entry in
that row and the designated column if r 2 S and is
the negative of the entry otherwise.
Remark 3. In the proof of the lower bound in Lemma
4.1, we used Theorem 3.1 in order to deduce that for
any forest F of depth at most d, the probability with
respect to a particular distribution P on assignments
F is correct for all k functions is at most p(f; d) k . In
the special case which is the relevant
case for proving that C Theorem
4.1, there is an alternative argument. We sketch
this argument, which has the benefit that it extends to
other models besides decision trees, as will be seen in
the next section. As noted above, for
we have p(f; d) = 1=2, and thus for ~
ff selected from
D (the distribution of Lemma 4.2) any decision tree
of depth d agrees with f with probability exactly 1/2.
In particular, this can be shown to imply that if we
fix the values of any d variables then either that partial
assignment occurs with probability 0 under -
D, or
that the value of f conditioned on this assignment is
unbiased.
Now, define the random variable c i to be 0 if
We want to show
that the probability that c is at most
In fact, the distribution on
uniform on f0; 1g k . By the XOR lemma of [Vaz] (see
also [CGHFRS]) a distribution over f0; 1g k is uniform
if for any subset J of [k], the random variable c J defined
to be the XOR of the c i for
s J be the probability that c J = 0. The event c
is the same as the event that T J ( ~
is equal to f J ( ~
Now by combining
the decision trees fT i ji 2 Jg we can get a single decision
tree of depth at most jJ jd that computes T J .
We claim that such a decision tree must agree with f J
with probability exactly 1/2, which is enough to finish
the argument. We prove the claim by showing that for
each leaf of the tree T J that is reached with nonzero
probability, f J (~ff) conditioned on ~
ff reaching the leaf
is unbiased. For each such leaf of the tree, there is
an such that at most d variables of X i appear
on the path. Recall that the value of f i is unbiased
when conditioned on the values of these d variables.
If we further condition the value of f J by the values
of all variables not in X i , then f i is still unbiased and
therefore so is f J .
Remark 4. One implication of Theorem 4.1 is that
for large enough k, the best algorithm for H
uses pure trees. It is reasonable to speculate that this
is the case for H k;l (f ) for all k and l, and this is open.
For the case is interesting to note that for
the case it is not hard to show
that pure tree algorithm can not do better than C(f ),
the ordinary decision tree complexity of f . To see this,
note that the help bit partitions the set of assignments
of into two groups A 1 and A 2 . It is not
hard to see that either the set of assignments on X 1
induced by A 1 is all of B X1 , or the set of assignments
on induced by A 2 must be all of B X2 . In the first
case, then given A 1 , a pure tree computation for f on
1 is as hard as the problem without the help bits,
and in the second case, then given A 2 , a pure tree
computation for f on X 2 is as hard as the problem
without the help bits.
5 Other Models
Some of the ideas used so far are also relevant to other
models of computation. We can get results for these
models that are similar to but neither as precise or
as strong as what we obtain for decision trees. It is
convenient to describe our results in the following very
general framework. We fix some computational model
for computing a function f on input ff 2 X , and some
class, FEAS, of "feasible" algorithms.
Our results will only hold for classes having certain
closure properties. A class FEAS is closed under
k-counting if for any k algorithms in FEAS, any
algorithm that runs all k of these algorithms on the
input and accepts or rejects based on the number of
computations out of k that accept, is also in FEAS.
Examples of such classes are polynomial size circuits,
which are closed under poly-counting, and polylog-bit
communication complexity protocols which are closed
under polylog-counting.
From such a class we define when a multi-input
algorithm is feasible. An algorithm for computing a
function f on a pair of inputs ff is said to
be rectangularly-feasible, in FEAS   , if for every fixed
value of ff 1 the induced algorithm for f is in FEAS,
and for every fixed value of ff 2 the induced algorithm
for f is in FEAS. Notice that for the two examples
mentioned above (and essentially any model one may
think of), FEAS ae FEAS   . Thus, for example, for
the case of poly-size circuits, the lower bounds given
below for two-input algorithms apply to all poly-size
circuits as well.
5.1 Products
A product theorem in such a setting may be proven using
Yao's XOR-lemma [Y2], which we observe applies
in this general setting. Let D 1 ; D 2 distributions, and
Lemma 5.1 (Yao) Assume that FEAS is closed under
k-counting. Then
From this one can deduce an "approximate product
theorem".
Theorem 5.1 Assume that FEAS is closed under k-
counting. Then
Proof. Fix an algorithm A in FEAS   , and denote by
pY Y the probability that it is correct on both inputs,
by pNN the probability that it is incorrect on both, by
pY N the probability that it is correct only on the first
input and by pNY the probability that it is correct
only on the second input. Since for every fixed value
of ff 1 the probability that A is correct on f 2 is at
most averaging over all ff 1 , we have
Similarly, Finally, Yao's
xor-lemma implies
\Omega\Gamma10 . These inequalities, together with the
fact that p YY +p Y N directly imply
\Omega\Gamma/1 , which proves the lemma.
5.2 Help Bits
We can use the approximate product theorem to get
help-bit results for randomized algorithms. Given a
class of "feasible algorithms" FEAS, We say that a
function is randomly feasibly computable, in RFC, if
there exists a probability distribution on algorithms in
FEAS such that for any input, an algorithm chosen
from this distribution will be be correct on f with
probability of at least 2=3. The constant 2=3 is not
important as the usual "amplification" lemmas work
in this general case.
Lemma 5.2 If FEAS is closed under k-counting
then the constant 2=3 can be replaced by 1=2
(or by 2 \Gammak ) without changing the class RFC.
For the case where FEAS is the class of polynomial
size circuits, it is known that randomization does
not increase power, and thus RFC is exactly equal
to the functions computable by deterministic poly-
size circuits. For the case where FEAS is polylog-
bit communication protocols, RFC is the functions
computable by randomized polylog-bit protocols with
two-sided error.
Let us define what is feasible computation with a
help-bit. Let FEAS be a given class of algorithms.
A 1-help-bit-feasible algorithm, in FEAS 1 , is a set
of two algorithms A 0 ; A 1 in FEAS, and a boolean
function h, whose value on input ff is the output of
A h(ff) . A function is in RFC 1 if there is a FEAS 1

algorithm for computing two copies of f , which on
every pair of inputs is correct on both with probability
of at least 2=3. We then can prove a randomized help-
bit theorem.
Theorem 5.2 If FEAS is closed under O(1)-
counting then RFC
Proof. Assume that f 62 RFC then, amplifying and
similarly to lemma 4.2, there exists a distribution D
such that q D (f ; FEAS) - 0:51. Using the approximate
product theorem, any FEAS   algorithm for two
copies of f can be correct on at most 0:51 2 +o(1) fraction
of inputs (under distribution D \Theta D). If follows
that any FEAS 1
algorithm can be correct with probability
at most twice that, a probability smaller than
2=3 (again probability taken over a pair of inputs chosen
from D \Theta D.) This in turn implies that f 62 RFC 1 .
For the case of boolean circuits, this was proven in
[ABG].
5.3 The log k Barrier
The "approximate product" theorem and the "ran-
domized help-bit" theorem can be naturally generalized
to up to log k functions where the family FEAS is
closed under k-counting. After that, these techniques
break down. It is unknown for example whether a
polynomial size circuit using n help-bits can compute
n+1 copies of function which doesn't have polynomial
size circuits. One can show that in a black box model,
alternatively, relative to a particular oracle, that the
generalizations are false using !(log
Consider the model of polynomial-size circuits each
with access to the same black-box.
Theorem 5.3 There is a black-box so that there exists
a Boolean function f which can't be computed by
a polynomial-sized circuit family, but
help-bits will allow a polynomial-sized circuit to always
compute the answer to n disjoint copies of f , where n
is the input size to f .
Proof. It is well know that a random f can't
be computed by a polynomial-sized circuit. Fix
such an f . A successful circuit would take inputs
and output the vector V =!
in the black-box
in such a way that a circuit without help-bits can't
find it, but a circuit with help-bits goes directly to it.
Let n be the size of each X i and choose n. For
each input tuple, and output V do the following: Let
s be a random l(n)-bit string. Place V in the location
indexed by place a
"SORRY" in location t. By a standard
counting argument, one can show that no polynomial-
sized circuit family (with access to the black box) can
answer correctly on all n-tuples of inputs. However,
given l help-bits, it is easy to query the oracle at the
location revealing the answer tuple.
It is interesting to note that the Yao XOR lemma
fails relative to this black-box in the sense that once we
XOR more than l(n) variables the parity stops getting
harder to compute. In other words, the XOR lemma
has the same log n barrier as above.

Acknowledgement

. The authors have had many
conversations with several people regarding this re-
search. We would especially like to acknowledge the
contributions of Richard Beigel, Nati Linial, Russell
Impagliazzo, and Avi Wigderson.



--R

Some connections between bounded query classes and nonuniform complexity
On the extended direct sum conjecture
Lower bounds for constant depth circuits in the presence of help bits
The bit extraction problem of t-resilient functions
Amortized Communication Complexity
On the complexity of 2-output Boolean networks
"Advances in Computational Complexity Theory"

Fractional Covers and Communication Com- plexity
On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity
A Direct Product Theorem

Rounds in Communication Complexity Revisited
Realizing Boolean functions on disjoint set of variables

On the synthesis of self-correcting schemes from functional elements with a small number of reliable components

Theory and applications of trapdoor functions
Probabilistic computations: towards a unified measure of complexity
--TR

--CTR
Ronen Shaltiel, Towards proving strong direct product theorems, Computational Complexity, v.12 n.1/2, p.1-22, July 2004
Paul Beame , Toniann Pitassi , Nathan Segerlind , Avi Wigderson, A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness, Computational Complexity, v.15 n.4, p.391-432, December  2006
Anna Gl , Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoretical Computer Science, v.379 n.3, p.405-417, June, 2007
help bits;decision trees