Complexity measures and decision tree complexity: a survey.
type: Item
instance of: scholarly article
title: Complexity measures and decision tree complexity: a survey.
zbMATH Open document ID: 1061.68058
DOI: 10.1016/S0304-3975(01)00144-X
author: Harry Buhrman
author: Ronald de Wolf
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 81P68
zbMATH DE Number: 1857046
zbMATH Keywords: Decision tree complexity
zbMATH Keywords: Complexity measures for Boolean functions
zbMATH Keywords: Randomized computing
zbMATH Keywords: Quantum computing
MaRDI profile type: Publication
cites work: A note on quantum black-box complexity of almost all Boolean functions
cites work: Q4501528
cites work: Quantum lower bounds by polynomials
cites work: Sensitivity vs. block sensitivity (an average-case study)
cites work: The average sensitivity of bounded-depth circuits
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
cites work: An oracle builder's toolkit
cites work: Complexity limitations on quantum computation
cites work: Polynomials with two values
cites work: Q4040797
cites work: Q4228473
cites work: An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
cites work: On read-once threshold formulae and their randomized decision tree complexity
cites work: Randomized vs. deterministic decision tree complexity for read-once Boolean functions
cites work: A topological approach to evasiveness
cites work: The quantum query complexity of approximating the median and related statistics
cites work: Q2706552
cites work: CREW PRAM<scp>s</scp> and Decision Trees
cites work: On the degree of Boolean functions as real polynomials
cites work: On rank vs. communication complexity
cites work: On recognizing graph properties from adjacency matrices
cites work: A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
cites work: Sensitivity vs. block sensitivity of Boolean functions
cites work: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
cites work: Lower bounds on probabilistic linear decision trees
cites work: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
cites work: The critical complexity of graph properties
cites work: The critical complexity of all (monotone) boolean functions and monotone graph properties
cites work: Q3762226
cites work: Q3031933
full work available at URL: s0304-3975(01)00144-x
OpenAlex ID: W2012496360
description: scientific article; zbMATH DE number 1857046