Towards proving strong direct product theorems.
A fundamental question of complexity theory is the direct product question. A famous example is Yao's XOR-lemma, in which one assumes that some function f is hard on average for small circuits (meaning that every circuit of some fixed size s which attempts to compute f is wrong on a non-negligible fraction of the inputs) and concludes that every circuit of size s' only has a small advantage over guessing randomly when computing ... f(xk) on independently chosen x1,...,xk. All known proofs of this lemma have the property that s' < s. In words, the circuit which attempts to compute fk is smaller than the circuit which attempts to compute f on a single input! This paper addresses the issue of proving strong direct product assertions, that is, ones in which s'  ks and is in particular larger than s. We study the question of proving strong direct product question for decision trees and communication protocols.
Introduction
1.1 The direct product question
Given a boolean function f over domain X and an integer k, we define a function f
Intuitively, if f is hard on average, (say f can be computed correctly by some computational class
on at most a (1/2 + p)-fraction of of the inputs), then we expect f #k to be computed correctly
on at most a (1/2 )-fraction of the inputs. This intuition is based on an information theoretic
analog. In the information theoretic setup f is a biased random coin with probability of heads
#k is the exclusive-or of k such independent coins which indeed induces a coin with
probability of heads roughly equal to 1/2 . Transferring this intuition from the information
theoretic setting to computational settings is much more involved than one can expect at first
glance. Such assertions are referred to as direct product assertions.
Let us present the direct product question in a general computational setting. Consider some
computational resource (such as circuit size, decision tree depth, number of bits exchanged in a
communication protocol. Let Res r denote the class of all functions computable using r "units"
of the resource. In this paper we consider the following classes:
. Size s the family of functions computed by circuits of size s.
. Comm c the family of functions (on two inputs) computed by a communication protocol which
exchanges c bits.
. Depth d the family of functions computed by decision trees of depth d.
Saying that a function f is "hard on average" for Res r means that every algorithm from Res r
computes f correctly on a bounded fraction of the inputs 1 . We use the following notation:
Suc Res
Since f is boolean it can always be computed on at least half the inputs. We will be interested
in the advantage the algorithm can get over guessing.
Adv Res
The direct product question can now be presented as follows: 2
The direct product problem: Is it true that for all f and r, k:
Adv Res
Where r # and p # are parameters. In words, one supposes that f is hard on the average to algorithms
with r units of the resource, and concludes that f #k is hard on the average to algorithms having
1 In this paper we restrict ourselves to average case hardness relative to the uniform distribution. Indeed, some of
out results do not generalize to arbitrary probability distributions. See the discussion at the end of the paper.
di#erent variant that is sometimes considered is the concatenation variant. It involves replacing the function
f #k with f (k) (x1 ,    , xk asking weather Suc Res
These two
variants are closely related and in particular a strong direct product assertion for f #k implies a strong direct product
assertion for f (k) . Exact details are omitted from this version.
r # units of the resource. Naturally, the assertion is stronger when r # is large and p # is small. we say
that the assertion is optimal when r It seems reasonable to allow the algorithm
attempting to compute f #k to use kr units of the resource, as its input is k times larger than that
of the algorithm attempting to compute f . In this paper we are interested in proving direct product
assertions for large r # . We will call such assertions strong if r # kr) and
p#
The strong-direct product problem: Is it true that for all f and r, k:
Adv Res
Res#
In our results r # is a parameter, and the fixing of r # kr) is made to simplify the presentation 3 .
1.2 Previous work
The most studied model for direct product results is circuit complexity. The so called "Yao's
XOR-lemma", [Yao82] can be stated this way in our terminology:
Adv Size
is the number of inputs of f . Note that in this result s # is actually
smaller than s. In other words the circuit which tries to compute f on many instances is smaller
than the one which tries to compute f on one instance. This is unavoidable in the sense that all
known proofs of this lemma, [Lev85, Imp95, GNW95, IW97] work by proving the contra-positive
claim: Adv Size
s (f) > p, and use the circuit which computes f #k as a
sub-circuit in the circuit that computes f . (See [GNW95] for a survey on Yao's XOR-lemma).
Another unpleasant feature of this result is that p # is always larger than 1/s which means that
one does not benefit from taking k > log s. An unpublished result which is commonly attributed to
Steven Rudich shows that all "black-box" 4 proofs of the XOR-lemma su#er from this flaw. Thus,
proving a result in which s # > s or p # < 1/s seems to be beyond our current ability, as we do not
know how to handle boolean circuits other than using them as black boxes.
The direct product question was also studied in other computational models. Nisan et al,
[NRS94] consider a specific variant of decision trees which they call "decision forests". A k-decision
forest of depth d consists of k decision trees of depth d. Each is allowed to query all k inputs,
and the i'th tree is supposed to compute f(x i ). The final output of the decision forest is the
concatenation of outputs of individual trees. Let us denote the class of all functions computable
by depth d k-decision forests by F orest k,d . With this terminology their result could be stated this
way:
Suc Depth
d
orest
(Here f (k)
Parnafes et al, [PRW97] used the technique of Raz's parallel repetition theorem [Raz98] to prove
a product theorem for "forests of c-bit communication protocols" 5 . Their result is similar in flavor
3 In particular, our negative results work whenever p # < p and apply to "intermediate" values of r # . Our positive
result for communication complexity gives a tradeo# between r # and p #
4 "Black box" refers to proofs like the ones mentioned above, that use a circuit which computes f #k too well as a
black box in a circuit that computes f too well.
5 A forest of c-bit communication protocol is a collection of k c-bit communication protocols each is over all k
inputs, and the i'th protocol is supposed to compute the function on the i'th input.
to that of [NRS94] with the exception that
p# k/c) . This dependence on c comes from the
technique of Raz, but whereas a dependence on c is unavoidable in the parallel repetition theorem
(as was shown by [FV96]), it is open weather the result of [PRW97] is best possible for forests of
communication protocols.
1.3 Our results
Our first result is a general counterexample which shows that strong direct product assertions, (or
even ones with r # su#ciently larger than r) are simply not true. We can apply this counterexample
whenever there is a function such that Adv Res
r
(f) is small, yet f # Res  r for  r not much larger
than r. This means that whenever a computational model has functions which are hard when
given r units of the resource and easy when given slightly more units we cannot expect a strong
direct product assertion to hold. The counterexample applies to boolean circuits, communication
protocols and decision trees.
While this counterexample rules out the possibility of having strong direct product assertions,
it seems to exploit defects in the formulation of the problem rather than show that our general
intuition for direct product assertions is false. Intuitively, the algorithm of the counterexample
is able to compute f #k correctly with high probability by using its resources in an imbalanced
way allocating a lot of its resources to specific instances. This is beneficial to the algorithm as
the function of the counterexample is with high probability easy on many instances. This does not
contradict our intuition why strong direct product assertions are true as this is not a counterexample
to our belief that it is not beneficial for the algorithm to correlate computations on di#erent inputs.
We elaborate on this point in section 3.3. In any case, as the assertion is not true as is, in order to
capture our intuition and prove a strong direct product assertion we would have to either strengthen
the assumption or weaken the conclusion.
1.3.1 Strengthening the assumption: demanding more information on the function
The function presented in the counterexample has the property that it has a large subset of its
inputs on which it is easy, and checking weather an input belongs to this subset is feasible for the
algorithm. It is natural to ask weather a strong direct product assertion holds for functions which
do not have this property. More generally, what kind of restrictions can we place on the function
in order to make a strong product assertion hold?
We provide an answer to these questions for communication protocols. We do this by analyzing
the discrepancy of f #k . (The discrepancy of f , denoted by disc(f) measures how imbalanced is f
in large rectangles). Using ideas from [NW94], we are able to show that:
It is standard that Adv Comm
c (f) # disc(f)2 c , this immediately entails:
Adv Comm
This inequality has the following interpretation: If the fact that f is hard on average for c-bit
communication protocols follows from the fact that f has low discrepancy then a strong product
theorem holds for f . We would like to point out that the "discrepancy method" is the most common
way to prove that f is hard on average for communication protocols.
1.3.2 Weakening the conclusion: imposing restrictions on the algorithm
The algorithm presented in the counterexample has the property that it uses its resource in an
"unfair" way spending more than r units on particular inputs. It is natural to ask weather a strong
direct product assertion holds for "fair" algorithms. More generally, what kind of restrictions can
we place on the algorithm in order to make a strong direct product assertion hold?
Intuitively, the forest model of [NRS94] is such a restriction. However, we would like our
algorithm to be a restricted algorithm from
Res# kr) . We suggest to impose a "fairness" restriction
on the algorithm. Some evidence to the potential of this direction is that we can prove an optimal
direct product theorem for "fair" decision trees.
A decision tree of depth kd over variables x 1 ,    , x k is fair if on every path from the root to
the leaf at most d bits from each variable are queried. Let us denote the class of fair decision trees
of depth kd by F airDepth kd . It is not hard to prove the following theorem:
Adv Depth
d
kd
It is our hope that the two directions we present here can be extended to prove strong direct
product assertions for stronger computational models.
1.4 Organization of the paper
In section 3 we present our counterexample. In section 4 we prove a strong direct product theorem
for communication protocols via the discrepancy method. In section 5 we prove a strong direct
product theorem for fair decision trees.
Preliminaries
We use # to denote the exclusive or. For two matrices A and B of size N N , we use
A# B to
denote the tensor product of the two matrices. More precisely
A# B is an N 2
we think of this matrix as an N N matrix with entries being matrices of size N N and place a
copy of the matrix A ij  B in the i'th row and j'th column. The tensor product of A with itself k
times is denoted by
A# k .
We use Size s to denote the class of all functions (over arbitrary number of inputs) computable
by boolean circuits of size s.
We use Comm c to denote the class of all functions of two arguments which can be computed
by a c-bit communication protocol. The exact definition of a communication protocol can be found
in any textbook on this subject, (i.e. [KN97]). The only property of such protocols used in this
paper is that such a protocol induces a partition of the inputs into 2 c rectangles.
We use Depth d to denote the class of all functions computed by a decision tree of depth d.
Whereas a decision tree is a binary tree in which every internal node is labeled with a specific bit
of the input, and leafs are labeled with outputs. An input to the decision tree defines a path from
root to leaf in the obvious way, and the output of the tree on this input is the leaf label.
3 A general counterexample
In this section we give a general counterexample to direct product results with r
for boolean circuits, decision trees and communication protocols. We show that given a function
which is hard given r units of the resource and easy given slightly more units, we can construct a
function which is hard given r units of the resource, and yet computing it on k independent inputs
is easy. We present the example using our general notation in section 3.1 and then draw conclusions
for specific models in section 3.2. In section 3.3 we discuss the implications of this counterexample.
3.1 The general setting
We will present a function which is hard on average given r units of the resource, yet f #k can be
computed correctly with probability units of the resource, for r # su#ciently larger
than r.
The counterexample works assuming the existence of a function which is hard given r units of
the resource, and easy given slightly more units. Formally, we assume the existence of a function
# {0, 1} and r <  r such that:
. Suc Res
. g # Res
r .
Another ingredient is an easy function (over few inputs) which answers one on a prescribed
fraction of its inputs. Formally, Given a number q < 1 we assume the existence of a function
# {0, 1} and a small number r # such that
. h # Res r #
. Pr y#R {0,1} l
Our counterexample function is a combination of the easy and hard functions.
{0, 1} l
# {0, 1} in the following way.
An algorithm for computing f #k can utilize its resource smartly by spending a lot of the resource
on the (expectedly few) inputs in which f involves the hard function, and spend a very small amount
on other inputs. This is made formal in the following lemma.
Lemma 1 The following inequalities hold:
. Suc Res
. If r # 2qkr
Proof: (of lemma 1) For the first item note that an algorithm which is correct on f with probability
greater than 1 - q/4 must be correct on g with probability greater than 3/4. For the second and
third item, note that when (y 1 ,    , y k ) are randomly chosen, we expect qk of them to have h(y
By Cherno#'s inequality The probability that more than 2qk of them have h(y bounded by
. We can check which of the y i 's have h(y using kr # units of the resource. Assuming
the constant function zero can be computed using 0 units of the resource, we can compute the
function f on (x i , y i )'s such that h(y i ) Assuming that there are at most 2qk of these we can use
2qkr units to compute the outputs of the "hard inputs". Thus, Suc Res
Corollary 1 If
kr
-#
Remark 1 It should be noted that the function f constructed here isn't as pathological as it may
seem at first glance. Impagliazzo's hard core theorem [Imp95], shows that (at least in the boolean
circuit model) every function f with Suc Size
has a large subset of the inputs on which
any (slightly smaller) circuit succeeds with probability roughly 1/2. In our example the "hard core"
of f is the function g. The unnatural state of a#airs in our example is that the function is easy
outside of the hard core, and deciding weather an input is in the hard core is an easy computational
task.
3.2 Conclusions for specific models
In order to use the counterexample from the previous section we will show the existence of the
required "building block" functions g and h for various computational models.
We will use the same function as "h" in all constructions. Namely we choose
l, and define h : {0, 1} l
# {0, 1} to take the value one if all its inputs are zeroes, and zero otherwise.
It is immediate to verify that h is in Size O(l) , Comm l , Depth l , and accepts a q-fraction of its inputs.
3.2.1 Boolean Circuits
There is a hierarchy theorem for circuits which provides us with a function # which is computable
in size s but not in size s - n. The following formulation is weaker than the best known result.
Theorem 1 [PW86] If  s < 2 n
then there is a function # : {0, 1} n
# {0, 1}, such that # Size  s
and # Size  s-n .
We can now use hardness amplification techniques to convert # into a function which is hard
on average for slightly smaller size 6 .
Theorem 2 [Imp95, STV99] If # Size " s then there exists a function
# {0, 1} such
that Suc Size
By combining theorems 1,2 we get the existence of the function g we wanted.
Corollary 2 If s < 2 #n , (for some constant #) then there exists a function
such that Suc Size
s
Using lemma 1 we conclude that Adv Size
s (f) for
Where c and d are constants which can depend on the constant hidden in
the#4528762 This
means that strong direct product assertions are not true for boolean circuits 7 .
6 Some of these hardness amplification techniques involve proving XOR-lemmas for circuits. Thus, the counterexample
is actually based on a true direct product assertion! The hardness amplification results used are explicit in
the sense that the new function can be e#ciently computed given access to the initial one. This is reflected in the
"moreover clause" in the next lemma, and is not necessary for our purposes. The result stated is a strong variant of
hardness amplification in the sense that the new function has roughly the same number of inputs as the initial one.
7 We can also draw some conclusion for general s # . The only weakness of this example is that the starting advantage
is not a constant.
3.2.2 Communication Protocols
For communication complexity we use the inner product function g(x, As all
functions over n bit inputs, g # Comm n . It is known that g is very hard on average given n/4 bits
of communication 8 .
Theorem 3 [CG88] Adv Comm
Using lemma 1 we conclude that Adv Comm
kc
c (f) for a su#ciently small constant
q and a su#ciently large constant k. Thus, there are no strong direct product assertions for
communication protocols evan when starting from a constant advantage.
Remark 2 In this example c is very large and in particular  this can be avoided by "padding"
the inputs of the two players to increase n.
3.2.3 Decision Trees
For decision trees we choose g to be the parity function It is immediate that
# Depth n and Adv Depth
Once again we can use lemma 1 to get a counterexample with
the same behavior of parameters as the counterexample for communication protocols.
3.3 How bad is this counterexample?
It seems that the counterexample is not so bad in the sense that it does not contradict our intuition
as to why direct product assertions are true. When proving a direct product assertion, the main
task is to show that the algorithm does not benefit from correlating computations on di#erent
inputs. In the counterexample we presented no such correlations occur. Instead, the algorithm
uses its resource in an unbalanced way, spending a lot of it on particular inputs. In particular, the
algorithm is able to compute f on single instances with advantage greater than p. This is something
which is ruled out when r # r.
We would like to change the formulation of the direct product problem to rule out such cases.
In the next two sections we suggest two such strengthenings. One involves adding assumptions on
the function f , in hope that such assumptions can prevent the situation of the counterexample.
Intuitively, if f is hard in a "robust way", any additional resources spent on f on one instance will
result in a "loss" in another instance, and it will not be beneficial to treat the inputs unfairly. The
other involves restricting the algorithm in a way that insures that it cannot have advantage greater
than p when attempting to compute f on any single coordinate.
4 A discrepancy product theorem
In the previous section we've seen that a direct product assertion for communication protocols is
not true if we allow the protocol trying to compute f #k to communicate more bits than the protocol
attempting to compute f . In this section we show that if f has "low discrepancy" then a strong
direct product theorem holds for f .
It will be convenient to think of the outputs of a communication complexity problem as being
{-1, 1} rather than {0, 1}. Thus, such a problem can be viewed as a matrix with entries in {-1, 1}.
8 Preparing for section 4, we remark that the proof of that statement works by showing that g has very low
discrepancy.
This matrix is not necessarily a square matrix, as the input of the di#erent players may be chosen
from sets of di#erent sizes. Still, in the remainder of this section we will assume that the matrix is
a square matrix. Our results follow for the general case as well, and this assumption is made only
to simplify the presentation. The choice of {-1, 1} is made so that the tensor product of A with
itself k times, (denoted by
exactly the matrix of the communication problem A #k .
For a set C # [N ], we use #C to denote the characteristic vector of C, that is (# C
A be an N by N matrix with entries in {-1, 1}. For a rectangle
where C, D # [N ] we define:
C A# D |
The discrepancy of A is defined in the following way:
where the maximum is taken over all rectangles
For a fixed rectangle
C A# D |
|CD|
measures how imbalanced is the matrix A in the
rectangle R. If R is a rectangle reached in a leaf of a communication protocol then half this quantity
is the advantage the protocol gets over random guessing in the rectangle R. The definition of
multiplies this quantity by |CD| N 2
to take into account the volume of the rectangle. More
precisely, the advantage over random guessing is multiplied by the volume of the rectangle R to give
the contribution of R to the advantage of the protocol over random guessing. This normalization is
made so that low discrepancy will imply that the problem is hard on average. This is made formal
in the following lemma.
Proof: (of lemma 2) Let P be the c-bit communication protocol which achieves Adv Comm
c (A). A cbit
communication protocol partitions A into 2 c disjoint rectangles. On each rectangle R
the advantage of the protocol is bounded by |# t
. We can now bound the advantage of
Adv Comm
c
The requirement that disc(A) is small is stronger than that A is hard on average. Still, the most
common way of showing that communication problems are hard on average is by showing that they
have low discrepancy. Intuitively, low discrepancy provides a "smooth" hardness condition which
rules out the counterexample of the previous section.
Remark 3 Note that for a sub-matrix B of A, the discrepancy of B is upper bounded by the
discrepancy of A times the ratio of the volumes of B and A. Thus, by lemma 2, low discrepancy
means that any large sub-matrix of A is average case hard. Another nice feature of this setup is
that checking membership in B is easy for communication protocols and can be done by exchanging
bits. Thus, it captures our intuition that the subsets of inputs on which we bound the function
are easily computable. This should be compared to remark 1.
The main theorem of this paper shows that the discrepancy of a taking the tensor product of
A with itself k times goes down exponentially with k.
Theorem 4
kThis has the following interpretation: Suppose, (as is often the case), that fact that Adv Comm
p follows from the fact that disc(A) < p2 -c . In that case:
Adv Comm
In words, we get a strong direct product theorem for A. This is stated with more generality in the
next corollary.
Corollary 3 For every c # , Adv Comm
Note that in this formulation one can get rid of the constant 3, and get a result on Adv Comm
kc
in terms of disc(A).
The proof of the theorem will require the definition of the spectral norm of a matrix A.
Definition 3 For a vector x we use ||x|| 2 to denote the L2-norm of x. For a matrix A, ||A|| 2 is
defined to be
It will be useful to consider equivalent definitions of this norm.
Fact 1 Equivalent definitions for ||A|| 2 are:
1.
2. is an eigenvalue of A t A}
A useful property of ||A|| 2 is that it is multiplicative under tensor product.
Fact 2
The proof of fact 2 consists of two steps: The first is to show this is true for
symmetric matrices. If A is symmetric then there is an orthonormal basis of eigenvectors of A and
is the maximal eigenvalue of A in absolute value. It is easy to see that the
eigenvalues of
A# k are exactly all products of eigenvalues of A. Thus, ||A|| . The fact now
follows for non symmetric matrices by using the second item of fact 1, and the observation that
In the remainder of this section we prove theorem 4. The first step is to express the discrepancy
in terms of the spectral norm. We then use the multiplicativity of the spectral norm to get the
conclusion. The second item of fact 1 enables us to upper bound the discrepancy using the spectral
norm.
Proof: (of lemma be the rectangle such that (A). We have that
C A# D |
. We define |D|. Note that ||# C
it follows from the first item of fact 1 that
C A# D |
C A# D |
In [NW94], Nisan and Wigderson address the so called "log-rank conjecture" and show that
use ideas from that paper to lower bound the discrepancy
using the spectral norm.
Lemma 4 disc(A)
We start by showing that theorem 4 easily follows from lemma 4.
Proof: (of theorem
The first inequality follow from lemma 3. The second follows from fact 2, and the third follows
from lemma 4.
We want to prove lemma 4 in a similar way to the previous lemma. The first step is a way
to transform a bilinear form with arbitrary vectors into one with characteristic vectors. Such a
transformation was given by Nisan and Wigderson in [NW94].
Lemma 5 [NW94] Let u, v be vectors such that ||u|| # , ||v|| # 1, then there exist a rectangle
such that |# t
For completeness we give the proof of this lemma.
Proof: (of lemma 5) We "split" u and v to their positive coordinates and negative coordinates,
having
. We now have that ||u
and the four vectors are non-negative. Since |u t
then one of the four terms is larger in absolute value than |u t Av|/4. Setting C to be
the non-negative coordinates of the u-part of this term and D to be the non-negative coordinates
of the v-part of this term, we have that |# t
We are now tempted to use lemma 5 directly to prove lemma 4. That is start from u, v such that
get a rectangle with roughly the same value. This will not do since
to get a bound on disc(A) we have to divide by N 2 . Thus, the above argument only gives the non-
impressive estimate: disc(A) # ||A|| 2
. Had it been the case that u and v had ||u|| # , ||v|| # < 1
we could deduce that # 2 disc(A) # ||A|| 2
and do better. We will now show that ||A|| 2 is obtained
by such u and v.
Lemma 6 There are vectors u, v with ||u|| # , ||v|| # such that |u t Av| # ||A||
Proof: (of lemma and y be vectors such that ||x||
Let u be the vector obtained from x by setting the coordinates
in I to zero, and v be the vector obtained from y by setting the coordinates in J to zero. Note
that |I|, |J | # 1/# 2 , (since otherwise the contribution of elements in I (J) to the norm of x (y) is
greater than one). We now have that:
We will now argue that the two terms on the right hand side are small because they involve
small rectangles. We will bound the first term, and the second will follow the same way.
| #
(where the second inequality follows from the Cauchy-Schwartz inequality). Plugging this in the
previous calculation we have that:
Lemma 4 follows from the previous lemmas.
Proof: (of lemma Given a matrix A, we set be the vectors which
existence is given by lemma 6. We now define new vectors
v/#. Note that
Using lemma 5 there exists a rectangle such that
(Note that this result is valid even if # > 1. In that case, it follows directly without using anything).
We conclude that disc(A)
5 Fair decision trees
In this section we prove an optimal direct product theorem for fair decision trees. We start with
the definition of "fairness" for decision trees.
Definition 4 A decision tree over inputs x 1 ,    , x k is (d 1 ,    , d k )-fair if for every 1 # i # k and
on every path from root to leaf the decision tree queries at most d i bits from x i . A decision tree is
d-fair if it is (d,    , d)-fair.
Let F airDepth d 1 ,,d k
denote the class of functions over inputs x 1 ,    , x k computed by d 1 ,    , d k
decision trees. Let F airDepth kd denote F airDepth d,,d .
Theorem 5 Adv F airDepth
kd
d
(f) k .
The proof of this theorem is by induction and is almost similar to that of [NRS94]. To simplify
the notation we will prove it for 2. The proof for general k follows the same way. To have a
stronger induction hypothesis we will prove the following stronger version.
Lemma 7 For every two functions f 1 , f 2 and numbers d 1 , d 2
Proof: (of lemma 7) We prove the lemma by induction over d 1 then the
decision tree does not base its answer on the inputs. It is now standard to check that indeed
To bound Adv F airDepth
let T be a decision tree which achieves this advantage. Without loss of generality the first query
of T is from x 1 . We will use the notation x b is the bit queried by T and y is the
remaining bits. We denote the two sub-trees of T by T 0 and T 1 respectively. For b # {0, 1}, we
define functions We now have:
Here, Adv T (f) is used to denote the advantage of T on f . However, T 0 and T 1 are of depth
are in F airDepth d1 -1,d2 . Applying our induction hypothesis we continue and get
d2
Consider trees P 0 , P 1 which achieve the advantage on g 0 , g 1 . We now construct a tree P of depth
d 1 which starts by querying b and depending on the outcome activates P b . We now have that:
The first equality follows from the definition of P and the second from the fact that P is of depth
d 1 . Plugging this in our previous calculation we prove the lemma.
6 Open problems
The natural direction is to try and extend the ideas of this paper to stronger computational models.
Particular such extensions are:
Extend the technique of section 4 to non-uniform probability distributions. The reason the
current argument does not extend is that we use the fact that small rectangles have small probability.
It will also be nice to be able to handle one sided discrepancy, that is removing the absolute
value from the definition 2. This may require totally di#erent techniques as we are unaware of
an algebraic interpretation of one sided discrepancy. Both extension are motivated by the lower
bound on the disjointness function [BFS86, KS87, Raz92] which uses a one sided discrepancy in a
non-uniform probability distribution.
The next model on which we may want to prove a strong product assertion by imposing a
fairness restriction is communication complexity. It seems that the result of [PRW97] regarding
the forest model does not extend to a fair kc-bit communication protocol.
For some models of computations it may not be obvious how to define "fairness". We suggest
the following definition: An algorithm for x 1 ,    , x k is fair, if for every i and for every
a 1 ,    , a i-1 , a i+1 ,    , a k the "computation" of the algorithm over a 1 ,    , a i-1 , x, a i+1 ,    , a k for
fixed a's and varying x can be simulated by an algorithm with r units of the resource when given
x.
An alternative approach is to replace the "syntactic" fairness condition by a "semantic" one.
Intuitively, the fairness restriction is supposed to guarantee that the algorithm cannot compute the
function on individual coordinates with advantage greater than p. If it is hard to impose fairness
restrictions, one may try to prove the direct product assertion only for algorithms which obey this
semantic restriction.

Acknowledgments

I would like to thank my advisor Avi Wigderson for introducing me to this area, for countless
conversations and for his guidance and support.



--R


Unbiased bits from sources of weak randomness and probabilistic communication complexity.
reduction by parallel repetition-a negative result (preliminary version)
On yao's xor-lemma


Communication Complexity.
The probabilistic communication complexity of set intersection (preliminary version).

Products and help bits in decision trees.
On rank vs. communication complexity.
Direct product results and the GCD problem
Nearly optimal hierarchies for network and formula size.
On the distributed complexity of disjointness.
A parallel repetition theorem.
Pseudorandom generators without the xor lemma.
Theory and applications of trapdoor functions (extended abstract).
--TR
One-way functions and Pseudorandom generators
Unbiased bits from sources of weak randomness and probabilistic communication complexity
A hard-core predicate for all one-way functions
The probabilistic communication complexity of set intersection
On the distributional complexity of disjointness
exponential circuits
Direct product results and the GCD problem, in old and new communication models
Communication complexity
A Parallel Repetition Theorem
Products and Help Bits in Decision Trees
Hard-core distributions for somewhat hard problems
Reduction by Parallel RepetitionMYAMPERSAND#x2014;A Negative Result
product theorems;average case complexity;hardness amplification;XOR-lemma