  We consider an active learning setting where a learner is presented with a
pool S of n unlabeled examples belonging to a domain X and asks queries to find
the underlying labeling that agrees with a target concept h^* \in H.
  In contrast to traditional active learning that queries a single example for
its label, we study more general region queries that allow the learner to pick
a subset of the domain T \subset X and a target label y and ask a labeler
whether h^*(x) = y for every example in the set T \cap S.
  Such more powerful queries allow us to bypass the limitations of traditional
active learning and use significantly fewer rounds of interactions to learn but
can potentially lead to a significantly more complex query language. Our main
contribution is quantifying the trade-off between the number of queries and the
complexity of the query language used by the learner.
  We measure the complexity of the region queries via the VC dimension of the
family of regions. We show that given any hypothesis class H with VC dimension
d, one can design a region query family Q with VC dimension O(d) such that for
every set of n examples S \subset X and every h^* \in H, a learner can submit
O(d log n) queries from Q to a labeler and perfectly label S. We show a
matching lower bound by designing a hypothesis class H with VC dimension d and
a dataset S \subset X of size n such that any learning algorithm using any
query class with VC dimension less than O(d) must make poly(n) queries to label
S perfectly.
  Finally, we focus on well-studied hypothesis classes including unions of
intervals, high-dimensional boxes, and d-dimensional halfspaces, and obtain
stronger results. In particular, we design learning algorithms that (i) are
computationally efficient and (ii) work even when the queries are not answered
based on the learner's pool of examples S but on some unknown superset L of S
