CS 598 TMC, Fall 2020
Notes on HW1
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
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...