Optimal direct sum results for deterministic and randomized decision tree complexity
From MaRDI portal
Publication:407594
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
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
