boofun.analysis.huang

Huang’s Sensitivity Theorem and related results.

Huang’s Theorem (2019): For any Boolean function f: {0,1}^n → {0,1},: s(f) ≥ √deg(f)

where s(f) is the sensitivity and deg(f) is the Fourier degree.

This resolved the long-standing Sensitivity Conjecture, proving that sensitivity is polynomially related to all other complexity measures.

Key relationships established: - bs(f) ≤ s(f)^2 (block sensitivity) - D(f) ≤ s(f)^4 (deterministic query complexity) - C(f) ≤ s(f)^2 (certificate complexity) - deg(f) ≤ s(f)^2 (Fourier degree)

References: - Huang, “Induced subgraphs of hypercubes and a proof of the

Sensitivity Conjecture” (2019)

O’Donnell, “Analysis of Boolean Functions” Chapter 2

Functions

`average_sensitivity`(f)	Compute average sensitivity: E_x[s(f, x)].
`block_sensitivity`(f)	Compute block sensitivity: bs(f) = max_x bs(f, x).
`max_sensitivity`(f)	Compute maximum sensitivity: s(f) = max_x s(f, x).
`sensitivity`(f)	Alias for max_sensitivity.
`sensitivity_at`(f, x)	Compute sensitivity of f at input x.
`sensitivity_vs_degree`(f)	Compare sensitivity and degree for Huang analysis.
`verify_huang_theorem`(f)	Verify Huang's Sensitivity Theorem for function f.

Classes

HuangAnalysis(f)

Comprehensive sensitivity analysis with Huang's theorem.

boofun.analysis.huang.sensitivity(f: BooleanFunction) → int[source]: Alias for max_sensitivity.

boofun.analysis.huang.sensitivity_at(f: BooleanFunction, x: int) → int[source]

Compute sensitivity of f at input x.

s(f, x) = |{i : f(x) ≠ f(x ⊕ eᵢ)}|

The number of bits that, if flipped, change the output.

Parameters:

f – Boolean function
x – Input (as integer)

Returns:

Number of sensitive coordinates at x

boofun.analysis.huang.max_sensitivity(f: BooleanFunction) → int[source]

Compute maximum sensitivity: s(f) = max_x s(f, x).

Also called just “sensitivity” of f.

Parameters:: f – Boolean function
Returns:: Maximum sensitivity over all inputs

boofun.analysis.huang.average_sensitivity(f: BooleanFunction) → float[source]

Compute average sensitivity: E_x[s(f, x)].

This equals the total influence I[f].

Parameters:: f – Boolean function
Returns:: Average sensitivity

boofun.analysis.huang.block_sensitivity(f: BooleanFunction) → int[source]

Compute block sensitivity: bs(f) = max_x bs(f, x).

bs(f, x) is the maximum number of disjoint blocks B₁, …, Bₖ such that flipping all bits in any Bᵢ changes f(x).

Huang showed: bs(f) ≤ s(f)²

Parameters:: f – Boolean function
Returns:: Block sensitivity

boofun.analysis.huang.verify_huang_theorem(f: BooleanFunction) → Dict[str, Any][source]

Verify Huang’s Sensitivity Theorem for function f.

Checks: s(f) ≥ √deg(f)

Returns:: Dict with sensitivity, degree, and verification result

boofun.analysis.huang.sensitivity_vs_degree(f: BooleanFunction) → Tuple[int, int, float][source]

Compare sensitivity and degree for Huang analysis.

Returns:: (sensitivity, degree, ratio s/√deg)

class boofun.analysis.huang.HuangAnalysis(f: BooleanFunction)[source]

Comprehensive sensitivity analysis with Huang’s theorem.

Computes various sensitivity-related measures and verifies the polynomial relationships established by Huang.

__init__(f: BooleanFunction)[source]: Initialize analyzer with a Boolean function.

sensitivity() → int[source]: Get maximum sensitivity.

block_sensitivity() → int[source]: Get block sensitivity.

degree() → int[source]: Get Fourier degree.

sensitivity_profile() → ndarray[source]: Get sensitivity at each input.

verify_all_bounds() → Dict[str, Any][source]

Verify all Huang-related polynomial bounds.

Checks: - s(f) ≥ √deg(f) [Huang] - bs(f) ≤ s(f)² - C(f) ≤ s(f)² - D(f) ≤ s(f)⁴

summary() → str[source]: Get a text summary of the analysis.