CS 598 TMC, Fall 2020

Algorithms from the Fine-Grained Perspective

Instructor

Timothy Chan (tmc "at" illinois.edu, office hours: Thu 3:00pm-4:00pm on zoom, or email me to meet at a different time)

Meeting Time

Wed & Fri 11:00am-12:15pm on zoom (email me if you are not officially registered but wants to attend)

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.

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.)

Course Work

4 homeworks (problem sets), worth 40%
- HW1 (due Sep 30 Wed 10am)
- HW2 (due Oct 14 Wed 10am)
- HW3 (due Nov 6 Fri 10am)
- HW4 (due Dec 2 Wed 10am)
- (notes on HW solutions)
- 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%

(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) 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...

Lectures

(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 for bounded integers, string matching with "don't cares". (Ref: Clifford and Clifford'07)
Sep 4: Applications of FFT (cont'd): string matching with mismatches, subset sum. (Ref: Abrahamson'87, Chao and Xu'17)
Sep 9: Subset sum (cont'd). (Ref: Bringmann'17, Jin and Wu'19)
Sep 11: Matrix multiplication. (Ref: see my notes) (breaking news: a faster algorithm by Alman and Vassilevska W. (SODA'21) -- it's a tiny improvement!)
Sep 16: Matrix multiplication cont'd (rectangular, sparse). Applications: triangle finding. (Ref: Yuster and Zwick'05, Alon, Yuster, and Zwick'97)
Sep 18: Transitive closure. APSP... (Ref: Munro'71)
Sep 23: Directed APSP with small integer weights. (Ref: Zwick'02)
Sep 25: Undirected APSP with small integer weights. (Ref: Seidel'95, Shoshan and Zwick'99)
Sep 30: Min triangle and APSP with real vertex weights. (Ref: Vassilevska, Williams, and Yuster'06, Czumaj and Lingas'09, Sec 3 of C.'10)
Oct 2: Conditional lower bounds. APSP (or (min,+)-matrix multiplication) → negative-weight triangle. (Ref: Vassilevska W. and Williams'10)
Oct 7: APSP → zero-weight triangle; APSP → graph radius; (min,+)-convolution → (min,+)-matrix multiplication. (Ref: Thm 3.3 of Vassilevska W. and Williams'13, Abboud, Grandoni, and Vassilevska W.'15, Thm 10 of BCDEHILPT'14)
Oct 9: (min,+)-convolution → knapsack; (min,+)-convolution → min k-enclosing rectangle. (Ref: Cygan, Mucha, Wegrzycki, and Wlodarczyk'17 or Kunnemann, Paturi, and Schneider'17, Sec 3.5 of C. and Har-Peled'19)
Oct 14: SETH. k-SAT → subset sum... (Ref: Impagliazzo, Paturi, and Zane'01)
Oct 16: k-SAT → subset sum; k-SAT → OV (Ref: Abboud, Bringmann, Hermelin, and Shabtay'19)
Oct 21: 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 23: 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 28: 3SUM → geometry problems; 3SUM → convolution-3SUM → zero-weight triangle (Ref: Gajentaan and Overmars (originally from the '90s), Sec 2 of Patrascu'10 or Sec 6 of Kopelowitz, Pettie, Porat'16 or C. and He'20)
Oct 30: 3SUM → triangle listing (Ref: Patrascu'10)
Nov 4: 3SUM → jumbled text indexing. (Ref: Amir, C., Lewenstein, and Lewenstein'14)
Nov 6: 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 13: Real APSP and 3SUM further improved, via geometric techniques. (Ref: C.'05, Sec 3.1-3.2 of C.'18)
Nov 18 and Nov 20: APSP and OV via the polynomial method. (Ref: Williams'14, Abboud, Williams, and Yu'15, C. and Williams'16)
Dec 2: 3SUM via additive combinatorics. (Ref: C. and Lewenstein'15)
Dec 4, 9: student presentations