Dynamic Algebraic Algorithms
CS 8803 - DAA, Fall 2022
Time: Mon/Wed 3:30-4:45pm.
Location: Engineering Sci and Mechanics 202
Office hours: Tue 4-5pm in KACB 2116
TA: Mehrdad Ghadiri
Instructor: Jan van den Brand
Access course on canvas.
Lecture notes are available here.
They will be regularly updated. Feel free to send feedback, issues, etc. via email.
Description
Dynamic algebraic algorithms allow to efficiently maintain properties of matrices and vector spaces that change over time. These techniques can also be used to maintain properties of a graph while the graph changes (e.g. the shortest path in a road network under changing traffic conditions). When used as a subroutine, dynamic algebraic techniques can accelerate many iterative algorithms.
This course will explore different algorithmic techniques, connections and applications related to dynamic algebraic algorithms, including:
- randomized linear algebra and sketching: algorithms for large matrices and compressing data
- interior point methods: solving convex optimization problems such as linear programs
- algebraic graph algorithms: using algebraic techniques to solve graph problems efficiently
- dynamic algorithms: data structures that maintain properties of some input while the input changes over time
- fine grained complexity theory: proving complexity lower bounds via reductions
Prerequisites are basic knowledge of linear algebra (matrices, determinant, inverse etc), probability theory and theoretical analysis of algorithms.
This is a theory course, both the lecture and the problem sets are proof-oriented.
Grading
Problemsets: You are encouraged to collaborate, but you must write your own solutions.
Final project: The project should demonstrate understanding of tools and techniques covered in this course. A possible project could be one of the following:
- A report (3-5 pages) on a paper related to this course. This can be an overview or presenting some key proofs and their context. I will provide a list of papers as suggestion, but you can also propose others.
- A survey on a topic/problem related to this course.
- Implementation: Experimental evaluation and comparison of some algorithms discussed in the course.
The list above is a suggestion and you can propose another project. You are encouraged to relate the project to your research interests, but it must involve techniques covered in this course.
Projects must be proposed in advance (some time in October) so I can confirm scope and topic fit.
You can work in groups but the scope of the project should match the group size.
Optional: Depending on demand, there will be an option to present your project.