Permutation pointer chasing
DefinitionNondetConn_Supplement_pcPermcommunication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1permutationspointer-chasing
Starting from , permutation pointer chasing recursively sets through alternatingly owned permutation layers and outputs :
This is the permutation-restricted pointer-chasing problem used in Appendix B.
Definition code
import Definitions.Def_NondetConn_Supplement_PCPermAliceInput
import Definitions.Def_NondetConn_Supplement_PCPermBobInput
set_option autoImplicit false
namespace NondetConn.Supplement
/-- Permutation pointer chasing `PC-Perm_{n,k}`: starting at `v₀`, apply the `k`
alternatingly owned permutation layers in order and return the final vertex. -/
def pcPerm (n k : ℕ) (alice : PCPermAliceInput n k) (bob : PCPermBobInput n k) : Fin n :=
let layer : Fin k → Equiv.Perm (Fin n) :=
fun i ↦ if Even i.val then alice.layer i else bob.layer i
(List.ofFn layer).foldl (fun v p ↦ p v) alice.start
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, p.45 (PDF p.47)