The function
DefinitionNondetConn_Supplement_ippccommunication-complexityinner-productp2o-gran-per-chapterp2o-plan-paperp2o-v1pointer-chasing
Given and alternatingly owned permutations of , define
Permutations act as permutation matrices: . This is the communication problem of Theorems 7.1 and C.1.
Definition code
import Definitions.Def_NondetConn_Supplement_IPPCAliceInput
import Definitions.Def_NondetConn_Supplement_IPPCBobInput
set_option autoImplicit false
namespace NondetConn.Supplement
/-- The Boolean function `IP∘PC_{n,r}`. Alice supplies the odd-numbered permutation layers,
Bob supplies the even-numbered layers and `X,Y`, and the output is the binary inner product
`<A_r⋯A_1 X, B_r⋯B_1 Y>`.
The paper's `[n]={1,…,n}` is `Fin n`; a permutation matrix sends a vector `x` to
`j ↦ x(σ⁻¹(j))`. Lean layer index `i` represents paper layer `i+1`, so Alice owns
exactly the even-valued Lean indices. -/
def ippc (n r : ℕ) (alice : IPPCAliceInput n r) (bob : IPPCBobInput n r) : Bool :=
let fullA : Fin r → Equiv.Perm (Fin n) :=
fun i ↦ if Even i.val then alice.A i else bob.layers.A i
let fullB : Fin r → Equiv.Perm (Fin n) :=
fun i ↦ if Even i.val then alice.B i else bob.layers.B i
let act (x : Fin n → Bool) (p : Equiv.Perm (Fin n)) : Fin n → Bool :=
fun j ↦ x (p.symm j)
let xFinal := (List.ofFn fullA).foldl act bob.vectors.1
let yFinal := (List.ofFn fullB).foldl act bob.vectors.2
decide (Odd ((Finset.univ.filter fun j ↦ xFinal j && yFinal j).card))
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)