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