M.Sc Student | Makhoul Waseem |
---|---|

Subject | On Polynomial Time Constructions of Minimum Height Decision Tree |

Department | Department of Computer Science |

Supervisor | Professor Nader Bshouty |

Full Thesis text |

We
address the problem of constructing a minimum height decision tree of a class *C*
in polynomial time. This problem has many interesting applications that
include, to name a few, computer vision, group testing, exact learning from
membership queries, and game theory.

In
this work, we further study the combinatorial measure, *ETD(C)*, which is the
extended teaching dimension of a class *C*. We show an algorithm that
achieves an *ETD(C)*-approximation of the optimal height. When the
extended dimension is small, this approximation is better than the *log(|C|)-*approximation
already known from the literature. We also show that no better approximation
ratio can be achieved unless *P=NP*.

We
then apply our results to learning the class of disjunctions of predicates from
membership queries, Bshouty *et al.* *(2017)*. We show that the
extended teaching dimension of this class is bounded from above by the degree *d*
of its *Hasse* diagram. This gives optimal algorithms when the degree is
constant.