Title: Space-bounded Communication Complexity
Speaker: Periklis A. Papakonstantinou
Inviter: Prof. Sun Xiaoming, Center for Advanced Computing Research, ICT
Time: 14:00pm—15:00pm, June 5th, 2012 (Tuesday)
Place: Room 1234, Institute of Computing Technology, Chinese Academy of Sciences
Abstract:
We put forward a new 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 fundamentally new techniques (model-specific) for proving lower bounds. As a first step we aim 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 in progress with Joshua Broody, Shiteng Chen, Hao Song, and Xiaoming Sun