Theorem 3 — XOR lemma with circuit loss
OpenRevisitXor.Supplement.theorem_3boolean-functionscircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1xor-lemma
There are positive absolute constants , , and with the following property. Let , let be a fan-in-two Boolean circuit over the full binary basis with exactly gates, and let . If
then there is a circuit satisfying
The theorem improves the dependence of the circuit-size loss in this two-copy-to-one-copy XOR lemma to the square-root scale in .
Formalization Note The real power is Real.rpow. Sign-valued functions are represented by their bit exponents in , and the 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: the three printed occurrences of the possibly different absolute constant → separate constants , , and , each quantified before all problem data; reason: the paper's p.1 convention says every occurrence of may denote a different positive absolute constant
- encoding: “for all ” after expressions containing and → with the power interpreted by
Real.rpow; reason: positivity is the ordinary implicit domain of the printed expressions - encoding: sign-valued functions, uniform expectations, and a circuit on two copies → 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
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 3 (power amplification with square-root circuit loss).** Viola, *Revisiting the
XOR lemma*, STOC 2027 submission (manuscript of August 25, 2026, sha256 3b49e10d…716),
Theorem 3, pp.3–4.
There are positive absolute constants such that, for every sufficiently small positive `ε`,
a size-`s` circuit with two-copy correlation at least `ε` yields a circuit of size at most
`c_size · sqrt (1/ε) · s` and one-copy correlation at least `ε^(1-c_power)`.
**Formalization Note.** The paper states that each occurrence of `c` may denote a different
positive absolute constant. Accordingly `cSize`, `cPower`, and `cRange` are separate and are
quantified before `n`, `f`, `C`, and `ε`. Positivity of `ε` is the implicit domain condition of
the printed `sqrt (1/ε)` and real power. The sign/bit encoding, uniform correlations, two-block
input indexing, and concrete `B₂` circuit model are the same as in Theorem 2. -/
theorem theorem_3 :
∃ cSize cPower cRange : ℝ, 0 < cSize ∧ 0 < cPower ∧ 0 < cRange ∧
∀ (n s : ℕ) (f : Cube n → ZMod 2) (C : AffDisp4n.Acyclic (Fin 2 × Fin n))
(ε : ℝ), C.size = s → 0 < ε → ε ≤ cRange →
ε ≤ 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 : ℝ) ≤ cSize * Real.sqrt (1 / ε) * (s : ℝ) ∧
Real.rpow ε (1 - cPower) ≤ 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 3, p.3 (proof continues p.4; PDF pp.3–4)