英语论文网

aeli
Academy of Sciences.
zDepartment of Computer Science, Carnegie-Mellon University, Pittsburgh, PA 15213. This
research was partially supported by NSF grant CCR-9119319.
xDepartment of Mathematics and RUTCOR, Rutgers University, New Brunswick, NJ 08903
(saks@math.rutgers.edu). This research was supported in part by NSF contracts CCR-9215293
and STC{91{19999, and by DIMACS.
1035
1036 N. NISAN, S. RUDICH, AND M. SAKS
the references contained in [Raz]). In this paper we consider tworelated problems ofa similar °avor.
The product problem. Let f be a function, and suppose that for any allowablecomputation that has complexity bounded by c and attempts to compute f, thefraction of inputs on which it correctly computes f is at most p. Suppose that wehave two independent computations, each taking as input the same ordered pair a; bof inputs to f, where the rst computation is trying to compute f(a) and the secondis 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 p2? What aboutthe analogous question for k independent computations and k inputs?
If the rst computation accesses only a and the second accesses only b, then thep2 upper bound is trivial. Intuition suggests that there is no advantage in having each
computation access the input of the other. 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]. A version of this problem for interactive proofs, the well-known \parallelrepetition problem," was recently solved by Raz [Raz].
The help-bit problem. Suppose that the complexity of exactly computing theBoolean function f is c. Suppose that we wish to compute f on two inputs a and b,and are 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) andf(b) can each be evaluated by a computation of complexity less than c, and if so, how
much can the complexity be reduced below c? How about computing f on k inputswith k ¡ 1 help bits?
The notion of help bits is essentially the same as that of bounded queries, whichwere studied in recursion theory [Be87]. The term \help bit" was introduced inthe context of constant depth circuits in [Cai] and was also studied in the context ofBoolean circuits in [ABG]. The point here is that if we have k inputs, then we can use
k help bits to obtain the value of f on each of the inputs, and no further computation
is necessary. With only k ¡ 1 help bits, we can for instance obtain the value of f at
k ¡ 1 inputs, but then we still need complexity c to compute f on the last input. Is
there a more e ective use of the help bits?
In this paper we consider these problems in the context of 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 de nition is given in section 2. While it is an easy
exercise to see that \direct-sum" holds for decision-tree depth, the other two problemsare more dicult. Our answer for the product problem is a quali ed \Yes."
Theorem 1.1. Let f be a Boolean function and suppose that any depth-d decisiontree computes f correctly on a fraction at most p of the in