BoolBLR.BLR_accept_prob
defimported Lean
The BLR acceptance probability of $f : \{0,1\}^n \to \{0,1\}$ is \[ \Pr_{x,y}[\text{BLR accepts}] \;=\; \E_{x}\!\left[\E_{y}\!\left[ \mathbf{1}\!\left[ \texttt{BoolBLR.lift\_pm1}\,f(x \oplus y) = \texttt{BoolBLR.lift\_pm1}\,f(x)\cdot\texttt{BoolBLR.lift\_pm1}\,f(y) \right] \right]\right], \] where $x, y$ are drawn uniformly from $\{0,1\}^n$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in noncomputable def BoolBLR.BLR_accept_prob {n : ℕ} (f : hypercube n → Bool) : ℝ
- Defined in
- TCSlib, `BoolBLR.BLR_accept_prob`
- Lean proof
- By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Prastik Mohanraj. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.BoolBLR.BLR_accept_prob← BoolBLR.BLR_accept_prob (TCSlib/BooleanAnalysis/BLR/BoolBLR.lean:177): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 4
- BoolFourier.expectationFor $f : \{0,1\}^n \to \mathbb{R}$, the uniform expectation is \[ \mathbb{E}[f] = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} f(x). \]
- BoolFourier.xor_vecFor $x, y \in \{0,1\}^n$, the vector $\mathrm{xor\_vec}(x,y)_i = x_i \oplus y_i$ is the componentwise XOR, giving the group operation on…
- BoolFourier.hypercubeThe Boolean hypercube of dimension $n$ is the type $\{0,1\}^n$, defined as an abbreviation for
BooleanAnalysis.BoolCube$n$. - BoolBLR.lift_pm1Given $f : \{0,1\}^n \to \{0,1\}$, its $\pm 1$ lift $\texttt{BoolBLR.lift\_pm1}\,f : \{0,1\}^n \to \mathbb{R}$ is defined by…
- Used by 3
- BoolBLR.BLR_completenessCompleteness of the BLR linearity test. Let $n$ be a natural number and let $f : \{0,1\}^n \to \{0,1\}$ be linear, meaning that…
- BoolBLR.BLR_soundnessSoundness of the BLR linearity test. Let $f : \{0,1\}^n \to \{0,1\}$ and let $\varepsilon \in \bbr$ satisfy $0 \le \varepsilon \le 1$.…
- BoolBLR.BLR_accept_prob_pm1BLR acceptance probability in ±1 form. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean-valued function, and write…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BoolFourier in /-- Defines the acceptance probability of the Boolean BLR linearity test. **Source:** [OD14, §1.6]. -/ noncomputable def BoolBLR.BLR_accept_prob {n : ℕ} (f : hypercube n → Bool) : ℝ := expectation (fun x => expectation (fun y => if lift_pm1 f (xor_vec x y) = lift_pm1 f x * lift_pm1 f y then 1 else 0)) -- Pr [ BLR accepts f ] = ( 1 + E [ E [ f(x) f(y) f(x + y) ] ] ) / 2