Decision tree complexity versus block sensitivity and degree

Cites work

Alternation, sparsity and sensitivity: bounds and exponential gaps
An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
Communication Complexity
Communication Complexity
Complexity measures and decision tree complexity: a survey.
Composition limits and separating examples for some Boolean function complexity measures
CREW PRAM<scp>s</scp> and Decision Trees
Decision trees with Boolean threshold queries
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
Deterministic communication vs. partition number
Fourier sparsity, spectral norm, and the log-rank conjecture
scientific article; zbMATH DE number 3460321 (Why is no real title available?)
scientific article; zbMATH DE number 3558963 (Why is no real title available?)
Improved lower bounds on the randomized complexity of graph properties
Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
Learning circuits with few negations
Learning decision trees from random examples
Limiting negations in bounded-depth circuits: an extension of Markov's theorem
Limiting Negations in Constant Depth Circuits
Limiting Negations in Formulas
Limiting negations in non-deterministic circuits
On fractional block sensitivity
On rank vs. communication complexity
On recognizing graph properties from adjacency matrices
On the degree of Boolean functions as real polynomials
On the Inversion Complexity of a System of Functions
On the structure of Boolean functions with small spectral norm
Polynomials with two values
Properties and applications of Boolean function composition
Quantum certificate complexity
Quantum lower bounds by polynomials
Quantum query complexity of minor-closed graph properties
Query-to-communication lifting for BPP
Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
Symmetries, graph properties, and quantum speedups
The critical complexity of graph properties
The power of negations in cryptography

This page was built for publication: Decision tree complexity versus block sensitivity and degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6951707)