Bobby Kleinberg

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.

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.