讨论组:算法、复杂性及密码组
标题:Space-bounded Communication Complexity
演讲人: Periklis A. Papakonstantinou University
时间: 2012-06-01 14:00-2012-06-01 15:30
地点:FIT 1-222

内容:

 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 in the difference in using 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

 



人物介绍: