0
$\begingroup$

What does rounds in communication complexity mean in setting of deterministic/non-deterministic $2$ party communication or multi party setting?

Is it number of bits exchanged between players participating/involved?

In multiparty setting what does simultaneous and non-simultaneous messaging means? Is it related to round?

Improve this question
$\endgroup$
3
  • $\begingroup$ What research and self-study have you done? Where have you looked? We expect you to do a significant amount of research before asking to show us in the question what you've tried. This is covered in standard textbooks on communication complexity; questions that are covered in standard resources typically don't make a good question on this site. $\endgroup$
    – D.W. ♦
    Commented Jan 16, 2015 at 21:06
  • $\begingroup$ I did a fair amount of googling. I could not locate a precise definition of round. $\endgroup$
    – Turbo
    Commented Jan 16, 2015 at 21:20
  • $\begingroup$ Googling is not a substitute for reading and self-study of standard resources, such as textbooks on the subject. $\endgroup$
    – D.W. ♦
    Commented Jan 16, 2015 at 22:37

2 Answers 2

Reset to default
2
$\begingroup$

The notion of round should be quite similar to the intuitive idea of "one step of the protocol". At any round you are allowed to send 1 message (of any size) and/or receive one message. The message you send at round $i$ may depend on all the information you have up to round $i$, but it cannot depend on the message you receive at round $i$ (or later). It follows that any information that depends on the the message you receive at round $i$ may be sent only at round $\ge i+1$. This sequentiality is the core of splitting into rounds, they just formulate the causality of the protocol

Since the above doesn't determine the size of each message sent, one can define the communication complexity to be exactly the number of bits communicated throughout.

As for simultaneous transmission of messages: In the above informal description I wrote:

At any round you are allowed to send 1 message (of any size) and/or receive one message.

note the and/or part. If simultaneous transmission is allowed, then each party sends a message and receives one. If no simultaneous messages allowed, then the party either sends or receives a message, but not both. This makes the partitioning to rounds more crisp: every time the sender party changes, it is a new round.

finally, I repeat the recommendation of @hengxin, and refer you to the book of Kushilevitz and Nissan.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there a nuance with respect to multiparty protocol (simultaneous/non-suimultaneous)? $\endgroup$
    – Turbo
    Commented Jan 16, 2015 at 21:23
  • $\begingroup$ In the multiparty simultaneous case, every party gets to send one message, and all these messages are delivered at the same round. For non-simultaneous transmissions, one needs to define the order of speaking (round robin, etc.) $\endgroup$
    – Ran G.
    Commented Jan 16, 2015 at 22:58
1
$\begingroup$

Round: The protocol (or the communication game) proceeds in rounds. In each round, some bits are communicated. In the simple model of Alice and Bob to evaluate some function f, it depends on the protocol P that specifies which player sends a bit of communication (and of course, what bit to send) next.

Complexity measure: The communication complexity refers to the number of bits communicated.

Simutaneous: Simultaneous protocols were defined in the paper "Simultaneous Messages vs. Communication" [1].

We consider a restricted version of the multiparty communication game which we call the simultaneous messages model. The difference is that in this model, each of the $k$ players simultaneously sends a message to a referee, who sees none of the input. The referee then announces the function value.

Note: The answer above is by no means formal and rigorous. For the mathematically precise answer, please refer to the book "Communication Complexity" by Eyal Kushilevitz and NoamNisan.

[1] Simultaneous Messages vs. Communication. Babai, Kimmel, and Lokam 1995

Improve this answer
$\endgroup$
6
  • $\begingroup$ So what is a round? $\endgroup$
    – Turbo
    Commented Jan 14, 2015 at 10:13
  • $\begingroup$ @Turbo The protocol (or the communication game) proceeds in rounds. In each round, some bits are communicated. $\endgroup$
    – hengxin
    Commented Jan 14, 2015 at 11:49
  • $\begingroup$ So each round A sends 1 bit to B. Next round B sends 1 bit to A? $\endgroup$
    – Turbo
    Commented Jan 14, 2015 at 11:53
  • $\begingroup$ @Turbo In the simple model of Alice and Bob to evaluate some function $f$, it depends on the protocol $\mathcal{P}$ that specifies which player sends a bit of communication (and of course, what bit to send) next. $\endgroup$
    – hengxin
    Commented Jan 14, 2015 at 12:02
  • 1
    $\begingroup$ @Turbo It is difficult for me to give a formal and rigorous answer for all the questions. Sorry for that. However, the book mentioned in the answer would be helpful. Looking forward to other answers. $\endgroup$
    – hengxin
    Commented Jan 14, 2015 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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