Alice's input to
DefinitionNondetConn_Supplement_IPPCAliceInputcommunication-complexityinner-productp2o-gran-per-chapterp2o-plan-paperp2o-v1pointer-chasing
Alice's input to consists of the permutations for odd paper indices .
Lean stores arrays at all zero-based indices and ignores Alice's padded entries at even paper layers; hence Alice controls exactly the even-valued Lean indices.
Definition code
import Mathlib
set_option autoImplicit false
namespace NondetConn.Supplement
/-- Alice's input to `IP∘PC_{n,r}`. Entry `i` is used when the paper's layer `i+1` is
odd; the other entries are harmless padding that the communication function ignores. -/
structure IPPCAliceInput (n r : ℕ) where
A : Fin r → Equiv.Perm (Fin n)
B : Fin r → Equiv.Perm (Fin n)
deriving Fintype
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), §1.1, pp.2–3 (PDF pp.4–5), and Theorem 7.1, p.22 (PDF p.24)