boofun.analysis

Boolean function analysis module providing spectral analysis tools.

This module implements fundamental algorithms for analyzing Boolean functions including Fourier analysis, influence computation, and noise stability.

Classes

PropertyTester(function[, random_seed])	Property testing algorithms for Boolean functions.
SpectralAnalyzer(function)	Spectral analysis tools for Boolean functions.

class boofun.analysis.SpectralAnalyzer(function: BooleanFunction)

Spectral analysis tools for Boolean functions.

Provides methods for computing Fourier coefficients, variable influences, total influence, noise stability, and other spectral properties.

__init__(function: BooleanFunction)

Initialize analyzer with a Boolean function.

Parameters:

function – BooleanFunction instance to analyze

fourier_expansion(force_recompute: bool = False) → ndarray

Compute Fourier expansion coefficients.

The Fourier expansion represents f: {0,1}^n → {0,1} as: f(x) = Σ_S f̂(S) * χ_S(x) where χ_S(x) = (-1)^(Σ_{i∈S} x_i) are the Walsh functions.

Parameters:

force_recompute – If True, recompute even if cached

Returns:

Array of Fourier coefficients indexed by subsets

influences(force_recompute: bool = False) → ndarray

Compute variable influences (also called sensitivities).

The influence of variable i is: Inf_i(f) = Pr[f(x) ≠ f(x ⊕ e_i)] where e_i is the i-th unit vector.

Parameters:

force_recompute – If True, recompute even if cached

Returns:

Array of influences for each variable

total_influence() → float

Compute total influence (sum of all variable influences).

Returns:

Total influence = Σ_i Inf_i(f)

noise_stability(rho: float) → float

Compute noise stability at correlation ρ.

Noise stability is the probability that f(x) = f(y) where y is obtained from x by flipping each bit independently with probability (1-ρ)/2.

Parameters:

rho – Correlation parameter in [-1, 1]

Returns:

Noise stability value

spectral_concentration(degree: int) → float

Compute spectral concentration at given degree.

This is the fraction of Fourier weight on coefficients corresponding to sets of size at most ‘degree’.

Parameters:

degree – Maximum subset size to include

Returns:

Fraction of spectral weight on low-degree coefficients

get_fourier_coefficient(subset: int | List[int]) → float

Get Fourier coefficient for a specific subset.

Parameters:

subset – Either integer index or list of variable indices

Returns:

Fourier coefficient for the subset

summary() → Dict[str, Any]

Compute summary statistics for the Boolean function.

Returns:

Dictionary with various spectral properties and confidence information

class boofun.analysis.PropertyTester(function: BooleanFunction, random_seed: int | None = None)

Property testing algorithms for Boolean functions.

Implements various randomized and deterministic tests to check if Boolean functions satisfy specific properties.

__init__(function: BooleanFunction, random_seed: int | None = None)

constant_test() → bool

Test if function is constant.

Deterministic test that checks if all outputs are identical. Time complexity: O(2^n) for exhaustive check.

Returns:

True if function is constant, False otherwise

blr_linearity_test(num_queries: int = 100, epsilon: float = 0.1) → bool

BLR (Blum-Luby-Rubinfeld) linearity test.

Tests if a function f: {0,1}^n → {0,1} is linear (i.e., f(x ⊕ y) = f(x) ⊕ f(y)). Uses randomized queries to test the linearity property.

QUERY COMPLEXITY: O(3 * num_queries) - safe for arbitrarily large n.

Parameters:

• num_queries – Number of random queries to perform

• epsilon – Error tolerance (function passes if error rate < epsilon)

Returns:

True if function appears linear, False otherwise

junta_test(k: int, num_queries: int = 1000, confidence: float = 0.9) → bool

Test if function is a k-junta (depends on at most k variables).

A function is a k-junta if there exists a set S ⊆ [n] with |S| ≤ k such that f(x) depends only on coordinates in S.

Parameters:

• k – Maximum number of relevant variables

• num_queries – Number of random queries

• confidence – Confidence level for the test

Returns:

True if function appears to be a k-junta, False otherwise

