Tuesday, 30.12.2008, 14:30
New Algorithms for Ranking and Dimension Reduction
The study of ranking crosses many disciplines.
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. I will present
my contribution on both fronts, and show a connection to classic theories
of social choice and econometrics.
Randomized algorithms have been using measure concentration phenomena in
countless cases, and in particular in dimension reduction and streaming.
These tools have become a standard black box, and their computational
aspects have been almost taken for granted. In recent work I have
discovered an exciting and surprising new method for computing a standard
dimension reduction algorithm (Johnson-Lindenstrauss) more efficiently
than previously assumed. This method has been later used to speed up
various standard high dimensional linear algebraic computations
(such as SVD) and fueled increased collaboration between computer science
and analysis. The main ingredient is the use of a Fast Fourier Transform
and a type of uncertainty principle.