General Information
- Instructor: Josh Alman
- Time: Tuesdays 4:10 – 6:00 PM
- Classroom: 415 Schapiro Center for Engineering & Physical Science Research
- TA: Shunhua Jiang
- Office hours:
- Josh: Thursdays 4:00 – 6:00 PM starting Sept 23, or by email/appointment
- Shunhua: Fridays 12:30 – 2:30 PM starting Sept 17
Description
Algebraic techniques have been used in nearly every area of computer science. This course will develop some of these techniques and explore a broad range of applications. We will mostly see applications to algorithm design and complexity theory, but we will touch on applications to other areas as well. The course will focus on four main topics:
- Algebraic graph algorithms. The fastest known algorithms for several important graph problems use algebraic tools. Often, the graph problem appears (at first glance) to have nothing to do with algebra, and algorithm designers have found surprising algebraic connections.
- The polynomial method. If one can capture a computational task using a simple polynomial, then fast algorithms for manipulating polynomials can often be used to solve the problem more efficiently. In contrast, if one can show that a task cannot be captured by simple polynomials, this can often be used to prove complexity-theoretic lower bounds.
- Matrix rigidity. Some of the most important and applicable algorithms are for computing linear transforms such as Fourier transforms. Matrix rigidity is a powerful but poorly understood tool for understanding their complexity. A matrix is called rigid if it cannot be decomposed as the sum of a low-rank matrix and a sparse matrix. It remains an open problem to prove that any explicit family of matrices is rigid.
- Matrix multiplication algorithms. Matrix multiplication is prevalent in computational science and is known to be equivalent to many other computational problems in linear algebra. We will see how fast matrix multiplication algorithms are designed, including some recent developments.
Evaluation will be primarily based on a final project. I will provide a list of suggestions for the project, but students are encouraged to relate their project to their interests. There will also be occasional (at most 4) homework assignments, and students will be asked to scribe a lecture.
Prerequisites
This is an advanced topics class, but it is open to everyone. The most important prerequisite is mathematical maturity (comfort with understanding and writing mathematical proofs). Students should also be comfortable with linear algebra and the design and analysis of algorithms. Familiarity with complexity theory or more abstract algebra is helpful but not necessary; I’ll introduce the relevant notions as they arise.
Tentative Syllabus (subject to change)
September 14 |
Introduction to the course. |
September 21 |
Algebraic graph algorithms: Using matrix multiplication to compute the inverse and determinant. Maximum matching, k-path, Baur-Strassen theorem, finding a shortest cycle in a weighted graph. |
September 28 |
Intro to fine-grained complexity: fine-grained reductions and common hypotheses — (S)ETH, OV, APSP, 3SUM |
October 4 |
The polynomial method: probabilistic and approximate polynomials, applications to circuit complexity and learning theory. |
October 11 |
The polynomial method in algorithm design: orthogonal vectors problem, all-pairs shortest paths with integer weights, batch nearest neighbor search. |
October 18 |
Linear circuits and sparse matrix factorization: definitions and basics, fast Fourier transform, fast Walsh-Hadamard transform, fast polynomial evaluation |
October 25 |
Matrix Rigidity: connections to linear circuits and communication complexity, known rigidity lower bounds |
November 2 |
No meeting (Election Day) |
November 9 |
Matrix Rigidity: rigidity upper bounds for the Walsh-Hadamard transform and generalizations |
November 16 |
Matrix Multiplication: Strassen’s algorithm, tensors, tensor rank, border rank, Schönhage’s asymptotic sum inequality |
November 23 |
Matrix Multiplication: The laser method and Coppersmith-Winograd algorithm |
November 30 |
Matrix Multiplication: Rectangular matrix multiplication, barriers to improving Coppersmith-Winograd, the group-theoretic approach, Boolean matrix multiplication and other variants |
December 7 |
Epilogue |