Bob's input to
DefinitionNondetConn_Supplement_IPPCBobInputcommunication-complexityinner-productp2o-gran-per-chapterp2o-plan-paperp2o-v1pointer-chasing
Bob's input to consists of bit vectors and the permutations for even paper indices .
Lean stores padded permutation arrays and ignores Bob's entries at odd paper layers.
Definition code
import Definitions.Def_NondetConn_Supplement_IPPCAliceInput
set_option autoImplicit false
namespace NondetConn.Supplement
/-- Bob's input to `IP∘PC_{n,r}`: the two bit vectors and the even-numbered permutation
layers. Entries at the other parity are harmless ignored padding. -/
structure IPPCBobInput (n r : ℕ) where
vectors : (Fin n → Bool) × (Fin n → Bool)
layers : IPPCAliceInput n r
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)