| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427961 | Information Processing Letters | 2010 | 5 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
