# Bounds on the size of smallest decision tree for a boolean function?

Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?

It seems to me that assuming $f$ has $n$ variables and $m$ true points then any minimal decision tree has at most $$2^{\lceil{\log_2 m}\rceil}−m+m⋅(n−\lceil{\log_2 m}\rceil)$$ 0-leaves (obviously, one can take the dual as well). I am wondering if whether this sort of thing has been covered before (I presume it has somewhere).

• A related concept will be the decision tree complexity. But instead of using size as a measure, it uses the depth of the decision tree. Jun 7, 2011 at 1:39
• I'm more interested in the size though. Another way of stating my questions would be to ask if you consider $f$ and $m$, are there bounds in $m$ on the smallest DT-DNF (or DT-CNF), that is, Decision Tree DNF? Jun 7, 2011 at 5:30

The size of the smallest DT is determined up to constant factors by the number of leaves of the tree. There is a lemma in the book that says: If you have a DT for a function $f$ with $s_0$ 0-leaves and $s_1$ 1-leaves then $f$ can be represented by a DNF with $s_1$ monomials and a CNF with $s_0$ clauses. So even if you have a function with only a small number of true points, the size of the smallest DT could be very large. So you need small size of CNF and DNF to have a small DT size.
There is a upper bound of the DT size with respect to the sum of the minimal number of monomials of $f$ and the minimal number of monomials of $\overline{f}$. Lets call this sum $DCNF(f)$. Then you have the following upper bound for the number of leaves $DT(f)$ of the smallest DT for the function $f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$ $$DT(f) \leq n^{O(log^2 DCNF(f))}.$$
• If you are interested in lower bounds: later on in the same chapter of the same book, lower bounds on $DT(f)$ are obtained via Fourrier coefficients.
• Sorry, quick question: what is a "monomial" in this context? Is it a clause of a DNF (i.e. we treat + as OR and we treat * as AND)? And thus, is $DCNF(f)$ exactly the sum lower bounding the decision tree size (as in the prior paragraph)? Sep 17, 2021 at 4:39