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. |
Decision tree complexity
|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. https://doi.org/10.1016/j.ipl.2010.07.020|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 17, 2018
WEB OF SCIENCETM
checked on Sep 5, 2018
checked on Aug 3, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.