First sender of a public-coin protocol
DefinitionNondetConn_Supplement_startsWithcommunication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1pointer-chasingrandomized-protocols
A protocol starts with Alice (respectively, starts with Bob) when every public-coin communication tree with a nonempty transcript has Alice (respectively, Bob) send the first bit.
This records the paper's default Alice-first convention and the explicit Bob-first convention of Theorem B.1.
Definition code
import Definitions.Def_CommThresholdPR_StrongConverse_Protocols
set_option autoImplicit false
namespace NondetConn.Supplement
open CommThresholdPR.StrongConverse
/-- Every public-coin tree starts with the specified party (`true` for Alice, `false` for
Bob). A zero-communication tree is allowed for either convention. -/
def startsWith {X Y A B : Type} (P : Protocol X Y A B) (alice : Bool) : Prop :=
∀ ω, P.publicLaw ω ≠ 0 → match P.tree ω with
| .leaf _ _ => True
| .alice _ _ _ => alice = true
| .bob _ _ _ => alice = false
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), §3, p.8 (PDF p.10), and Theorem B.1, p.45 (PDF p.47)