Lower Bounds for Randomised Algorithms
Reading Group, Fall 2020
Fridays at 15:15 - Online
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.
Mika has two copies of the book!
Part I – Decision trees
Part II – Communication protocols