Speaker: Periklis Papakonstantinou
Title: Space-bounded Communication Complexity
We put forward a program for developing tools towards understanding the limitations of space-bounded computation. This new, pure information-theoretic model restricts the classical 2-player communication complexity model by limiting (in some sense) the space each player can use to compress communication. We set the foundations of this model, and we develop two new techniques (model-specific) for proving lower bounds. A first non-trivial step aims to provide a concrete explanation on what's different in the use of space when computing each of the following three basic functions: EQUALITY, INNER-PRODUCT, and st-CONNECTIVITY.
This is joint work (also in progress) with Joshua Broody, Shiteng Chen, Hao Song, Xiaoming Sun, and Andrew Yao.
 Space-bounded Communication Complexity joint with Joshua Broody, Shiteng Chen, Hao Song, Xiaoming Sun
(to be submitted this August)
 Advances in space-bounded Communication Complexity lower bounds joint with Hao Song, Andrew Yao
(work in progress)