Title	Query-to-Communication Lifting
Creator	Göös, Mika
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2017-03-21T09:04
Description	This will be a tutorial-style talk, with a particular focus on the following result. For any n-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f o g^n$, where $g$ is a small index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity. Joint work with Toniann Pitassi and Thomas Watson.
Extent	62.0
Subject	Mathematics; Computer science; Information and communication, circuits; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Harvard University
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2019-03-12
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0376808
URI	http://hdl.handle.net/2429/68642
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Postdoctoral
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos