Lower Bounds for Randomised Algorithms
Reading Group, Fall 2020
Fridays at 15:15 in BC02 (we have the room until 17:00)
In this reading group, we will study basic techniques to prove lower bounds for simple models of randomised computation: randomised decision trees (Part I) and communication protocols (Part II). Highlights include a New Minimax Theorem by Ben-David and Blais, which won the Best Paper Award at FOCS'20, and delving into a brand new textbook (published 2020) on Communication Complexity by Rao and Yehudayoff.
Part I – Decision trees
Part II – Communication protocols