Theorem 5 — XOR lemma with quadratic loss in
OpenRevisitXor.Supplement.theorem_5boolean-functionscircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1xor-lemma
There is a positive absolute constant with the following property. Let , let , and let be a fan-in-two Boolean circuit over the full binary basis of size at most . If
then there is a circuit such that
This is the paper's quadratic-loss alternative proof of the XOR lemma; it retains both the factor in the hypothesis and the strict correlation improvement in the conclusion.
Formalization Note Real.log is the natural logarithm. Sign-valued functions are represented by their bit exponents in , and both displayed expectations are RevisitXor.corr. The two input blocks use , and circuits use the published full-basis syntax with gate-count size.
Differences from the source:
- encoding: sign-valued functions, uniform expectations, and a circuit on → bit-valued functions,
RevisitXor.corr, and a full-basis circuit indexed by ; reason: the sign/bit and two-block identifications preserve the functions, expectations, and gate count - encoding: with unspecified base →
Real.log (1 / ε), the natural logarithm; reason: changing the logarithm base only rescales the existential positive absolute constant
Preamble
import Mathlib import Definitions.Def_RevisitXor_corr import Definitions.Def_AffDisp4n_Circuit import Definitions.Def_AffDisp4n_Acyclic_eval set_option autoImplicit false
Formal statement
namespace RevisitXor
namespace Supplement
/-- **Theorem 5 (quadratic-loss XOR lemma).** Viola, *Revisiting the XOR lemma*, STOC 2027
submission (manuscript of August 25, 2026, sha256 3b49e10d…716), Theorem 5, pp.4–5.
There is a positive absolute constant `c` such that, for `0 < ε ≤ 1/2`, a circuit of size
at most `s` with two-copy correlation at least `3ε²` yields a one-copy circuit of size at
most `c · ε⁻² · log(1/ε) · s` whose correlation is strictly greater than `ε`.
**Formalization Note.** `Real.log` is the natural logarithm; changing the logarithm base only
rescales the existential absolute constant. The paper's sign-valued functions are represented
by their bit exponents in `ZMod 2`, so both displayed expectations are the published signed
uniform `corr`. The two blocks of the input circuit are indexed by `Fin 2 × Fin n`, and sizes
are gate counts in the published full-basis `B₂` circuit syntax. -/
theorem theorem_5 :
∃ c : ℝ, 0 < c ∧
∀ (n s : ℕ) (ε : ℝ) (f : Cube n → ZMod 2)
(C : AffDisp4n.Acyclic (Fin 2 × Fin n)),
0 < ε → ε ≤ 1 / 2 → C.size ≤ s →
3 * ε ^ 2 ≤ corr
(fun xy : Cube n × Cube n ↦
C.eval (fun ji ↦ if ji.1 = 0 then xy.1 ji.2 else xy.2 ji.2))
(fun xy ↦ f xy.1 + f xy.2) →
∃ C' : AffDisp4n.Circuit n,
(C'.size : ℝ) ≤ c * (ε⁻¹) ^ 2 * Real.log (1 / ε) * (s : ℝ) ∧
ε < corr C'.eval f := by sorry
end Supplement
end RevisitXor
Source
Viola, Revisiting the XOR lemma, STOC 2027 submission (manuscript of August 25, 2026, sha256 3b49e10d…716), Theorem 5, p.4, proof p.5 (PDF pp.4–5)