boofun.analysis.sparsity

Fourier sparsity analysis for Boolean functions.

This module provides functions for analyzing the Fourier sparsity of Boolean functions - the number and structure of non-zero Fourier coefficients.

Fourier sparsity is important for: - Learning algorithms (sparse functions are easier to learn) - Circuit complexity (sparsity bounds imply circuit bounds) - Approximate degree bounds

Key concepts: - sparsity(f): Number of non-zero Fourier coefficients |{S : f̂(S) ≠ 0}| - granularity(f): GCD structure of Fourier coefficients - sparsity_up_to_constants(f): Sparsity ignoring constant multiples

Bounds: - If deg(f) = d, then sparsity(f) ≤ 4^d (Nisan-Szegedy style) - If sparsity(f) = k, then deg(f) ≤ k

References: - O’Donnell HW1 Problem 7 - Tal’s BooleanFunc.py (sparsity, sparsity_upto_constants) - Gopalan et al., “Sparsity and Fourier Analysis” (2011)

Functions

effective_sparsity(f[, weight_threshold])

Compute effective sparsity based on Fourier weight concentration.

fourier_sparsity(f[, threshold])

Count the number of non-zero Fourier coefficients.

fourier_sparsity_up_to_constants(f[, threshold])

Compute Fourier sparsity ignoring constant multiples.

fourier_support(f[, threshold])

Return the support of the Fourier spectrum.

granularity(f[, threshold])

Analyze the granularity structure of Fourier coefficients.

sparsity_by_degree(f[, threshold])

Count non-zero Fourier coefficients at each degree.
boofun.analysis.sparsity.fourier_sparsity(f: BooleanFunction, threshold: float = 1e-10) → int[source]

Count the number of non-zero Fourier coefficients.

The Fourier sparsity is:

sparsity(f) = |{S : |f̂(S)| > threshold}|

For any Boolean function f of degree d:

sparsity(f) ≤ 4^d (Nisan-Szegedy style bound)

Parameters:

  • f – BooleanFunction to analyze

  • threshold – Minimum magnitude to count as non-zero

Returns:

Number of non-zero Fourier coefficients

References

  • Tal’s BooleanFunc.py: sparsity

  • O’Donnell HW1 Problem 7

boofun.analysis.sparsity.fourier_sparsity_up_to_constants(f: BooleanFunction, threshold: float = 1e-10) → int[source]

Compute Fourier sparsity ignoring constant multiples.

This counts the number of distinct non-trivial Fourier coefficient values, where “trivial” means 0 or ±f̂(∅). This measure captures the “essential” complexity of the Fourier spectrum.

Specifically, counts:

|{S : f̂(S) ≠ 0 and f̂(S) ∉ {0, f̂(∅), -f̂(∅)}}|

This is Tal’s sparsity_upto_constants function.

Parameters:

  • f – BooleanFunction to analyze

  • threshold – Minimum magnitude for non-zero

Returns:

Effective sparsity ignoring constants

References

  • Tal’s BooleanFunc.py: sparsity_upto_constants

boofun.analysis.sparsity.granularity(f: BooleanFunction, threshold: float = 1e-10) → Dict[float, int][source]

Analyze the granularity structure of Fourier coefficients.

Returns a count of how many times each distinct coefficient value appears. This reveals patterns in the Fourier spectrum, e.g., all coefficients being powers of 1/2.

Parameters:

  • f – BooleanFunction to analyze

  • threshold – Precision for rounding coefficients

Returns:

Dictionary mapping coefficient values to their counts

boofun.analysis.sparsity.fourier_support(f: BooleanFunction, threshold: float = 1e-10) → List[int][source]

Return the support of the Fourier spectrum.

The support is the set of subsets S where f̂(S) ≠ 0.

Parameters:

  • f – BooleanFunction to analyze

  • threshold – Minimum magnitude for non-zero

Returns:

List of subset masks where f̂(S) ≠ 0, sorted by |S| then by value

boofun.analysis.sparsity.sparsity_by_degree(f: BooleanFunction, threshold: float = 1e-10) → Dict[int, int][source]

Count non-zero Fourier coefficients at each degree.

Returns a dictionary where result[d] = |{S : |S| = d and f̂(S) ≠ 0}|.

Parameters:

  • f – BooleanFunction to analyze

  • threshold – Minimum magnitude for non-zero

Returns:

Dictionary mapping degree to count of non-zero coefficients at that degree

boofun.analysis.sparsity.effective_sparsity(f: BooleanFunction, weight_threshold: float = 0.01) → Tuple[int, float][source]

Compute effective sparsity based on Fourier weight concentration.

Returns the number of coefficients needed to capture (1 - weight_threshold) of the total Fourier weight.

This is useful because many functions have most of their weight concentrated on a small number of coefficients.

Parameters:

  • f – BooleanFunction to analyze

  • weight_threshold – Fraction of weight to allow outside the effective support

Returns:

Tuple of (effective_sparsity, weight_captured) - effective_sparsity: minimum k such that top-k coefficients have weight ≥ 1 - threshold - weight_captured: actual fraction of weight captured