Multitask Efficiencies in the Decision Tree Model

Andrew Drucker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In Direct Sum problems \cite{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. We focus on the deterministic decision tree model, with depth as the complexity measure; in this model we prove a result to the effect that the `obvious' constraints on joint computational complexity are essentially the only ones. The proof uses an intriguing new type of cryptographic data structure called a `mystery bin' which we construct using a small polynomial separation between deterministic and unambiguous query complexity shown by Savick\'{y}. We also pose a variant of the Direct Sum Conjecture of \cite{KRW} which, if proved for a single family of functions, could yield an analogous result for models such as the communication model.
Original languageEnglish
Title of host publicationProceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages286-297
Number of pages12
ISBN (Electronic) 978-0-7695-3717-7
DOIs
Publication statusPublished - Jul 2009

Fingerprint

Dive into the research topics of 'Multitask Efficiencies in the Decision Tree Model'. Together they form a unique fingerprint.

Cite this