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: Bae, Shinn, and Takaoka (COCOA'16)