__
TR08-096 | 8th September 2008 00:00
__

#### Multitask Efficiencies in the Decision Tree Model

**Abstract:**
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.