Thursday, December 14, 2006

Continuous Communication Complexity

Alice and Bob are seeing a continuously changing set of numbers. At time t, set Alice has is A_t and set Bob has is B_t. A_t and B_t each change by addition or removal of an element during each time step. They communicate with Carole independently (one way or two way). Carole must report |A_t union B_t|, at all times t. The goal is to minimize the total number of bits sent between (Alice,Bob) and (Carole). Is there a good theory one can develop?

Notes: One should allow Carole to approximate |A_t \union B_t|. This seems related to Slepian-Wolf where A and B independently communicate their individual streams to C and the goal is to make use of mutual information in their streams. Things get tricky when we allow A, B or C use models to predict how A_t, B_t vary over time t.

Refs: There has been a few papers recently in the database community that give upper bounds on the number of bits communicated for different problems. It is called distributed, continuous streaming. There is a survey and a tutorial by Graham Cormode and Minos Garofalakis. What we need is a good theory and a semblance of lower bounds.

5 Comments:

Anonymous Term Papers said...

I never thought of it like that, but it really is true.

11:14 PM  
Anonymous Term papers said...

Valuable information and excellent design you got here!

11:51 PM  
Anonymous cheap viagra said...

This an interesting article, I wasn't aware that this can grow into a bigger problem, thanks for the update.

9:16 AM  
Anonymous viagra online said...

An old communicative dilemma, I wonder why intellectuals didn't investigate this problem well.

7:06 AM  
Anonymous pittsburgh hotel said...

really cool stuff we have there. Hey I see smart article, I love it greatly because I cannot find any one thing greater than your writers. I will note your feed to keep up to date with your approaching updates. Just striking and do uphold up the good work..

10:38 PM  

Post a Comment

<< Home