Monday, September 10, 2007
4:00 PM
5130 Upson Hall
  Theory Seminar
Fall 2007
CS 789

Bobby Kleinberg
Cornell University


Noisy Binary Search


We consider a noisy version of the classic binary search problem of inserting an element into its proper place within an ordered sequence by comparing it with elements of the sequence.  In the noisy version we can not compare elements directly.  Instead we are given a coin corresponding to each element, such that as one goes through the ordered sequence the probability of observing heads when tossing the corresponding coin increases.  

We design algorithms which adaptively choose a sequence of experiments, each consisting of tossing a single coin, with the goal of identifying the set of coins whose heads probability is less than some specified target value.  Matching lower bounds will be given as well.  Possible applications of such algorithms include sponsored search advertising, admission control in queueing networks, college admissions, and admitting new members into an organization ranked by ability, such as a tennis ladder.

This is joint work with Richard Karp.