Products and help bits in decision trees

Citation
N. Nisan et al., Products and help bits in decision trees, SIAM J COMP, 28(3), 1999, pp. 1035-1050
Citations number
23
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
28
Issue
3
Year of publication
1999
Pages
1035 - 1050
Database
ISI
SICI code
0097-5397(19990319)28:3<1035:PAHBID>2.0.ZU;2-4
Abstract
We investigate two problems concerning the complexity of evaluating a funct ion 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 t he fraction of input k-tuples for which all k decision trees are correct. A ssume that for a single input to f, the best depth-d decision tree is corre ct on a fraction p of inputs. We prove that the maximum fraction of k-tuple s on which k depth-d algorithms are all correct is at most p(k), which is t he 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 t o k ? 1 arbitrary binary questions (help-bit queries) can be asked about th e 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 co mplexity 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 deg(s) (f), which is the minimum degree of a multivariate polynomial whose sign i s equal to f.