CS 598 TMC, Fall 2022

Algorithms from the Fine-Grained Perspective

Instructor

Timothy Chan (tmc "at" illinois.edu, office hours: Wed 12:30pm-1:20pm, Siebel 3230)

Meeting Time

Wed & Fri 11:00am-12:15pm, Siebel 1302

Course Overview

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.

Prerequisites: Solid background in algorithm design and analysis, at the level of CS 374. (CS 473 is not required, though some previous exposure to randomized algorithms might be helpful. Interested undergraduate students are welcomed, and may request for an UG petition.)

Course Work

4 homeworks (problem sets), worth 45%
- HW1 (due Sep 22 Thu 5pm)
- HW2 (due Oct 13 Thu 5pm) (note (9/28): Q1 has been revised)
- HW3 (due Nov 3 Thu 5pm)
- HW4 (due Dec 1 Thu 5pm)
- submit homework on Gradescope (entry code RZ5YXE)
presentation, worth 15%
project (reading some papers and writing a report, or doing some original research), worth 40%

(Assignments, presentations, and projects may be done in groups of at most 3.)

See guidelines for presentation and project.

Outline

Basic algorithmic tools: convolution/FFT, matrix multiplication, and their applications
Conditional lower bounds via reductions (from SETH, OV, 3SUM, APSP, k-clique, ...)
Advanced algorithmic techniques: log shaving, polynomial method, additive combinatorics...

Lectures

(There is no textbook; I'll provide links to relevant papers below, and also scribbles from class. Lecture recordings may be accessed on mediaspace for registered students.)

Aug 24: Introduction.
Aug 26: Convolution/FFT. (Ref: Jeff's book)
Aug 31: Applications of FFT: 3SUM for bounded integers, string matching with "don't cares". (Ref: Clifford and Clifford'07)
Sep 2: Applications of FFT (cont'd): string matching with mismatches, subset sum.... (Ref: Abrahamson'87)
Sep 7: Subset sum (cont'd). (Ref: Bringmann'17, Jin and Wu'19)
Sep 9: Matrix multiplication. (Ref: see my notes) (breaking news (10/7): see Fawzi et al. found a way to multiply 4x4 matrices with 47 instead of 49 scalar multiplications... over Z_2)
Sep 14: Matrix multiplication cont'd (rectangular, sparse). Applications: triangle finding. (Ref: Yuster and Zwick'05, Alon, Yuster, and Zwick'97)
Sep 16: Transitive closure. APSP... (Ref: Munro'71)
Sep 21: Directed APSP with small integer weights. (Ref: Zwick'02)
Sep 23: Undirected APSP with small integer weights. Min triangle and APSP with real vertex weights... (Ref: Appendix F of C., Vassilevska W., and Xu'21, Vassilevska, Williams, and Yuster'06, Sec 3 of C.'10)
Sep 28: Conditional lower bounds. APSP (or (min,+)-matrix multiplication) → negative-weight triangle. (Ref: Vassilevska W. and Williams'10)
Sep 30: APSP → zero-weight triangle; APSP → graph radius (Ref: Thm 3.3 of Vassilevska W. and Williams'13, Abboud, Grandoni, and Vassilevska W.'15)
Oct 5: (min,+)-convolution → (min,+)-matrix multiplication; (min,+)-convolution → knapsack... (Ref: Thm 10 of BCDEHILPT'14, Cygan, Mucha, Wegrzycki, and Wlodarczyk'17 or Kunnemann, Paturi, and Schneider'17)
Oct 7: ... (min,+)-convolution → min k-enclosing rectangle. (Ref: Sec 3.5 of C. and Har-Peled'19)
Oct 12: SETH. (Ref: Impagliazzo, Paturi, and Zane'01
Oct 14. k-SAT → subset sum. (ref: Abboud, Bringmann, Hermelin, and Shabtay'19)
Oct 19: OV → (approximate) diameter in sparse unweighted graphs. (Ref: Roditty and Vassilevska W.'13, Backurs, Roditty, Segal, Vassilevska W., and Wein'18, or Sec 3 of Virginia's survey)
Oct 21: OV → LCS/edit-distance-related problems (specifically, discrete Frechet distance). (Ref: Bringmann'14 (see also Backurs and Indyk'15, Abboud, Backurs, and Vassilevska W.'15, article on Wired magazine))
Oct 26: 3SUM → geometry problems (Ref: Gajentaan and Overmars originally from the '90s)
Oct 28: 3SUM → convolution-3SUM → zero-weight triangle (Ref: Sec 2 of Patrascu'10 or Sec 6 of Kopelowitz, Pettie, Porat'16, or C. and He'20)
Nov 2: 3SUM → triangle listing (Ref: Patrascu'10)
Nov 4: triangle listing → dynamic graph data structures (e.g., graph connectivity with vertex updates); other conjectures, including the "directed unweighted APSP conjecture" (Ref: see some of the results of Abboud and Vassilevska W.'14; and C., Vassilevska W., and Xu'21)
Nov 9: Advanced algorithmic techniques. Shaving logs: Boolean matrix multiplication, LCS/edit distance, integer 3SUM. (Ref: the 4 Russians, Masek and Paterson'80, Baran, Demaine, and Patrascu'08)
Nov 11: More log shavings, via decision trees: real APSP, real 3SUM. (Ref: Fredman'76, Gronlund and Pettie'14)
Nov 16: Real APSP further improved, via geometric techniques. (Ref: C.'05)
Nov 18: OV via the polynomial method... (Ref: Abboud, Williams, and Yu'15)
Nov 30: APSP via the polynomial method. (Ref: Williams'14, C. and Williams'16)
Dec 2, 7: student presentations in room Siebel 1103