Bit permutation pointer chasing
DefinitionNondetConn_Supplement_bpcPermcommunication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1permutationspointer-chasing
The bit problem returns the parity of the final vertex of permutation pointer chasing.
Since the paper labels from while Lean's Fin n is zero-based, Lean returns the parity of v.val + 1.
Definition code
import Definitions.Def_NondetConn_Supplement_pcPerm
set_option autoImplicit false
namespace NondetConn.Supplement
/-- The bit version `bPC-Perm_{n,k}`: the parity of the final pointer-chasing vertex.
Because `Fin n` is zero-based while the paper's `[n]` is one-based, the returned bit is
the parity of `v.val + 1`. -/
def bpcPerm (n k : ℕ) (alice : PCPermAliceInput n k) (bob : PCPermBobInput n k) : Bool :=
decide (Odd ((pcPerm n k alice bob).val + 1))
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)