Theorem 4.3 — matching delay across the source threshold
OpenCorrelatedLocalSearch.Supplement.theorem_4_3local-searchp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytheoretical-computer-scienceweak-random-sources
There are positive constants such that for every , and , some complete formula has a nonsatisfying initial assignment at distance from its unique all-one strong witness and one source satisfying, simultaneously for every selector,
with .
Differences from the source:
- encoding: → one positive constant quantified before all instances; reason: expands the uniform asymptotic bound
- encoding: → the second branch of is in ENNReal at ; reason: exact extended-value convention
- encoding: the almost-sure delay compares a possibly infinite stopping time with a nonnegative bound →
\mathbb N\cup\{\infty\}andENNReal; reason: exact extended-nonnegative encoding
Preamble
import Mathlib import Definitions.Def_CorrelatedLocalSearch_Supplement_SAT set_option autoImplicit false
Formal statement
namespace CorrelatedLocalSearch.Supplement
open MeasureTheory
open scoped ENNReal BigOperators
/-- Xu, arXiv:2607.17469 (sha256 17e00d69…), Theorem 4.3, p.11 (PDF p.13).
A single admissible source forces the full cubic-to-linear delay almost surely, simultaneously for
every selector, on a complete formula whose size has matching order. -/
theorem theorem_4_3 (k r : Nat) (hk : k < 2 * r) (hr : r < k) :
∃ c C : Real, 0 < c ∧ 0 < C ∧
∀ s, CorrelatedLocalSearch.sStar k r ≤ s -> s ≤ 1 ->
∀ h : Nat, r ≤ h -> ∀ D : Real, 1 ≤ D ->
∃ (n : Nat) (x0 : Fin n -> Bool) (nu : Measure (Nat -> Fin k)),
¬ CorrelatedLocalSearch.Satisfies (completeFormula k r n) x0 ∧
hammingDist x0 (allOneAssignment n) = h ∧
CorrelatedLocalSearch.IsStrongWitness r (completeFormula k r n) (allOneAssignment n) ∧
(∀ xs, CorrelatedLocalSearch.IsStrongWitness r (completeFormula k r n) xs ->
xs = allOneAssignment n) ∧
nu ∈ CorrelatedLocalSearch.SourceClass k s D ∧
(∀ sel, CorrelatedLocalSearch.IsValidSelector (completeFormula k r n) sel ->
nu {omega | ENNReal.ofReal c *
Psi k r s ((h : Real) + Real.log D + 1) ≤
((CorrelatedLocalSearch.walkTau (completeFormula k r n) sel x0 omega : ℕ∞) : ENNReal)} = 1) ∧
(n : Real) ≤ C * (Psi k r s ((h : Real) + Real.log D + 1)).toReal := by sorry
end CorrelatedLocalSearch.Supplement
Source
Xu, Local Search with Correlated Randomness, arXiv:2607.17469 (sha256 17e00d69…), Theorem 4.3, p.11 (PDF p.13)