Complexity measures and decision tree complexity: a survey

By Harry Buhrman, Ronald de Wolf. Theoretical Computer Science, 2002

684 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Algorithmics of Matching Under Preferences (2013, background): “This question was answered in the negative by Dougherty and Selkow [170], who proved that the certificate complexity [114] of determining whether a given matching is stable in an sm instance of size n is Ω(n(2)).”
Quantum walk algorithm for element distinctness (2003, methodology): “Our model is the quantum query model (for surveys on query mod el, see [7, 18]).”
Sharp phase transition for the random-cluster and Potts models via decision trees (2017, background): “The theory of (random) decision trees played a key role in computer science (we refer the reader to the survey [BDW02]), but also found many applications in other fields of mathematics.”
New degree bounds for polynomial threshold functions (2003, background): “degree for an approximating polynomial (see Theorem 18 of [ 8 ]), their results imply an O(s1/2 logd−1(s)) upper bound on the degree of the formulas that they consider.”