The deterministic XOR source reduction #
At each outer coordinate, XOR the correlation-breaker bits obtained from all sampler candidates. The sampler and correlation breaker read the same original input. This is the actual reduction in Chattopadhyay--Liao, Extractors for Sum of Two Sources, Lemma 5.4: https://arxiv.org/abs/2110.12652.
The definition imposes no statistical premise. Those premises belong to the bad-seed and parity theorems for its component calls.
def
Algebraic.Cutwidth.Extractor.affineSourceReduction
{n N C : ℕ}
{Seed : Type u_1}
{Advice : Type u_2}
(cb : (Fin n → Bool) → Seed → Advice → Bool)
(sampler : (Fin n → Bool) → Fin N → Fin C → Seed)
(advice : Fin N → Fin C → Advice)
(x : Fin n → Bool)
(i : Fin N)
:
XOR all candidate outputs at each outer sampler coordinate.
Equations
- Algebraic.Cutwidth.Extractor.affineSourceReduction cb sampler advice x i = Complexity.Schnorr.xorBool C fun (z : Fin C) => cb x (sampler x i z) (advice i z)