Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ipl.2010.07.020
DC FieldValue
dc.titleOptimal direct sum results for deterministic and randomized decision tree complexity
dc.contributor.authorJain, R.
dc.contributor.authorKlauck, H.
dc.contributor.authorSantha, M.
dc.date.accessioned2013-07-23T09:25:07Z
dc.date.available2013-07-23T09:25:07Z
dc.date.issued2010
dc.identifier.citationJain, 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
dc.identifier.issn00200190
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/43106
dc.description.abstractA 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.ipl.2010.07.020
dc.sourceScopus
dc.subjectComputational complexity
dc.subjectDecision tree complexity
dc.subjectDirect sum
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.departmentCENTRE FOR QUANTUM TECHNOLOGIES
dc.description.doi10.1016/j.ipl.2010.07.020
dc.description.sourcetitleInformation Processing Letters
dc.description.volume110
dc.description.issue20
dc.description.page893-897
dc.description.codenIFPLA
dc.identifier.isiut000281457000010
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

9
checked on Jan 17, 2020

WEB OF SCIENCETM
Citations

6
checked on Jan 10, 2020

Page view(s)

83
checked on Dec 30, 2019

Google ScholarTM

Check

Altmetric


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