On Polynomial time Constructions of Minimum Height Decision Tree
  In this paper we study a polynomial time algorithms that for an input
$A\subseteq {B_m}$ outputs a decision tree for $A$ of minimum depth. This
problem has many applications that include, to name a few, computer vision,
group testing, exact learning from membership queries and game theory.
  Arkin et al. and Moshkov gave a polynomial time $(\ln |A|)$- approximation
algorithm (for the depth). The result of Dinur and Steurer for set cover
implies that this problem cannot be approximated with ratio $(1-o(1))\cdot \ln
|A|$, unless P=NP. Moskov the combinatorial measure of extended teaching
dimension of $A$, $ETD(A)$. He showed that $ETD(A)$ is a lower bound for the
depth of the decision tree for $A$ and then gave an {\it exponential time}
$ETD(A)/\log(ETD(A))$-approximation algorithm.
  In this paper we further study the $ETD(A)$ measure and a new combinatorial
measure, $DEN(A)$, that we call the density of the set $A$. We show that
$DEN(A)\le ETD(A)+1$. We then give two results. The first result is that the
lower bound $ETD(A)$ of Moshkov for the depth of the decision tree for $A$ is
greater than the bounds that are obtained by the classical technique used in
the literature. The second result is a polynomial time $(\ln 2)
DEN(A)$-approximation (and therefore $(\ln 2) ETD(A)$-approximation) algorithm
for the depth of the decision tree of $A$. We also show that a better
approximation ratio implies P=NP.
  We then apply the above results to learning the class of disjunctions of
predicates from membership queries. We show that the $ETD$ of this class is
bounded from above by the degree $d$ of its Hasse diagram. We then show that
Moshkov algorithm can be run in polynomial time and is $(d/\log
d)$-approximation algorithm. This gives optimal algorithms when the degree is
constant. For example, learning axis parallel rays over constant dimension
space.
