ECCC-Report TR08-096https://eccc.weizmann.ac.il/report/2008/096Comments and Revisions published for TR08-096en-usTue, 11 Nov 2008 14:36:13 +0200
Paper TR08-096
| Multitask Efficiencies in the Decision Tree Model |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2008/096In 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.
Tue, 11 Nov 2008 14:36:13 +0200https://eccc.weizmann.ac.il/report/2008/096