Alice's input to permutation pointer chasing
DefinitionNondetConn_Supplement_PCPermAliceInputcommunication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1permutationspointer-chasing
The paper fixes the starting vertex . Lean strengthens this to the delayed-start variant used in Appendix B, where Alice receives as input together with the odd-numbered permutation layers .
The Lean array contains ignored padding at Bob's even-numbered layers.
Definition code
import Mathlib set_option autoImplicit false namespace NondetConn.Supplement /-- Alice's input to permutation pointer chasing: the starting vertex and the odd-numbered permutation layers. The source fixes the starting vertex; treating it as an Alice input is the stronger delayed-start variant used in its Appendix B proof. Even-numbered entries are ignored padding. -/ structure PCPermAliceInput (n k : ℕ) where start : Fin n layer : Fin k → 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.2, p.3 (PDF p.5), and Appendix B, pp.45–49 (PDF pp.47–51)