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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.