Optimal direct sum results for deterministic and randomized decision tree complexity

DOI10.1016/j.ipl.2010.07.020zbMath1234.68119arXiv1004.0105OpenAlexW1523387560WikidataQ58040211 ScholiaQ58040211MaRDI QIDQ407594

Hartmut Klauck, Rahul Jain, 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)

Related Items (7)

The choice and agreement problems of a random function ⋮ Unnamed Item ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Unnamed Item

Cites Work

• Improved direct product theorems for randomized query complexity
• 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
• Robust polynomials and quantum algorithms
• Products and Help Bits in Decision Trees
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Unnamed Item
• Unnamed Item

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