Optimal direct sum results for deterministic and randomized decision tree complexity

DOI10.1016/J.IPL.2010.07.020zbMATH Open1234.68119DBLPjournals/ipl/JainKS10arXiv1004.0105OpenAlexW1523387560WikidataQ58040211 ScholiaQ58040211MaRDI QIDQ407594FDOQ407594

Authors: Rahul Jain, Hartmut Klauck, Miklos Santha 

Publication date: 27 March 2012

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

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.

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

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

zbMATH Keywords

computational complexitydirect sumdecision tree complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• On the direct sum conjecture
• Title not available (Why is that?)
• The direct sum of universal relations
• Title not available (Why is that?)
• Choosing, agreeing, and eliminating in communication complexity
• A composition theorem for decision tree complexity
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved direct product theorems for randomized query complexity
• 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)