Title	CONGEST lower bounds : beyond two-party reductions
Creator	Oshman, Rotem
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2016-12-01T09:00
Description	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.
Extent	66 minutes
Subject	Mathematics; Computer science; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Tel-Aviv University
Series	BIRS Workshop Lecture Videos (Oaxaca de Juárez (Mexico))
Date Available	2017-06-22
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0348415
URI	http://hdl.handle.net/2429/62095
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos