text: abstract
  in sequential hypothesis testing, generalized
  binary search (gbs) greedily chooses the
  test with the highest information gain at each
  step. it is known that gbs obtains the gold
  standard query cost of o(log n) for problems
  satisfying the k-neighborly condition, which
  requires any two tests to be connected by a
  sequence of tests where neighboring tests disagree on at most k hypotheses. in this paper, we introduce a weaker condition, splitneighborly, which requires that for the set of
  hypotheses two neighbors disagree on, any
  subset is splittable by some test. for four
  problems that are not k-neighborly for any
  constant k, we prove that they are splitneighborly, which allows us to obtain the optimal o(log n) worst-case query cost.