We work on improving the algorithms for algebraic problems like matrix multiplication, and using these to design algorithms for fundamental non-algebraic problems.
In this project, we study the powers and limitations of using algebraic techniques like matrix multiplication and polynomial evaluation to design new and faster algorithms. First, we investigate how quickly these algebraic primitives can be computed: Can we multiply matrices or polynomials faster than is currently known? Can we prove lower bounds showing that such improvements are impossible? Second, we study how for many fundamental algorithmic problems, we can use these highly-optimized algebraic techniques to design faster algorithms than were previously known. For example, by combining fast matrix multiplication and polynomial approximation, we design a faster algorithm for nearest neighbor search. Finding nearest neighbors has applications to many problems in computer science like search and error correction, and also to problems outside of computer science in domains like biology and data analysis. It is surprising that algebraic techniques can be used to help with this problem, which a priori has nothing to do with algebra.
