October 14, 2017
FOCS 2017, Berkeley
https://raghumeka.github.io/workshop.html
The topic of this workshop is ‘hardness escalation’, a growing research area whereby lower bounds and separations in communication complexity are obtained by developing “simulation theorems”. The basic idea of a simulation theorem is to start with a simple ‘one-party’ function and “lift it” to a multi-party setting via function composition. These simulation theorems have introduced new tools into complexity theory, and have led to the resolution of many longstanding open problems including in graph theory, combinatorial optimization, circuit complexity and cryptography, proof complexity, game theory, and communication complexity. Moreover the field has led to a revival of query complexity, with new techniques leading to the resolution of some longstanding open problems. The goal of the workshop is to present a broad introduction to the area as well as highlight the recent developments.
CS Theory Events 