Last speaker of a binary communication transcript
DefinitionNondetConn_Supplement_lastSpeakercommunication-complexitylower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-protocols
The last speaker of a nonempty transcript is Alice or Bob according to which party sent its final bit. This identifies the receiver of the last message, whose output is the only one required by the paper's convention.
The empty transcript has no last speaker.
Definition code
import Definitions.Def_CommThresholdPR_StrongConverse_Protocols
set_option autoImplicit false
namespace NondetConn.Supplement
open CommThresholdPR.StrongConverse
/-- The party that sent the last bit along a transcript (`true` for Alice, `false` for Bob).
It is `none` for an empty or malformed transcript. -/
def lastSpeaker {X Y A B : Type} : BinaryTree X Y A B → List Bool → Option Bool
| .leaf _ _, _ => none
| .alice _ _ _, [] => none
| .bob _ _ _, [] => none
| .alice _ zero one, bit :: rest =>
match lastSpeaker (if bit then one else zero) rest with
| some party => some party
| none => some true
| .bob _ zero one, bit :: rest =>
match lastSpeaker (if bit then one else zero) rest with
| some party => some party
| none => some false
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)