  In this paper, the problem of estimating the level set of a black-box
function from noisy and expensive evaluation queries is considered. A new
algorithm for this problem in the Bayesian framework with a Gaussian Process
(GP) prior is proposed. The proposed algorithm employs a hierarchical sequence
of partitions to explore different regions of the search space at varying
levels of detail depending upon their proximity to the level set boundary. It
is shown that this approach results in the algorithm having a low complexity
implementation whose computational cost is significantly smaller than the
existing algorithms for higher dimensional search space $\X$. Furthermore, high
probability bounds on a measure of discrepancy between the estimated level set
and the true level set for the the proposed algorithm are obtained, which are
shown to be strictly better than the existing guarantees for a large class of
GPs. In the process, a tighter characterization of the information gain of the
proposed algorithm is obtained which takes into account the structured nature
of the evaluation points. This approach improves upon the existing technique of
bounding the information gain with maximum information gain.
