Computer Science Colloquium, 2008-2009

Abstract:

In modern algorithm design and analysis, much has been drawn from classic disciplines such as combinatorics, analysis, economics and social choice. The use of classic theory has served in both change of perspective and in offering useful techniques and ideas. Often the exchange of ideas worked both ways, and the computer scientific perspective has given a fresh new look at classic results. This exchange is helping to shape and position the field of Computer Science within other more established disciplines.

An excellent example for this is the study of rankings. Social choice theoreticians have been interested for centuries in finding a good way to rank a set of candidates. Econometricians have been asking for decades how people choose from (and more generally rank) alternative sets. More recently, information retrieval theoreticians and practitioners have been interested in ranking search query results. In verification, practitioners have been interested in ordering variable sets so as to reduce the time to detect software errors. These recent problems have been identified in both machine learning and combinatorial optimization communities.

Another example is algorithms on high dimensional data: Randomized algorithms have been using classic measure concentration phenomena for dimension reduction and streaming purposes in countless examples. Recently there have been exciting developments on the computer scientific side, fueling evermore collaboration between computer science and analysis.

I will present my contribution to both examples and others.

Based on joint papers with Moses Charikar, Bernard Chazelle, Edo Liberty, Mehryar Mohri and Alantha Newman.