Concepedia

Decision Tree Complexity

Decision Tree Complexity is a computational complexity measure that quantifies the minimum number of queries or node evaluations required in the worst case by a decision tree to compute a Boolean function, distinguishing it from other complexity measures by its focus on the depth or structure of adaptive query strategies for function evaluation.

221

Publications

15.8K

Citations

406

Authors

209

Institutions

Publications per year

2017–2026

33

Parents

Publications

221

Constructing optimal binary decision trees is NP-complete

Laurent Hyafil, Ronald L. Rivest · Information Processing Letters · 1976 · 956 citations

, , +10

Complexity measures and decision tree complexity: a survey

Harry Buhrman, Ronald de Wolf · Theoretical Computer Science · 2002 · 692 citations

, , +13

Inferring decision trees using the minimum description lenght principle

J. R. Quinlan, Ronald L. Rivest · Information and Computation · 1989 · 665 citations

, , +9

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve et al. · Journal of the ACM · 2001 · 659 citations

, , +17

An Empirical Comparison of Pruning Methods for Decision Tree Induction

John Mingers · Machine Learning · 1989 · 638 citations · Full text

, , +14

1–5 of 221

Authors

406

  1. MM
    Mikhail Moshkov

    King Abdullah University of Science and Technology, Saudi Arabia

    8 publications · 178 citations

    8

    h-index

  2. AC
    Andrew Chi-Chih Yao

    Princeton University, United States

    7 publications · 382 citations

    7

    h-index

  3. RC
    Richard Cleve

    University of Calgary, Canada

    5 publications · 1.1K citations

    5

    h-index

  4. YM
    Yishay Mansour

    Tel Aviv University, Israel

    5 publications · 573 citations

    5

    h-index

  5. IC
    Igor Chikalov

    King Abdullah University of Science and Technology, Saudi Arabia

    5 publications · 114 citations

    5

    h-index

1–5 of 406

Institutions

209

  1. Princeton University

    Princeton, United States

    12 h-index

    22 publications

    1.1K citations

  2. University of Calgary

    Calgary, Canada

    8 h-index

    10 publications

    1.2K citations

  3. University of California San Diego

    San Diego, United States

    6 h-index

    12 publications

    333 citations

  4. Yaroslav-the-Wise Novgorod State University

    Veliky Novgorod, Russia

    6 h-index

    7 publications

    129 citations

  5. Hebrew University of Jerusalem

    Jerusalem, Israel

    6 h-index

    7 publications

    228 citations

  6. Centre National de la Recherche Scientifique

    Paris, France

    6 h-index

    13 publications

    406 citations

  7. Nizhny Novgorod State Pedagogical University

    Nizhny Novgorod, Russia

    5 h-index

    7 publications

    151 citations

  8. Microsoft (United States)

    Redmond, United States

    5 h-index

    7 publications

    367 citations

1–8 of 209

Venues

  1. SIAM Journal on Computing

    14 publications · 1.2K citations

    13

    h-index

  2. Machine Learning

    8 publications · 1.5K citations

    10

    h-index

  3. Journal of the ACM

    JACM · 8 publications · 1.2K citations

    8

    h-index

  4. arXiv (Cornell University)

    Repository · 7 publications · 140 citations

    7

    h-index

  5. Fundamenta Informaticae

    6 publications · 146 citations

    6

    h-index

1–5