Search Mailing List Archives
[theory-seminar] Two Theory Seminars This Week: Toniann Pitassi on 10/31 and Rotem Oshman on 11/2
ofirgeri at stanford.edu
Mon Oct 29 21:40:00 PDT 2018
This week we will have two theory seminars. On Wednesday (10/31), Toniann Pitassi (University of Toronto and Institute for Advanced Study) will give a talk on Lifting in Communication Complexity and Beyond (see abstract below). The talk will take place in Gates 463A at 3:00 PM.
Later this week on Friday, Rotem Oshman (Tel-Aviv University) will give a talk on Two Open Problems in Distributed Graph Algorithms. Another announcement will be sent closer to Friday.
The seminar schedule and abstracts are also available at:
Hope to see you there!
Lifting in Communication Complexity and Beyond
Speaker: Toniann Pitassi (University of Toronto and Institute for Advanced Study)
Hardness escalation or query-to-communication lifting is a method of proving tight upper and lower bounds on the complexity of a composed function or relation by a reduction to the query complexity of the base function. This talk will primarily be a tutorial. We will give many applications of lifting, including new and improved circuit lower bounds, as well as lower bounds in game theory, proof complexity and extended formulation complexity. We will sketch the main ideas in the proofs of lifting for randomized communication complexity, and conclude with new directions. This is joint work with Mika Goos and Thomas Watson.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar