Bob's input to permutation pointer chasing
DefinitionNondetConn_Supplement_PCPermBobInputcommunication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1permutationspointer-chasing
Bob's input to consists of the even-numbered permutation layers .
The Lean array contains ignored padding at Alice's odd-numbered layers.
Definition code
import Mathlib set_option autoImplicit false namespace NondetConn.Supplement /-- Bob's input to permutation pointer chasing: the even-numbered permutation layers. Odd-numbered entries are ignored padding. -/ structure PCPermBobInput (n k : ℕ) where 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)