Mika Göös: Query-to-Communication Lifting Theorems

Friday, November 4, 2016 - 1:30pm to 4:30pm
Pizza at 1:15p
MIT, Star, D463
Mika Göös

Abstract:  I will discuss new lower bound methods in communication complexity that "lift" lower bounds from decision tree complexity. These methods have recently enabled progress on core questions in communication complexity (log-rank conjecture, classical--quantum separations) and related areas (circuit complexity, proof complexity, LP/SDP formulations). In the 1st half, I will prove a simple lifting theorem for NP (non-deterministic query/communication complexity). In the 2nd half, I will discuss some ongoing work on finding lifting theorems for P^NP.