Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-096 | 8th September 2008 00:00

Multitask Efficiencies in the Decision Tree Model

RSS-Feed




TR08-096
Authors: Andrew Drucker
Publication: 11th November 2008 14:36
Downloads: 3672
Keywords: 


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.



ISSN 1433-8092 | Imprint