Deterministic protocols inside the randomized tree model
DefinitionNondetConn_Supplement_isDeterministiccommunication-complexitydeterministic-protocolsp2o-gran-per-chapterp2o-plan-paperp2o-v1pointer-chasing
A protocol is deterministic when its public coin is a point mass and every local message and output kernel is also a point mass.
This identifies ordinary deterministic interactive protocols inside the shared randomized communication-tree representation used by the supplement.
Definition code
import Definitions.Def_CommThresholdPR_StrongConverse_Protocols
set_option autoImplicit false
namespace NondetConn.Supplement
open CommThresholdPR.StrongConverse
/-- A protocol has one fixed public coin and every local message/output kernel is a point
mass. This identifies the deterministic protocols inside the general randomized tree model. -/
def isDeterministic {X Y A B : Type} (P : Protocol X Y A B) : Prop :=
∃ ω, P.publicLaw = PMF.pure ω ∧
let rec deterministicTree : BinaryTree X Y A B → Prop
| .leaf outA outB =>
(∀ x, ∃ a, outA x = PMF.pure a) ∧ (∀ y, ∃ b, outB y = PMF.pure b)
| .alice bit zero one =>
(∀ x, ∃ b, bit x = PMF.pure b) ∧ deterministicTree zero ∧ deterministicTree one
| .bob bit zero one =>
(∀ y, ∃ b, bit y = PMF.pure b) ∧ deterministicTree zero ∧ deterministicTree one
deterministicTree (P.tree ω)
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), Theorem B.1, p.45 (PDF p.47)