Algebraic Techniques in TCS, COMS 6998, FALL 2021, Josh Alman

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 – 6 PM in CSB 504 or by email/appointment
- Shunhua: Fridays 2 – 4 PM in CSB 487
Scribe notes are posted below.

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.

Syllabus and Scribe Note Drafts

Disclaimer: the provided notes are drafts and may be incomplete or need editing. Consult this page for the most up-to-date versions.

September 14	Introduction to the course. Algebraic graph algorithms: Finding triangles and 4-node subgraphs.	[scribe notes]
September 21	Algebraic graph algorithms: Finding 4-node subgraphs. Schwartz-Zippel lemma. Detecting a perfect matching.	[scribe notes]
September 28	Algebraic graph algorithms: Detecting a k-path. Quickly computing the inverse and determinant of a matrix. Intro to the Orthogonal Vectors problem and Strong Exponential Time Hypothesis.	[scribe notes]
October 4	The polynomial method: Constant-depth circuit models, probabilistic polynomials, and the Razborov-Smolensky proof that MAJORITY is not in AC0[2].	[scribe notes]
October 11	The polynomial method in algorithm design: probabilistic polynomial construction for MAJORITY, and applications to the orthogonal vectors problem and batch nearest neighbor search.	[scribe notes]
October 18	Brief intro to fine-grained complexity	[scribe notes]
October 25	Linear circuits and sparse matrix factorization: definitions and basics, fast Fourier transform, fast Walsh-Hadamard transform, fast polynomial evaluation	[scribe notes]
November 2	No meeting (Election Day)
November 9	Matrix Rigidity: known rigidity lower bounds, rigidity upper bounds for the Walsh-Hadamard transform and generalizations	[scribe notes]
November 16	Matrix Multiplication: Strassen’s algorithm, tensors, tensor rank, border rank	[scribe notes]
November 23	Matrix Multiplication: Reductions between tensors, Schönhage’s asymptotic sum inequality	[scribe notes]
November 30	Matrix Multiplication: The laser method and Coppersmith-Winograd algorithm	[scribe notes]
December 7	Epilogue