Theorem 6.1 — round-dependent randomized lower bound for
OpenNondetConn.Supplement.theorem_6_1communication-complexitygraph-connectivityp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-lower-bounds
For every fixed error probability , there is with the following property. For every positive satisfying there is such that, for every even , every Alice-first randomized protocol for using at most rounds and having worst-case error at most communicates at least
bits in the worst case.
The bound remains superlinear throughout the full regime.
Differences from the source:
- reading: and → for each fixed error, one positive lower-bound constant before every integer-valued round family with , followed by a family-dependent threshold; reason: this is the non-vacuous quantified meaning of the two asymptotic symbols
- encoding: an -round randomized protocol with constant error below → a communication tree whose maximal number of alternating sender blocks is at most , whose receiver has worst-case error at most a fixed , and whose two outputs are both checked only when no message is sent; reason: maximal sender blocks are the paper's messages/rounds, and the zero-message convention resolves an undefined receiver without affecting the positive asymptotic bound
Preamble
import Definitions.Def_NondetConn_bConn import Definitions.Def_NondetConn_Supplement_communicationRounds 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 6.1** (Zhang, *Settling Nondeterministic Communication Complexity of Graph
Connectivity*, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), printed p.21,
PDF p.23). If the positive integer-valued round bound satisfies `r(N)=o(log₂ N)`, every
`r(N)`-round randomized protocol for `bConn_N` with any fixed error below `1/2` communicates
`Ω((N/r(N)) log₂ N)` bits in the worst case.
**Formalization Note** Little-o is the displayed quotient tending to zero. A round is a
maximal consecutive block of bits sent by one party, not an individual bit. The constants
and threshold are uniform in the growing size `N` and its varying round count. -/
theorem theorem_6_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 → Even N → N₀ ≤ N →
∀ P : Protocol (Equiv.Perm (Fin (N / 2))) (Equiv.Perm (Fin (N / 2))) 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) (fun a b ↦ decide (NondetConn.bConn (N / 2) a b)) ε →
c * ((N : ℝ) / (rounds 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 6.1, p.21 (PDF p.23)