ABSTRACT:

In this talk, I will speak about how algebraic tools can be used to solve problems throughout computer science. I will focus on two such tools: algorithms for quickly multiplying matrices and mathematical techniques for approximating functions by low-degree polynomials. I will survey how these two tools, when combined, yield a wide variety of new results, including:

- the fastest known algorithm for batch nearest neighbor search, where one is given many data points and wants to find the “most similar” pairs of points according to various metrics,
- state-of-the-art limitation results for threshold circuits, a loose model of neural networks,
- a new, efficient representation of the Walsh-Hadamard transform from signal processing, and
- limitations on all known approaches to designing fast matrix multiplication algorithms.

BIO:

Josh Alman is a Ph.D. candidate in computer science at MIT, where he is advised by Ryan Williams and Virginia Vassilevska Williams. He received his master’s in computer science from Stanford in 2016 and his bachelor’s in mathematics from MIT in 2014.