« search calendars« DIMACS Day of Complexity Tutorials
« Help Me Solve All Problems in Communication Complexity (via Lifting)
Help Me Solve All Problems in Communication Complexity (via Lifting)
July 17, 2019, 9:00 AM - 10:15 AM
Location:
Rutgers Academic Building, Room 2225
Rutgers University
College Avenue Campus
15 Seminary Place
New Brunswick, NJ
Click here for map.
Mika Göös, Institute for Advanced Study
Lifting theorems translate lower bounds for simple models of computation (e.g., decision trees) to lower bounds for more powerful models (e.g., communication protocols). These techniques have recently enabled progress on core questions in communication complexity, circuit complexity, proof complexity, and LP/SDP extension complexity. This tutorial is an introduction to these topics, with a special emphasis on open problems.