On Exact Learning Monotone DNF from Membership Queries
  In this paper, we study the problem of learning a monotone DNF with at most
$s$ terms of size (number of variables in each term) at most $r$ ($s$ term
$r$-MDNF) from membership queries. This problem is equivalent to the problem of
learning a general hypergraph using hyperedge-detecting queries, a problem
motivated by applications arising in chemical reactions and genome sequencing.
  We first present new lower bounds for this problem and then present
deterministic and randomized adaptive algorithms with query complexities that
are almost optimal. All the algorithms we present in this paper run in time
linear in the query complexity and the number of variables $n$. In addition,
all of the algorithms we present in this paper are asymptotically tight for
fixed $r$ and/or $s$.
