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
Source: 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.

SCOPUSTM   
Citations

5
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

2
checked on Dec 11, 2017

Page view(s)

59
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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