Theorem 7.1 — tight lower bound for when
OpenNondetConn.Supplement.theorem_7_1communication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pointer-chasingrandomized-lower-bounds
For every fixed , there is with the following property. For every positive satisfying there is such that, for every , every Alice-first randomized protocol for with at most rounds and worst-case error at most communicates at least
bits in the worst case.
The lower bound loses no factor depending on the number of rounds throughout this regime.
Differences from the source:
- reading: and → for each fixed error, one positive constant before every integer-valued round family with , followed by a family-dependent threshold; reason: this retains the varying-round asymptotic theorem rather than a fixed-round special case
- encoding: and permutation-matrix action →
Fin nand ; reason: zero-based indexing is a bijective encoding and the inverse-index action is exactly the paper's permutation matrix convention - generalization: each party receives only its owned permutation layers → each party structure also contains ignored padding at unowned layers; reason: fixing the padding recovers every source instance, while the Lean theorem covers all redundant representations because the function ignores those entries
- encoding: an -round randomized protocol with receiver-only output → a finite communication tree with at most alternating sender blocks, receiver-only correctness, and both outputs checked only when no message is sent; reason: this represents the same interactive protocols and resolves the source's undefined zero-message receiver without affecting the eventual lower bound
Preamble
import Definitions.Def_NondetConn_Supplement_communicationRounds import Definitions.Def_NondetConn_Supplement_ippc import Definitions.Def_NondetConn_Supplement_solves import Definitions.Def_NondetConn_Supplement_startsWith set_option autoImplicit false
Formal statement
namespace NondetConn.Supplement
open Filter CommThresholdPR.StrongConverse
/-- **Theorem 7.1** (Zhang, *Settling Nondeterministic Communication Complexity of Graph
Connectivity*, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), printed pp.22 and 26,
PDF pp.24 and 28). If `r(n)=o(log₂ n)`, every `r(n)`-round randomized protocol for
`IP∘PC_{n,r(n)}` with any fixed error below `1/2` communicates `Ω(n log₂ n)` bits.
**Formalization Note** Alice's input structure supplies the odd-numbered permutation layers;
Bob's supplies `X,Y` and the even-numbered layers. Unused parity entries are ignored padding.
Fixing that padding recovers every source instance, while the statement covers all redundant
representations. The lower-bound constant is fixed across the full varying-round asymptotic
regime. -/
theorem theorem_7_1 :
∀ ε : ℝ, 0 < ε → ε < 1 / 2 →
∃ c : ℝ, 0 < c ∧ ∀ rounds : ℕ → ℕ,
Tendsto (fun n ↦ (rounds n : ℝ) / Real.logb 2 n) atTop (nhds 0) →
(∀ n, 1 ≤ rounds n) →
∃ n₀ : ℕ, ∀ n, 1 ≤ n → n₀ ≤ n →
∀ P : Protocol (IPPCAliceInput n (rounds n)) (IPPCBobInput n (rounds n)) Bool Bool,
startsWith P true →
(∀ a b ω z, P.publicLaw ω ≠ 0 → (P.tree ω).finiteRun a b z ≠ 0 →
communicationRounds (P.tree ω) (P.bits ⟨ω, z.1⟩) ≤ rounds n) →
solves P (fun _ _ ↦ True) (ippc n (rounds n)) ε →
c * (n : ℝ) * Real.logb 2 n ≤ (P.cost : ℝ) := by sorry
end NondetConn.Supplement
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), Theorem 7.1, pp.22 and 26 (PDF pp.24 and 28)