The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?

Question

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?

Answer 1

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.