Reading Group

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

25.9 Introduction (Mika)

Boolean function complexity measures: decision trees, certificates, (block) sensitivity, degree.
Buhrman–de Wolf survey: https://doi.org/10.1016/S0304-3975(01)00144-X

2.10 Randomised decision trees (Mika)

Minimax theorem, direct sum, OR lemma
Jain–Klauck–Santha: https://arxiv.org/abs/1004.0105

9.10 Strong direct sum (Gilbert)

“Strong” versions of direct sum and XOR lemmas
Brody–Blais: https://arxiv.org/abs/1908.01020
Brody et al.: https://arxiv.org/abs/2007.05580

16.10 No seminar
23.10 Intro to composition conjecture (Mika)

Sabotage complexity, counter-example to general conjecture
Ben-David–Kothari: https://arxiv.org/abs/1605.09071
Gavinsky et al.: https://arxiv.org/abs/1811.10752

30.10 New minimax theorem (Mika)

Ben-David–Blais: https://arxiv.org/abs/2002.10802 (FOCS'20 Best Paper!)

6.11 Search problems in query complexity (Siddhartha)

Lovász et al.: https://core.ac.uk/download/pdf/190866441.pdf
Pudlák: https://users.math.cas.cz/~pudlak/prfgame.ps

Part II – Communication protocols

13.11 Intro to randomized communication complexity (Mika)

Textbook by Rao–Yehudayoff

20.11 Discrepancy (Xinrui)

Chapter 5 in Rao–Yehudayoff

27.11 Information complexity (Michael)

Chapter 6 in Rao–Yehudayoff

4.12 Compressing communication (Michael)

Chapter 7 in Rao–Yehudayoff

11.12 Lifting (Siddharta)

Chapter 8 in Rao–Yehudayoff