CS 598 TMC, Fall 2020
Algorithms from the Fine-Grained Perspective
(tmc "at" illinois.edu, office hours: Thu 3:00pm-4:00pm on
or email me to meet at a different time)
Wed & Fri 11:00am-12:15pm on zoom
(email me if you are not officially registered but wants to attend)
In undergraduate algorithms classes, you have studied classical problems such as all-pairs shortest paths (APSP), longest common subsequence (LCS), edit distance, 3SUM, subset sum, triangles in graphs, etc. Have you ever wondered whether the textbook algorithms you learned could be improved, or whether they are in fact the best possible? Here, we are interested not just in determining whether the problems are polynomial-time solvable vs. NP-hard, but in their "fine-grained" complexity (quadratic time? cubic time? etc.). We will describe the recent theoretical techniques for obtaining (slightly) improved algorithms for these classical problems and their variants (in general as well as in important special cases). We will also prove conditional lower bounds via reductions that relate the fine-grained complexity of one problem to another.
Prerequisite: Solid background in algorithm
design and analysis, e.g., at the level of CS 374. (Although
CS473 is not required, some previous exposure to randomized algorithms will be helpful.)
(Assignments, presentations, and
projects may be done in groups of at most 3.)
- 4 homeworks (problem sets), worth 40%
- HW1 (due Sep 30 Wed 10am)
- submit homework on Gradescope
(entry code 9JREZ8)
(note: if you use a different alias or email address on gradescope, just let me know by email...)
- presentation, worth 20%
- a project (reading some papers and writing a report,
or doing some original research), worth 40%
- Basic algorithmic tools: convolution (FFT) and matrix multiplication, and their
applications (string matching, subset sum, triangles in graphs,
APSP for small integer weights, ...)
- Conditional lower bounds via reductions (from SETH/OV/3SUM/APSP/...)
- Advanced algorithmic techniques: log shaving (via bit tricks, or geometry in log dimensions), the polynomial method, additive combinatorics...
(There is no textbook; I'll provide links to relevant papers, and to scribbles from class.
Lectures will be also recorded, and for registered students, recordings may be accessed at mediaspace on the "CS598TMC Fall 2020" channel.)
- Aug 26: Introduction.
- Aug 28: Convolution/FFT.
(Ref: Jeff's book)
- Sep 2: Applications of FFT: 3SUM, string matching with "don't cares".
(Ref: Clifford and Clifford's paper ('07))
- Sep 4: Applications of FFT (cont'd): string matching with mismatches, subset sum. (Ref: Abrahamson'87, Chao and Xu (SODA'17))
- Sep 9: Subset sum (cont'd). (Ref: Bringmann (SODA'17),
Jin and Wu (SOSA'19))
- Sep 11: Matrix multiplication.
(Ref: see my notes)
- Sep 16: Matrix multiplication cont'd (rectangular, sparse). Applications: triangle finding.
(Ref: Yuster and Zwick'05 on sparse, Alon, Yuster, and Zwick on triangles)
- Sep 18: Transitive closure. APSP...
- Sep 23: Directed APSP with small integer weights.
- Sep 25: Undirected APSP with small integer weights.
Shoshan and Zwick'99)
- Next: vertex real weights (Vassilevska, Williams, and Yuster'06, Czumaj and Lingas'09, C.'10)...