boofun.families.theoretical

Theoretical bounds and asymptotic formulas for Boolean function properties.

This module provides known theoretical results that can be compared against computed values to validate understanding and implementation.

Classes

TheoreticalBounds()

Collection of theoretical bounds and asymptotic formulas.

class boofun.families.theoretical.TheoreticalBounds

Collection of theoretical bounds and asymptotic formulas.

These are from O’Donnell’s book and other sources.

static majority_total_influence(n: int) → float

Total influence of Majority_n.

I[MAJ_n] = √(2/π) · √n + O(1/√n)

static parity_total_influence(n: int) → float

Total influence of Parity_n = n.

static and_total_influence(n: int) → float

Total influence of AND_n = n · 2^{-(n-1)}.

static tribes_total_influence(n: int, w: int | None = None) → float

Total influence of Tribes.

For standard balanced Tribes: I[TRIBES_n] ≈ log(n)

static majority_noise_stability(rho: float) → float

Noise stability of Majority (Sheppard’s formula).

Stab_ρ[MAJ_n] → (1/2) + (1/π)·arcsin(ρ) as n → ∞

static parity_noise_stability(n: int, rho: float) → float

Noise stability of Parity.

Stab_ρ[XOR_n] = ρ^n → 0 for ρ < 1

static dictator_noise_stability(rho: float) → float

Noise stability of Dictator.

Stab_ρ[DICT] = ρ

static and_noise_stability(n: int, rho: float) → float

Noise stability of AND.

Stab_ρ[AND_n] = Pr[AND(x) = AND(y)] where y = ρ-correlated with x

static majority_influence_i(n: int, i: int = 0) → float

Influence of variable i in Majority_n.

By symmetry: Inf_i[MAJ_n] = √(2/(πn)) for all i

static parity_influence_i(n: int, i: int = 0) → float

Each variable has influence 1 in Parity.

static and_influence_i(n: int, i: int = 0) → float

Influence of each variable in AND_n = 2^{-(n-1)}.

static poincare_lower_bound(variance: float) → float

Poincaré inequality: Var[f] ≤ I[f]

So I[f] ≥ Var[f]

static kkl_lower_bound(n: int, variance: float) → float

KKL Theorem: max_i Inf_i[f] ≥ Var[f] · c·log(n)/n

For balanced f: max Inf_i ≥ Ω(log(n)/n)

static friedgut_junta_bound(total_influence: float, epsilon: float) → float

Friedgut’s Junta Theorem.

If I[f] ≤ k, then f is ε-close to a 2^{O(k/ε)}-junta.

Returns the junta size bound.

static decision_tree_fourier_support(depth: int) → int

Decision tree of depth d has at most 4^d non-zero Fourier coefficients.

static decision_tree_spectral_norm(size: int) → float

Decision tree of size s has Σ|f̂(S)| ≤ s.

static mansour_spectral_concentration(depth: int, epsilon: float) → int

Mansour’s Theorem: DNF of depth d has (1-ε) of Fourier weight on O(1/ε^2 · 2^{O(d)}) coefficients.

static ltf_total_influence(n: int, regularity: float = 0.0) → float

Total influence of an LTF.

For regular LTFs (τ small): I[f] ≈ √(2/π)·√n For irregular (τ → 1): I[f] → 1

static ltf_noise_stability(rho: float, regularity: float = 0.0) → float

Noise stability of LTF.

Regular LTFs: Stab_ρ → (1/2) + (1/π)arcsin(ρ) Dictator (τ=1): Stab_ρ = ρ

static sensitivity_vs_block_sensitivity(s: float) → float

Sensitivity Theorem (Huang 2019): bs(f) ≤ s(f)^4

Returns upper bound on block sensitivity.

static certificate_vs_sensitivity(s: float) → float

C(f) ≤ s(f) · bs(f) ≤ s(f)^5

static degree_vs_sensitivity(s: float) → float

deg(f) ≤ s(f)^2 (from Sensitivity Theorem)

classmethod get_bounds_for_family(family_name: str) → Dict[str, Callable]

Get all applicable theoretical bounds for a named family.

Returns dictionary of {property_name: bound_function}