Can I read Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity on EtoBox?

Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity by Jain, Rahul; Klauck, Hartmut; Santha, Miklos is a scholarly article available to read on EtoBox.

What is Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity about?

A Direct Sum Theorem holds in a model of computation, when 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.

Author

Jain, Rahul; Klauck, Hartmut; Santha, Miklos

Published

2010

Language

EN