Group:Lunch Meeting
Title: Bounded-space communication complexity
Speaker: Shiteng Chen University
Time: 2011-11-10 12:00-2011-11-10 13:30
Venue: FIT 1-222


The model of this problems is Alice has a n bits string x, Bob has a n bits string y. And they want to compute some function f(x,y). But different from classical model, they don't have enough space to store the communication information. They only have s(n) bits, here, s(n)<n. And we have proved:

1. If s(n)<n-logn, there exist some boolean functions can not be compute.
2. For some non-boolean functions, we can prove they can't be compute with omega(n) space.
3. We can compute all of the functions in nondeterministic-space(s(n)) with space s(n)+logn in our model, even in one-way communication.
4. We proved a space hierarchy for this model.

Because of 3, now we know that it is very hard to prove so me functions can't be compute in our model with s(n) space. So now we're trying to prove something about the "oblivious bits", that is, the communication bits is only depends on x. We want to prove parity can't be compute with o(n) "oblivious bits", and we have some ideas now.

Joint work with Joshua Brody, Periklis Papakonstantinou, Hao Song and Xiaoming Sun