# Computer Science/Discrete Mathematics Seminar II

**Topic: **Introduction to Query-to-Communication Lifting

**Speaker: **Mika Goos

**Affiliation: **Member, School of Mathematics

**Date & Time: **Tuesday November 20th, 2018, 10:30am - 12:30pm

**Location: **Simonyi Hall 101

**Video:** https://video.ias.edu/csdm/2018/1120-MikaGoos

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.