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


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). In fact, 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 thecommunication, and speak one bit in odd-numbered rounds. Bob will always speak abit 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.