monotonicity_test(num_queries: int = 1000) → bool

Test if function is monotone (f(x) ≤ f(y) whenever x ≤ y coordinate-wise).

QUERY COMPLEXITY: O(2 * num_queries) - safe for arbitrarily large n.

Parameters:

num_queries – Number of random pairs to test

Returns:

True if function appears monotone, False otherwise

unateness_test(num_queries: int = 1000) → bool

Test if function is unate (monotone in each variable, possibly negated).

A function is unate if for each variable x_i, either: - f is monotone increasing in x_i, OR - f is monotone decreasing in x_i

Unate functions generalize monotone functions - they can be monotone in different “directions” for different variables.

QUERY COMPLEXITY: O(2 * num_queries) - safe for arbitrarily large n.

Parameters:

num_queries – Number of random pairs to test per variable

Returns:

True if function appears unate, False otherwise

symmetry_test(num_queries: int = 1000) → bool

Test if function is symmetric (invariant under permutations of variables).

QUERY COMPLEXITY: O(2 * num_queries) - safe for arbitrarily large n.

Parameters:

num_queries – Number of random permutations to test

Returns:

True if function appears symmetric, False otherwise

balanced_test() → bool

Test if function is balanced (outputs 0 and 1 equally often).

Returns:

True if function is balanced, False otherwise

dictator_test(num_queries: int = 1000, epsilon: float = 0.1) → Tuple[bool, int | None]

Test if function is a dictator or anti-dictator.

A dictator function is f(x) = x_i for some i. An anti-dictator is f(x) = ¬x_i = 1 - x_i.

From O’Donnell Chapter 7: The FKN theorem states that if f is Boolean and has small total influence, it’s close to a dictator.

Parameters:

• num_queries – Number of random queries

• epsilon – Distance threshold

Returns:

• is_dictator_like: True if f is close to a dictator/anti-dictator

• dictator_index: The index of the dictator variable (or None)

Return type:

Tuple of (is_dictator_like, dictator_index) where

affine_test(num_queries: int = 1000, epsilon: float = 0.1) → bool

4-query test for affine functions over GF(2).

From HW1 Problem 4: A function f: F_2^n → F_2 is affine iff f(x) + f(y) + f(z) = f(x + y + z) for all x, y, z.

This is a generalization of the BLR linearity test.

Parameters:

• num_queries – Number of random queries

• epsilon – Error tolerance

Returns:

True if function appears to be affine

run_all_tests() → Dict[str, Any]

Run all available property tests.

Returns:

Dictionary mapping test names to results

Modules

arrow	Arrow's Impossibility Theorem and Social Choice Theory.
basic_properties	Basic properties of Boolean functions.
block_sensitivity	Block sensitivity analysis for Boolean functions.
canalization	Canalization Analysis for Boolean Functions.
certificates	Certificate utilities (exact search for modest n).
communication_complexity	Communication Complexity Analysis.
complexity	Complexity measures for Boolean functions.
equivalence	Equivalence testing and canonical forms for Boolean functions.
fkn	FKN Theorem and related results about functions close to dictators.
fourier	Fourier analysis utilities for Boolean functions.
gaussian	Gaussian analysis of Boolean functions (O'Donnell Chapter 10).
gf2	GF(2) analysis for Boolean functions (XOR/Algebraic Normal Form).
global_hypercontractivity	Global Hypercontractivity Module
huang	Huang's Sensitivity Theorem and related results.
hypercontractivity	Hypercontractivity tools for Boolean function analysis.
invariance	Invariance principles for Boolean functions (O'Donnell Chapter 11).
learning	Learning algorithms for Boolean functions.
ltf_analysis	Linear Threshold Function (LTF) Analysis Module.
p_biased	P-biased Fourier analysis for Boolean functions.
pac_learning	PAC (Probably Approximately Correct) Learning for Boolean functions.
query_complexity	Query complexity measures for Boolean functions.
restrictions	Random restrictions for Boolean function analysis.
sensitivity	Sensitivity-related helpers ported from legacy routines.
symmetry	Symmetry helpers informed by Krawchouk polynomials.