2
$\begingroup$

I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf and in specifically the following text:

What’s a good protocol for computing MAJORITY? The natural thing to do is to have Alice and Bob send the vote counts! Over multiple rounds, when it’s Alice’s turn, she sends bits of the integer $N_x$ which is the number of 1s in $x$, Bob computes $N_y$ which is the number of 1s in $y$, and Bob sends 1 to Alice if and only if $N_x+N_y$ is greater than $n$. (Note the total number of voters is $2n$.) If Alice sends $N_x$ encoded in binary, this takes $O(\log n)$ rounds. We therefore have:

If Alice is sending her total number of 1s over $\approx \log n$ bits to Bob ... what is Bob sending in back in return before the Alice is done with her input? I assumed or thought that in communication complexity, Alice and Bob are always taking turns back and forth right? Can Bob not send anything and just wait for Alice to send the $\log n$ bits?

$\endgroup$
3
$\begingroup$

Yes it's perfectly fine for one player to send multiple bits while the other waits. In fact, "the" trivial upper bound on communication complexity is having one party send its input to the other one, who can then compute the output locally (although note that there are some very nice and non-trivial probabilistic algorithms -- e.g. for EQ -- even for one-way communication, where Alice can talk to Bob but not the reverse). A deterministic communication protocol specifies, as a function of the transcript so far, if Alice or Bob should speak next. Additionally it always specifies when the communication has ended.

Ryan Williams' notes, which you linked, deals at first with the simplified setting:

In general, Alice and Bob will speak one bit each, in rounds. Alice will always start the communication, and speak one bit in odd-numbered rounds. Bob will always speak a bit in even-numbered rounds.

If you only care about communication complexity and not round complexity, you can replace the above with "Alice and Bob will speak at most one bit each, in rounds [...]" to capture the more general case.

$\endgroup$
  • $\begingroup$ What you quoted is exactly what confused me for a little bit because I thought THEY MUST go in rounds sending 1 bit at a time! $\endgroup$ – nemo Oct 16 '20 at 5:07
  • $\begingroup$ @nemo If you think about it, you could also design it so Bob always sends a 0 in those rounds, and it wouldn't affect the big-O complexity. $\endgroup$ – user253751 Oct 16 '20 at 12:31
  • $\begingroup$ oh yes!! thank you Bob can send garbage .... and it would just be twice the bits $\endgroup$ – nemo Oct 16 '20 at 21:00

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.