Theorem 5.1 — error-dependent randomized lower bound for
OpenNondetConn.Supplement.theorem_5_1communication-complexitygraph-connectivityp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-lower-bounds
There are absolute constants and such that the following holds uniformly for every error function satisfying on even . For every even , every randomized protocol for with worst-case error at most communicates at least
bits in the worst case, regardless of its number of rounds.
This strengthens the nondeterministic lower bound to weighted, almost monochromatic rectangles and is optimal for polynomially small error.
Differences from the source:
- reading: for → one positive constant and one threshold chosen before the entire error function, followed by every even above the threshold; reason: this is the uniform asymptotic reading required by the theorem's varying-error notation
- encoding: randomized protocols with receiver-only output and worst-case communication/error → the published finite communication-tree model with explicit public and private kernels, Alice first, receiver-only correctness, and both outputs checked only when no message is sent; reason: it represents the same finite-input interactive protocols and resolves the source's undefined zero-message receiver without affecting this positive asymptotic bound
Preamble
import Definitions.Def_NondetConn_bConn import Definitions.Def_NondetConn_Supplement_solves import Definitions.Def_NondetConn_Supplement_startsWith set_option autoImplicit false
Formal statement
namespace NondetConn.Supplement
open CommThresholdPR.StrongConverse
/-- **Theorem 5.1** (Zhang, *Settling Nondeterministic Communication Complexity of Graph
Connectivity*, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), printed p.14,
PDF p.16). Uniformly for every error function `ε(N) ∈ (0,1/3)`, any randomized
protocol for `bConn_N` has worst-case communication
`Ω(N log₂(min(1/ε(N),N)))`, without a round bound.
**Formalization Note** The absolute lower-bound constant and threshold precede `ε`, expressing
the theorem's uniformity over error functions. `N` remains the even total number of vertices,
while the published `bConn` takes permutations of `Fin (N/2)`. The public/private-randomness
tree model measures the worst-case number of communicated bits; only the receiver of the last
message must output. -/
theorem theorem_5_1 :
∃ c : ℝ, 0 < c ∧ ∃ N₀ : ℕ,
∀ ε : ℕ → ℝ, (∀ N, 1 < N → Even N → 0 < ε N ∧ ε N < 1 / 3) →
∀ N, 1 < N → Even N → N₀ ≤ N →
∀ P : Protocol (Equiv.Perm (Fin (N / 2))) (Equiv.Perm (Fin (N / 2))) Bool Bool,
startsWith P true →
solves P (fun _ _ ↦ True) (fun a b ↦ decide (NondetConn.bConn (N / 2) a b)) (ε N) →
c * (N : ℝ) * Real.logb 2 (min (1 / ε N) (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 5.1, p.14 (PDF p.16)