Research map / Learning theory and algorithms / Prediction and decision losses
The Influence of Dimensions on the Complexity of Computing Decision Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dimension-indexed hyperrectangle dynamic programming | DTS · Minimum Decision Tree Size | running time: O(n^{2d + 1}d) | Helped |
| Increase the number d of dimensions | DTS algorithms · Minimum Decision Tree Size | running-time dependence on d: f(d)n^{o(d/\log d)} | Hurt |
| Parameterize tree search by both size s and dimension count d | DTS · k-DTS | running time: O((s^3d)^{s}|E|^{1+o(1)}) | Helped |
| Restrict cuts to a given subset of at most s dimensions | DTS · DTS with specified cut dimensions | running time: 2^{O(s(\log{s}))} |E|^{1+o(1)} | Helped |
| Bound the number of leaves labeled with the less-frequent class by R | DTS · DTS parameterized by d+R | running time: (dR)^{O(dR)} \cdot n^{1+o(1)} | Helped |
Closest papers by meaning
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.92)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.91)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.91)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.89)
- Learning Small Decision Trees for Data of Low Rank-Width (AAAI 2024 · similarity 0.89)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.