Theorem 2.1, p. 8 — if D(P‖Q)/α = o(log n/n) with α bounded below, every algorithm has ℙ[β(π̂, π*) < α] → 1
ProvedGraphAlignment.Impossible.theorem_2_1For every let be generated by the correlated Erdős–Rényi model with and with drawn uniformly from the permutations. Let , possibly depending on but bounded below: there is with for all large . If
with the edge-pair laws (3)–(4) at , then for any sequence of algorithms inferring from and ,
In other words, no learning algorithm can infer a permutation that overlaps with on more than a fraction of the vertices with probability bounded away from zero.
This is the paper's impossibility result: it identifies a regime of the correlated Erdős–Rényi model in which even partial recovery of the planted alignment is information-theoretically impossible.
Formalization Note The page allows any "possibly dependent on "; as printed the statement fails for fast (with , , the hypothesis holds but the identity algorithm succeeds with probability tending to ). The hypothesis that is eventually bounded below by a constant is added; a constant is the special case. Algorithms are arbitrary stochastic kernels from the observed pair to permutations, one for each , and see neither nor the hidden graph . The little- hypothesis is the convergence of to ; natural logarithm.
import Mathlib import Definitions.Def_GraphAlignment_Impossible_Setting
namespace GraphAlignment.Impossible
open Filter Topology
theorem theorem_2_1 (q s α : ℕ → ℝ)
(hq : ∀ n, 0 ≤ q n) (hqs : ∀ n, q n < s n) (hs : ∀ n, s n ≤ 1)
(hα : ∀ n, 0 < α n ∧ α n < 1) (hαc : ∃ c : ℝ, 0 < c ∧ ∀ᶠ n in atTop, c ≤ α n)
(hD : Tendsto (fun n : ℕ => klPQ (q n) (s n) / α n / (Real.log n / n)) atTop (𝓝 0))
(alg : ∀ n, Alg n) :
Tendsto (fun n => failProb (q n) (s n) (α n) (alg n)) atTop (𝓝 1) := by sorry
end GraphAlignment.Impossible
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.