Optimal direct sum results for deterministic and randomized decision tree complexity
type: Item
instance of: scholarly article
title: Optimal direct sum results for deterministic and randomized decision tree complexity
zbMATH Open document ID: 1234.68119
author: Rahul Jain
author: Hartmut Klauck
author: Miklos Santha
published in: Information Processing Letters
publication date: 2012-03-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/1004.0105
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6018497
zbMATH Keywords: computational complexity
zbMATH Keywords: direct sum
zbMATH Keywords: decision tree complexity
MaRDI profile type: Publication
OpenAlex ID: W1523387560
arXiv ID: 1004.0105
Wikidata QID: Q58040211
cites work: Q3172424
cites work: A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
cites work: Decision trees with Boolean threshold queries
cites work: Complexity measures and decision tree complexity: a survey.
cites work: Robust polynomials and quantum algorithms
cites work: Improved direct product theorems for randomized query complexity
cites work: Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
cites work: Products and Help Bits in Decision Trees
cites work: Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
cites work: Q5365063
DBLP publication ID: journals/ipl/JainKS10
DOI: 10.1016/J.IPL.2010.07.020
description: scientific article; zbMATH DE number 6018497