1
$\begingroup$

There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.

I want to consider more restricted protocol that is "send once" protocol.

For example, Alice, Bob, and Cate are players and their communication must follow the following way:

Alice is only able to send Bob. Bob is only able to send Cate .

Each plyer sent bits just one time.

Are there lower bounds results and methods that k-party NIH or NOF communication complexity for set-disjointness and other functions ?

$\endgroup$
  • 3
    $\begingroup$ Why does your model not decompose into two games A->B and B->C? $\endgroup$ – András Salamon Mar 17 '13 at 0:40
3
$\begingroup$

There are several flavors of communication complexity. It sounds like your "send once" model is uses one-way communication and private messages. For concreteness, I give short synopses of some different communication complexity variants below.

Say there are k players who wish to jointly compute a function f(x_1,...,x_k) on k different inputs. Some different variants:

(1) One-way complexity vs interactive communication: In this setting, player 1 sends a single message, then player 2, etc. Player k computes the output of the protocol. With interactive communication, players may speak back and forth.

(2) Broadcast vs. private-messages models: In the broadcast model of communication, each message is received by all players. In the private-messages model, messages are sent point-to-point i.e., a message can come from player i to player j. In this model, if player i wants to communicate with all players, he must send individual messages to each other player. Broadcast messages is a stronger model, so lower bounds in the broadcast model will give you lower bounds in the private-messages model, and upper bounds for private-messages will give you upper bounds in the broadcast model.

(3) NIH vs. NOF complexity: In the Number-in-Hand (NIH) communication model, player i sees only x_i. In the Number-on-the-Forehead (NOF) communication model, player i sees all inputs except x_i. NOF lower bounds are harder to show, because players share inputs. Intuitively, this should allow players to compute a function using less communication, thus making lower bounds harder to prove.

As I said, I sense that you're looking for one-way communication with private messages (and perhaps importantly you're assuming the private messages only go from player i to player i+1). This setting is not very well-studied, but the NIH version of this setting is extremely well-motivated: The standard reduction from communication complexity to one-pass streaming algorithms naturally gives you a one-way protocol where player i sends a single (private) message to player i+1. Thus, lower bounds in this setting yield streaming algorithm lower bounds.

There are a couple of reasons why the one-way private-message model is not-as-studied, despite having such strong motivation. First, there's a longer history and more established toolbox for proving lower bounds in the broadcast model. Second, the lower bounds achieved from the broadcast model are typically very close to the upper bounds you get from the streaming algorithms, so it's not always necessary to use private-messages for your lower bounds.

One example where the communication bound crucially uses private-messages and not broadcast messages is the following bound for estimating the length of the longest increasing subsequence in a stream:

Gal, Gopalan SIAM Journal of Computing 2010. Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

Note that their communication bound is for deterministic protocols. Determining the space complexity of randomized streaming algs for estimating LIS is a big open problem.

For the private messages NIH communication model, there is a recent paper by Woodruff and Zhang that gives several strong communication lower bounds, as well as good applications towards distributed functional monitoring. They mostly cover interactive (rather than one-way) communication complexity, but it's worth reading.

Woodruff, Zhang STOC12. Tight Bounds for Distributed Functional Monitoring

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.