BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

CONGEST lower bounds : beyond two-party reductions Oshman, Rotem 


Most CONGEST lower bounds are proven by reduction from two-party communication complexity. In this tutorial/talk we will discuss some limitations of existing reductions, and ways in which they might potentially be overcome. In particular, we'll cover: - The two-party pointer-chasing lower bound of Nisan-Widgerson - A connection between the broadcast congested clique and number-on-forehead communication complexity - The basics of multi-party number-in - hand communication complexity.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International