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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International