# Expressivity of Polysize Decision Trees

A binary decision tree (DT) is a binary tree whose internal nodes are labelled by boolean variables (with repetitions), and whose leaves are labelled either $$0$$ or $$1$$. The size of a decision tree is the number of branches (or equivalently the number of leaves).

A DT determines a unique Boolean function of the variables labelling the internal nodes: given an assignment of these variables, start at the root of the tree and take the left branch if the label is assigned $$0$$ and the right branch otherwise, and repeat until a leaf is reached; the value of the function is the label of the leaf. Any boolean function $$f\colon \{0,1\}^n\to\{0,1\}$$ can be represented by a DT with size $$2^n$$ (a complete tree where the $$i^\text{th}$$ level of internal nodes is labelled by variable $$x_i$$).

Question: Is the class of languages recognisable by a family of polynomial-size decision trees known to be related to a ''natural'' class of single-output boolean circuits (e.g. NC$$^0$$, TC$$^0$$...)?

I am hoping for something analogous to Barrington's theorem [Bar89] for branching programs (which can be seen as an extension of DTs where ''tree'' is replaced by ''DAG'').

The class of decision problems solvable by a family of polynomial-size, constant-width ($$\geq 5$$) branching programs is exactly (non-uniform) NC$$^1$$.

However, the existence of strong learning algorithms for DTs [BLQT21] leads me to believe I'm looking for far less expressive classes.

[Bar89] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.

[BLQT21] Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan: Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021).

## 1 Answer

This is not an exact characterization, but the class of languages recognizable by poly-size DT is included in $$\mathrm{AC}^0$$, specifically within its second level: that is, any DT can be converted to a polynomially larger CNF and DNF. To see this, take $$\bigvee_i\bigwedge_jp_{i,j},$$ where $$i$$ runs over all accepting leaves of the DT, and for each $$i$$, $$p_{i,j}$$ enumerates literals corresponding to the decisions made on the path from the root to $$i$$.

• Interestingly, we can further narrow down the class: every function admitting a poly-size DT admits both a poly-size CNF and a poly-size DNF (as you wrote), but the converse is not true, as shown by [JRSW99]. [JRSW99] S. Jukna, A. Razborov, P. Savický, I. Wegener, "On P versus NP$\cap$co-NP for decision trees and read-once branching programs" (dx.doi.org/10.1007/s000370050005) Commented Jan 4, 2022 at 16:10
• Yes, that’s why I write this is not an exact characterization in the answer. Commented Jan 25, 2022 at 17:13