Lemma 5.4 — Assouad’s lemma
OpenQuantumLTF.Example.lemma_5_4assouad-lemmalower-boundssection-5statistics
Let be the output distribution of an estimator when the hidden string is . If neighboring hidden strings induce output distributions of total-variation distance at most , then for uniform ,
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Example_LowerModel
Formal statement
namespace QuantumLTF.Example
theorem lemma_5_4 :
∀ m : ℕ, 1 ≤ m → ∀ α : ℝ, 0 ≤ α → α ≤ 1 →
∀ P : SignString m → PMF (SignString m),
(∀ z i, pmfTV (P z) (P (Function.update z i (!(z i)))) ≤ α) →
(1 / (2 : ℝ) ^ m) * ∑ z : SignString m, ∑ zh : SignString m,
(P z zh).toReal * hamming z zh ≥ (m : ℝ) / 2 * (1 - α) := by sorry
end QuantumLTF.ExampleSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, STOC 2027 submission #347, Lemma 5.4, p. 75 (PDF p. 76).