boofun.analysis.sensitivity
Sensitivity analysis for Boolean functions.
This module provides sensitivity-related functions for analyzing Boolean functions, including pointwise sensitivity, average sensitivity, and higher moments.
Sensitivity measures how “locally” a function changes: s(f, x) counts how many single-bit flips of x change the output of f. This is fundamental to understanding the complexity and structure of Boolean functions.
Key concepts: - s(f, x): Sensitivity at input x = |{i : f(x) ≠ f(x^i)}| - s(f): Maximum sensitivity = max_x s(f, x) - as(f): Average sensitivity = E_x[s(f, x)] = total influence I[f] - as_t(f): t-th moment = E_x[s(f, x)^t]
- By the Poincaré inequality, average sensitivity equals total influence:
E_x[s(f, x)] = Σ_i Inf_i[f]
References: - O’Donnell Chapter 2 (Influences) - Tal’s BooleanFunc.py (sensitivity, average_sensitivity_moment) - Huang’s Sensitivity Theorem (2019): s(f) ≥ √deg(f)
Functions
|
Find an input achieving maximum sensitivity. |
|
Find an input achieving minimum sensitivity. |
Compute the average sensitivity as(f). |
|
Compute the t-th moment of the sensitivity distribution. |
|
|
Compute the maximum sensitivity s(f). |
|
Compute the minimum sensitivity (everywhere sensitivity). |
|
Return the list of sensitive coordinates at input x. |
|
Return the sensitivity of f at input index x. |
Compute histogram of sensitivity values. |
|
Return per-input sensitivities as a NumPy array. |
|
Compute total influence via the average sensitivity definition. |
- boofun.analysis.sensitivity.sensitivity_at(f: BooleanFunction, x: int) int[source]
Return the sensitivity of f at input index x.
The sensitivity s(f, x) is the number of coordinates i such that f(x) ≠ f(x^i), where x^i is x with the i-th bit flipped.
- Parameters:
f – BooleanFunction to analyze
x – Input point as integer
- Returns:
Number of sensitive coordinates at x
- boofun.analysis.sensitivity.sensitive_coordinates(f: BooleanFunction, x: int) List[int][source]
Return the list of sensitive coordinates at input x.
A coordinate i is sensitive at x if f(x) ≠ f(x^i).
This is Tal’s sens_coor function.
- Parameters:
f – BooleanFunction to analyze
x – Input point as integer
- Returns:
List of variable indices i where f(x) ≠ f(x^i)
References
Tal’s BooleanFunc.py: sens_coor
- boofun.analysis.sensitivity.sensitivity_profile(f: BooleanFunction) ndarray[source]
Return per-input sensitivities as a NumPy array.
- Parameters:
f – BooleanFunction to analyze
- Returns:
Array where profile[x] = s(f, x) for each input x
- boofun.analysis.sensitivity.max_sensitivity(f: BooleanFunction, output_value: int | None = None) int[source]
Compute the maximum sensitivity s(f).
The maximum sensitivity is s(f) = max_x s(f, x).
Optionally restricted to inputs where f(x) = output_value.
- Parameters:
f – BooleanFunction to analyze
output_value – If specified (0 or 1), only consider inputs with this output
- Returns:
Maximum sensitivity
References
Tal’s BooleanFunc.py: max_sensitivity
Huang’s Theorem (2019): s(f) ≥ √deg(f)
- boofun.analysis.sensitivity.min_sensitivity(f: BooleanFunction, output_value: int | None = None) int[source]
Compute the minimum sensitivity (everywhere sensitivity).
The minimum sensitivity is es(f) = min_x s(f, x).
Optionally restricted to inputs where f(x) = output_value.
- Parameters:
f – BooleanFunction to analyze
output_value – If specified (0 or 1), only consider inputs with this output
- Returns:
Minimum sensitivity
References
Tal’s BooleanFunc.py: min_sensitivity
- boofun.analysis.sensitivity.average_sensitivity(f: BooleanFunction) float[source]
Compute the average sensitivity as(f).
The average sensitivity is as(f) = E_x[s(f, x)].
- By the Poincaré inequality, this equals the total influence:
as(f) = Σ_i Inf_i[f]
- Parameters:
f – BooleanFunction to analyze
- Returns:
Average sensitivity
References
Tal’s BooleanFunc.py: average_sensitivity
O’Donnell Theorem 2.14
- boofun.analysis.sensitivity.total_influence_via_sensitivity(f: BooleanFunction) float[source]
Compute total influence via the average sensitivity definition.
This is an alias for average_sensitivity, provided for semantic clarity. Total influence I[f] = Σ_i Inf_i[f] = E_x[s(f, x)] = as(f).
- Parameters:
f – BooleanFunction to analyze
- Returns:
Total influence
- boofun.analysis.sensitivity.average_sensitivity_moment(f: BooleanFunction, t: float) float[source]
Compute the t-th moment of the sensitivity distribution.
- This computes:
as_t(f) = E_x[s(f, x)^t]
The t-th moment captures how spread out the sensitivity distribution is.
Special cases: - t = 0: Always returns 1 - t = 1: Returns average_sensitivity(f) - t = 2: Gives information about variance of sensitivity
This is Tal’s average_sensitivity_moment function.
- Parameters:
f – BooleanFunction to analyze
t – Moment parameter (can be non-integer)
- Returns:
The t-th moment E[s(f,x)^t]
References
Tal’s BooleanFunc.py: average_sensitivity_moment
- boofun.analysis.sensitivity.sensitivity_histogram(f: BooleanFunction) ndarray[source]
Compute histogram of sensitivity values.
Returns an array H where H[k] = |{x : s(f, x) = k}| / 2^n.
This gives the distribution of sensitivity values across inputs.
- Parameters:
f – BooleanFunction to analyze
- Returns:
Array of length n+1 where H[k] is fraction of inputs with sensitivity k
- boofun.analysis.sensitivity.arg_max_sensitivity(f: BooleanFunction, output_value: int | None = None) Tuple[int, int][source]
Find an input achieving maximum sensitivity.
- Parameters:
f – BooleanFunction to analyze
output_value – If specified, only consider inputs with this output
- Returns:
Tuple of (input_x, sensitivity) where sensitivity is maximized
References
Tal’s BooleanFunc.py: arg_max_sensitivity
- boofun.analysis.sensitivity.arg_min_sensitivity(f: BooleanFunction, output_value: int | None = None) Tuple[int, int][source]
Find an input achieving minimum sensitivity.
- Parameters:
f – BooleanFunction to analyze
output_value – If specified, only consider inputs with this output
- Returns:
Tuple of (input_x, sensitivity) where sensitivity is minimized