期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2014
卷号：2014
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：We completely characterise the complexity in the decision tree model of computing composite relations of the form $h = g \circ (f^1,\dots,f^n)$, where each relation $f^i$ is boolean-valued. Immediate corollaries include a direct sum theorem for decision tree complexity and a tight characterisation of the decision tree complexity of iterated boolean functions
