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).

  • $\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Jun 7 '11 at 1:39
  • $\begingroup$ 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? $\endgroup$ – MGwynne Jun 7 '11 at 5:30

I think the number of true points isn't a good measure to say anything about the size of the smallest decision tree.

There is a chapter in Branching programs and binary decision diagrams: theory and applications by Ingo Wegener about the size of decision trees for boolean functions.

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))}. $$

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Marc Sep 4 '15 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.