Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.ipl.2010.07.020
| 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. 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.