CS 598 TMC, Fall 2020

Notes on HW1

• Problem 1: this was very briefly mentioned after Cor 4.3 in C. and Lewenstein (STOC'15)
• Problem 2: this was first obtained by Amir and Farach'91 (the problem is sometimes called "dominance" or "less than" string matching)
• Problem 3: this interesting Boolean matrix multiplication algorithm was suggested recently by Karppa and Kaski (SODA'19)

Notes on HW2

• Problem 2: I think I have a subcubic solution to the bonus research question...
• Problem 3: see Bae, Shinn, and Takaoka (COCOA'16). The first bonus part is doable by a clever recursion. (I still don't have an answer to the "bonus research" question.)

Notes on HW3

• Problem 3: Part (a) is from Labib, Uznanski, and Wolleb-Graf (CPM'19). Part (b) was attributed to Indyk; see also Sec 4 of Gawrychowski and Uznanski (ICALP'18) for a similar k-sensitive conditional lower bound proof.

Notes on HW4

• Problem 1: conditional lower bounds for this and many other dynamic graph problems were considered by Abboud and Vassilevska Williams (FOCS'14)
• Problem 2: this was first obtained by Bille and Farach-Colton'08
• Problem 3: it is also possible to get slightly subquadratic algorithm for the non-convolution version of the problem (finding collinear p_i, p_j, p_k without requiring k=i+j), by combining with geometric cutting techniques...