英语论文网

NOAM NISANy, STEVEN RUDICHz, AND MICHAEL SAKSx
SIAM J. COMPUT. c° 1999 Society for Industrial and Applied Mathematics
Vol. 28, No. 3, pp. 1035{1050
Abstract. We investigate two problems concerning the complexity of evaluating a function fon k distinct inputs by k parallel decision-tree algorithms.In the product problem, for some xed depth bound d, we seek 代写留学生硕士毕业论文to maximize the fraction of inputk-tuples for which all k decision trees are correct. Assume that for a single input to f, the bestdepth-d decision tree is correct on a fraction p of inputs. We prove that the maximum fraction ofk-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 neednot 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 inputthat is consistent with the help bits. The complexity here is the maximum depth of any of the treesin the algorithm. We show that for all k suciently large, this complexity isequal to degs(f), whichis the minimum degree of a multivariate polynomial whose sign is equal to f.
Key words. decision trees, help bits
AMS subject classi cations. 68Q05, 68Q25, 68R99, 05D99
PII. S0097539795282444
1. Introduction. Pick your favorite computation model and complexity measure,e.g., Boolean circuit size, communication complexity, decision-tree depth, interactiveproof length, tensor rank, etc. Any attempt to understand such a model andcomplexity measure requires understanding the ways that an \unreasonable" computationcan be more ecient than a \reasonable" one. Of course, what is reasonablechanges 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 extentis this intuition valid in a given model? The following question is the most commonway of formalizing this.
The direct-sum problem. Suppose that the complexity of computing somefunctionf is c. Is it true that computing f twice, on two unrelated inputs, requires complexity
2c? How about computing f on k unrelated inputs?Versions of this question were rst studied in the context of Boolean circuits
[Ulig, Paul, GF]. Subsequent work has concerned bilinear circuits [JT, Bsh], Booleancircuits [FKN], communication complexity [KRW, KKN], and interactive proofs (seeReceived by the editors March 6, 1995; accepted for publication (in revised form) March 13,1997; published electronically January 29, 1999. A preliminary version of this paper appeared inProceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994.
https://www.siam.org/journals/sicomp/28-3/28244.html
yComputer Science Department, Hebrew University, Jerusalem, Israel (noam@cs.huji.ac.il). This
research was supported by BSF grant 92-00043 and by a Wolfson award administered by the Isr本论文由英语论文网提供整理，提供论文代写，英语论文代写，代写论文，代写英语论文，代写留学生论文，代写英文论文，留学生论文代写相关核心关键词搜索。