About
A lot of the world's computation is spent on linear algebra problems such as matrix multiplication, Ax = b, and Ax = λx, yet our theoretical understanding of these problems is far from sharp. What is the exponent of matrix multiplication? Which linear systems, other than Laplacians, can we solve in nearly linear time? Is Gaussian elimination numerically stable? Can efficient algorithms for linear algebra be derandomized? We don’t have satisfying answers to these questions. Moreover, there is a large disconnect between theory and practice, exemplified by the fact that all high-performance implementations of matrix multiplication currently in use are variations of the cubic-time algorithm.
Such questions have been intensively studied in several distinct research communities, including theoretical computer science, numerical linear algebra, high-performance computing, symbolic computation, and various branches of mathematics. These fields have had limited interaction and have developed essentially parallel research traditions around the same core problems, with their own models of computation (e.g., exact vs. floating point vs. rational vs. finite field arithmetic), solution concepts (backward vs. forward error), and techniques. This divergence of perspectives has been amplified by researchers from these fields generally publishing in disjoint venues and being housed in different departments.
On the other hand, some interactions that have taken place have been highly productive and paradigm-changing. For instance, combinatorial preconditioning, randomized numerical linear algebra, and smoothed analysis all arose from such interactions. On the more mathematical side, the complexity of matrix multiplication can itself be phrased as a linear algebraic problem, that of tensor rank. Exciting developments over the last decade have shown this problem to be related to algebraic geometry, geometric invariant theory, quantum information, and algebraic complexity, enabling new tools for proving upper and lower bounds. On the more computational side, there have been advances in minimizing communication costs and leading constants in linear algebra algorithms, with the aim of bringing theory closer to practice.
This program will bring together researchers from the research communities mentioned above for a whole semester, for the first time, around the following three themes.
- Complexity of linear algebra
- Theory toward practical linear algebra
- Randomness, invariants, and tensors
This program will feature a boot camp, a workshop on linear equations and eigenvalue problems, a workshop on matrix multiplication, and a workshop on randomness, invariants, and complexity theory.
Long-Term Participants (tentative):
Josh Alman (Columbia University ), Grey Ballard (Wake Forest University), Erin Carson (Charles University), Matthias Christandl (University of Copenhagen), Matthew Colbrook (University of Cambridge), Austin Conner (Harvard University), James Demmel (UC Berkeley), Harm Derksen (University of Michigan), Ioana Dumitriu (UCSD), Yuval Filmus (Technion), Michael Forbes (UIUC), Anne Greenbaum (University of Washington), Chen Greif (University of British Columbia), Laura Grigori (EPFL), Joshua Grochow (University of Colorado ), Leonid Gurvits (City University of New York), Erich Kaltofen (North Carolina State University), Petteri Kaski (Aalto University), Manuel Kauers (Johannes Kepler University), Rasmus Kyng (ETH Zurich), Joerg Liesen (TU Berlin), Gary Miller (CMU), Cameron Musco (UMass), Christopher Musco (NYU), Rafael Oliveira (University of Waterloo), Richard Peng (University of Waterloo), Youming Qiao (University of Technology, Sydney), Anna Seigal (Harvard University), Edgar Solomonik (UIUC), Arne Storjohann (University of Waterloo), Konstantin Tikhomirov (Georgia Tech), Tom Trogdon (University of Washington), Santosh Vempala (Georgia Tech), Michael Walter (Ruhr University Bochum), Omri Weinstein (Columbia University), Avi Wigderson (Institute for Advanced Study), Heather Wilbur (University of Washington), Virginia Williams (MIT), David Woodruff (CMU), Jeroen Zuiddam (University of Amsterdam)
