Please use this identifier to cite or link to this item:
Title: Optimal direct sum results for deterministic and randomized decision tree complexity
Authors: Jain, R. 
Klauck, H.
Santha, M. 
Keywords: Computational complexity
Decision tree complexity
Direct sum
Issue Date: 2010
Citation: Jain, R., Klauck, H., Santha, M. (2010). Optimal direct sum results for deterministic and randomized decision tree complexity. Information Processing Letters 110 (20) : 893-897. ScholarBank@NUS Repository.
Abstract: A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions. © 2010 Elsevier B.V.
Source Title: Information Processing Letters
ISSN: 00200190
DOI: 10.1016/j.ipl.2010.07.020
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.