Communication rounds as alternating message blocks
DefinitionNondetConn_Supplement_communicationRoundscommunication-complexitylower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-protocols
A binary communication transcript is partitioned into maximal consecutive blocks sent by the same party. Its number of communication rounds is the number of those blocks.
Thus a message may contain several bits and consecutive messages alternate between Alice and Bob. The theorem statements bound this count on every positive-probability execution, which is the paper's worst-case -round convention.
Definition code
import Definitions.Def_CommThresholdPR_StrongConverse_Protocols
set_option autoImplicit false
namespace NondetConn.Supplement
open CommThresholdPR.StrongConverse
/-- The number of alternating message blocks along a binary transcript. Consecutive bits
sent by the same party form one message/round. -/
def communicationRounds {X Y A B : Type} : BinaryTree X Y A B → List Bool → ℕ :=
let rec go (previous : Option Bool) : BinaryTree X Y A B → List Bool → ℕ
| .leaf _ _, _ => 0
| .alice _ _ _, [] => 0
| .bob _ _ _, [] => 0
| .alice _ zero one, bit :: rest =>
(if previous = some true then 0 else 1) +
go (some true) (if bit then one else zero) rest
| .bob _ zero one, bit :: rest =>
(if previous = some false then 0 else 1) +
go (some false) (if bit then one else zero) rest
go none
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), §3 Communication complexity, p.8 (PDF p.10)