Optimal direct sum results for deterministic and randomized decision tree complexity

DOI10.1016/J.IPL.2010.07.020MaRDI QIDQ407594zbMATHOpenAlexDBLPWikidataFDO

Authors Rahul Jain, Hartmut Klauck, Miklos Santha

Publication date 27 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.0105

zbMATH Keywords

computational complexitydirect sumdecision tree complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Recommendations

• A composition theorem for decision tree complexity
• Improved direct product theorems for randomized query complexity
• Decision trees with Boolean threshold queries
• Towards proving strong direct product theorems
• scientific article; zbMATH DE number 426344

Cites work

• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Complexity measures and decision tree complexity: a survey.
• Decision trees with Boolean threshold queries
• Improved direct product theorems for randomized query complexity
• Products and Help Bits in Decision Trees
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Reflections for quantum query algorithms
• Robust polynomials and quantum algorithms
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• The quantum query complexity of certification

Cited in

(11)

• scientific article; zbMATH DE number 1256781 (Why is no real title available?)
• A composition theorem for decision tree complexity
• On the direct sum conjecture
• Choosing, agreeing, and eliminating in communication complexity
• Improved direct product theorems for randomized query complexity
• Optimal separation and strong direct sum for randomized query complexity
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• The direct sum of universal relations
• The choice and agreement problems of a random function

This page was built for publication: Optimal direct sum results for deterministic and randomized decision tree complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407594)