TIME: 1:30-2:20 pm, Nov 6, 2007 PLACE: CSE 503 SPEAKER: Robert Kleinberg Cornell University TITLE: Online learning algorithms for searching and ranking ABSTRACT: This talk discusses some algorithm design problems that stem from the challenge of using implicit feedback from users to optimize the ranking of documents in response to a query. We will first consider the problem of inserting a new document into its proper position in an already sorted list, using the feedback from users' clicks. This can be modeled as a noisy binary search problem. We present an algorithm whose query complexity is information-theoretically optimal, up to a constant factor. The second part of the talk considers the problem of learning a ranking which maximizes utility for a heterogeneous user population. We show how this can be formulated as a generalization of the multi-armed bandit problem, and we give an algorithm for one special case of the problem (corresponding to the objective of minimizing abandonment) whose worst-case performance cannot be improved without violating complexity-theoretic lower bounds. The first part of the talk is joint work with Richard Karp. The second part is joint work with Thorsten Joachims and Filip Radlinski.