The Taub Faculty of Computer Science Events and Talks

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.