Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR08-096 | 8th September 2008 00:00

#### Multitask Efficiencies in the Decision Tree Model

TR08-096
Authors: Andrew Drucker
Publication: 11th November 2008 14:36
In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ways in which the joint computational complexity can behave when all the $f_i$ are evaluated on a \textit{common} input.