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