General Information

• Instructor: Josh Alman
• Time: Tuesdays 4:10 – 6:00 PM
• Classroom: Mudd room 825
• TA: Yunfeng Guan
• Office hours:
  • Josh: Thursdays 4-6pm in CSB 504 or by email/appointment
  • Yunfeng: Mondays 4-6pm in CSB 488
• Link to previous offering: 2021

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 at most 4 homework assignments.

 

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.