Two-point Boolean fibers and bias-matched shift error
DefinitionNarrowDNF_FiberShiftcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
A Boolean fiber is an ordered pair , giving a function's values when one coordinate is zero and one. For Boolean values , let be zero when they agree and one when they differ. Given target fiber , approximation fiber , and bias , the conditional disagreement error is
For this is the error under a Bernoulli- input on the fiber.
The upper shift sends to , and the lower shift sends it to . Thus the decreasing fiber becomes under the upper choice and under the lower choice. These explicit two-point quantities underlie the later randomized calculation that chooses the upper shift with probability and the lower shift with probability . Passing from a fiber calculation to a full cube is a separate finite-sum argument.
Definition code
import Mathlib.Data.Real.Basic import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring namespace NarrowDNF.FiberShift end NarrowDNF.FiberShift /-! # Bias-matched shifts on a Boolean fiber This file proves the two-point calculation used in Lemma 3.1 of the 2026-11-06 STOC revision. The probability of the upper shift is `1 - p` and the probability of the lower shift is `p`; the input fiber has the same bias `p`. The error theorem is a conditional, single-fiber statement. Passing to an arbitrary Boolean cube requires a separate summation/integration argument. -/ namespace NarrowDNF.FiberShift /-- Values at the lower and upper endpoints of one coordinate fiber. -/ abbrev Fiber := Bool × Bool /-- The real-valued indicator that two Boolean values disagree. -/ def mismatch (a b : Bool) : ℝ := if a = b then 0 else 1 /-- Conditional error on one fiber under a `p`-biased input. -/ def error (p : ℝ) (f v : Fiber) : ℝ := (1 - p) * mismatch f.1 v.1 + p * mismatch f.2 v.2 /-- The upper shift changes the decreasing fiber `10` to `11`. -/ def upper (v : Fiber) : Fiber := (v.1, v.1 || v.2) /-- The lower shift changes the decreasing fiber `10` to `00`. -/ def lower (v : Fiber) : Fiber := (v.1 && v.2, v.2) end NarrowDNF.FiberShift
Source