A composition theorem for decision tree complexity
We completely characterize the complexity in
the decision tree model of computing composite relations of the form h=g∘(f1,…,fn),
where each relation fi is Boolean-valued. Immediate corollaries include a
direct sum theorem for decision tree complexity and a tight characterization of
the decision tree complexity of iterated Boolean functions.
The article: PDF (189 KB)
Source material: ZIP (105 KB)
BibTeX entry for this article (265 bytes)
No comments:
Post a Comment