|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Introduction to Query-to-Communication Lifting|
|Affiliation:||Member, School of Mathematics|
|Date:||Tuesday, November 20|
|Time/Room:||10:30am - 12:30pm/Simonyi Hall 101|
I will survey 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). I will prove one concrete lifting theorem for non-deterministic (NP) query/communication models.