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
|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. 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||URI:||http://scholarbank.nus.edu.sg/handle/10635/43106||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.
checked on Dec 11, 2019
WEB OF SCIENCETM
checked on Dec 3, 2019
checked on Dec 2, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.