boofun.analysis.ltf_analysis

Linear Threshold Function (LTF) Analysis Module.

Based on O’Donnell Chapter 5: Threshold Functions and their Analysis.

Key Concepts: - LTF: f(x) = sign(w₁x₁ + … + wₙxₙ - θ) - Geometrically: a hyperplane cutting the Boolean hypercube - Chow parameters: (E[f], Inf₁[f], …, Infₙ[f]) uniquely identify LTFs - CLT applies: weighted sum approaches Gaussian for large n

Theory: - NOT all Boolean functions are LTFs (e.g., XOR/PARITY is NOT an LTF) - AND, OR, Majority, Threshold-k are all LTFs - LTFs are exactly the “halfspace” functions

Functions

`analyze_ltf`(f)	Perform complete LTF analysis of a Boolean function.
`chow_distance`(f, g)	Compute distance between Chow parameters of two functions.
`chow_parameters`(f)	Compute Chow parameters of a Boolean function.
`create_threshold_function`(n, k)	Create a k-threshold function.
`create_weighted_majority`(weights[, threshold])	Create a weighted majority (LTF) function.
`critical_index`(weights)	Compute the critical index of an LTF.
`dummy_voters`(f)	Find "dummy voters" in a weighted voting system.
`find_closest_ltf`(f)	Find the LTF closest to a given function (by Chow parameters).
`find_ltf_weights`(f)	Find LTF weights and threshold for a Boolean function.
`is_ltf`(f)	Test if a Boolean function is a Linear Threshold Function.
`is_regular_ltf`(f[, tau_threshold])	Check if function is a regular LTF (low regularity τ).
`is_symmetric_ltf`(f)	Check if function is a symmetric LTF (all weights equal).
`ltf_influence_from_weights`(weights)	Compute influences of an LTF from its weights.
`ltf_noise_stability_gaussian`(rho)	Gaussian noise stability for regular LTFs (Sheppard's formula).
`ltf_total_influence_estimate`(n[, regularity_tau])	Estimate total influence of an LTF.
`normalize_ltf_weights`(weights, threshold)	Normalize LTF weights to have unit L2 norm.
`regularity`(weights)	Compute the regularity parameter τ of an LTF.

Classes

LTFAnalysis(is_ltf[, weights, threshold, ...])

Complete analysis of a Linear Threshold Function.

class boofun.analysis.ltf_analysis.LTFAnalysis(is_ltf: bool, weights: ndarray | None = None, threshold: float | None = None, chow_parameters: ndarray | None = None, critical_index: int | None = None, regularity: float | None = None, gaussian_noise_stability: float | None = None)[source]

Complete analysis of a Linear Threshold Function.

is_ltf

Whether the function is an LTF

Type:: bool

weights

Weight vector (normalized)

Type:: numpy.ndarray | None

threshold

Threshold value

Type:: float | None

chow_parameters

(E[f], Inf₁[f], …, Infₙ[f])

Type:: numpy.ndarray | None

critical_index

Index where cumulative influence reaches 1/2

Type:: int | None

regularity

Measure of weight concentration

Type:: float | None

is_ltf: bool

weights: ndarray | None = None

threshold: float | None = None

chow_parameters: ndarray | None = None

critical_index: int | None = None

regularity: float | None = None

gaussian_noise_stability: float | None = None

summary() → str[source]: Generate human-readable summary.

__init__(is_ltf: bool, weights: ndarray | None = None, threshold: float | None = None, chow_parameters: ndarray | None = None, critical_index: int | None = None, regularity: float | None = None, gaussian_noise_stability: float | None = None) → None

boofun.analysis.ltf_analysis.chow_parameters(f: BooleanFunction) → ndarray[source]

Compute Chow parameters of a Boolean function.

The Chow parameters are: (E[f], Inf₁[f], …, Infₙ[f])

Key theorem (Chow, 1961): Two LTFs are identical if and only if they have the same Chow parameters.

Parameters:: f – Boolean function
Returns:: Array of length n+1 containing Chow parameters

boofun.analysis.ltf_analysis.is_ltf(f: BooleanFunction) → bool[source]

Test if a Boolean function is a Linear Threshold Function.

Uses linear programming to check if the function is linearly separable.

Parameters:: f – Boolean function to test
Returns:: True if f is an LTF

boofun.analysis.ltf_analysis.find_ltf_weights(f: BooleanFunction) → Tuple[ndarray, float][source]

Find LTF weights and threshold for a Boolean function.

Parameters:: f – Boolean function (must be an LTF)
Returns:: Tuple of (weights array, threshold)
Raises:: ValueError – If f is not an LTF

boofun.analysis.ltf_analysis.normalize_ltf_weights(weights: ndarray, threshold: float) → Tuple[ndarray, float][source]

Normalize LTF weights to have unit L2 norm.

Standard form: Σ wᵢ² = 1

Parameters:

weights – Original weight vector
threshold – Original threshold

Returns:

Tuple of (normalized weights, normalized threshold)

boofun.analysis.ltf_analysis.analyze_ltf(f: BooleanFunction) → LTFAnalysis[source]

Perform complete LTF analysis of a Boolean function.

Parameters:: f – Boolean function
Returns:: LTFAnalysis object with all computed properties

boofun.analysis.ltf_analysis.critical_index(weights: ndarray) → int[source]

Compute the critical index of an LTF.

The critical index k* is the smallest k such that: Σᵢ₌₁ᵏ wᵢ² ≥ 1/2 · Σᵢ₌₁ⁿ wᵢ²

This measures where “half the influence” is concentrated.

Parameters:: weights – LTF weight vector (not necessarily normalized)
Returns:: Critical index (1-indexed)

boofun.analysis.ltf_analysis.regularity(weights: ndarray) → float[source]

Compute the regularity parameter τ of an LTF.

τ = max|wᵢ| / ||w||₂

Small τ means “regular” LTF (no single coordinate dominates). Large τ means closer to a dictator.

Parameters:: weights – LTF weight vector
Returns:: Regularity parameter τ ∈ [0, 1]

boofun.analysis.ltf_analysis.ltf_influence_from_weights(weights: ndarray) → ndarray[source]

Compute influences of an LTF from its weights.

For a normalized LTF with Σwᵢ² = 1: Inf_i[f] ≈ (2/π) · wᵢ² · (1 / σ)

where σ = √(Σwⱼ²) = 1 for normalized weights.

This is the CLT/Berry-Esseen approximation.

Parameters:: weights – LTF weight vector
Returns:: Array of influences

boofun.analysis.ltf_analysis.ltf_noise_stability_gaussian(rho: float) → float[source]

Gaussian noise stability for regular LTFs (Sheppard’s formula).

For the majority function and regular LTFs: Stab_ρ[f] ≈ (1/2) + (1/π) · arcsin(ρ)

This is exact in the limit as n → ∞ for regular LTFs.

Parameters:: rho – Noise parameter ρ ∈ [0, 1]
Returns:: Noise stability estimate

boofun.analysis.ltf_analysis.ltf_total_influence_estimate(n: int, regularity_tau: float = 0.0) → float[source]

Estimate total influence of an LTF.

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

Parameters:

n – Number of variables
regularity_tau – Regularity parameter (0 for perfectly regular)

Returns:

Estimated total influence

boofun.analysis.ltf_analysis.create_weighted_majority(weights: List[float], threshold: float | None = None) → BooleanFunction[source]

Create a weighted majority (LTF) function.

f(x) = sign(w₁x₁ + … + wₙxₙ - θ)

If threshold is not specified, uses θ = 0 (symmetric around 0 in ±1 space).

Parameters:

weights – Weight for each variable
threshold – Threshold value (default: 0)

Returns:

BooleanFunction representing the weighted majority

Example

# Nassau County voting system nassau = create_weighted_majority([31, 31, 28, 21, 2, 2])

boofun.analysis.ltf_analysis.create_threshold_function(n: int, k: int) → BooleanFunction[source]

Create a k-threshold function.

f(x) = 1 if Σxᵢ ≥ k, else 0

Parameters:

n – Number of variables
k – Threshold (1 ≤ k ≤ n)

Returns:

BooleanFunction for threshold-k

Examples

AND = threshold(n, n) OR = threshold(n, 1) MAJORITY = threshold(n, (n+1)/2)

boofun.analysis.ltf_analysis.is_symmetric_ltf(f: BooleanFunction) → bool[source]

Check if function is a symmetric LTF (all weights equal).

Symmetric LTFs are exactly the threshold functions.

Parameters:: f – Boolean function
Returns:: True if f is a symmetric LTF

boofun.analysis.ltf_analysis.is_regular_ltf(f: BooleanFunction, tau_threshold: float = 0.5) → bool[source]

Check if function is a regular LTF (low regularity τ).

Regular LTFs have no dominant variable.

Parameters:

f – Boolean function
tau_threshold – Maximum regularity to be considered “regular”

Returns:

True if f is a regular LTF

boofun.analysis.ltf_analysis.dummy_voters(f: BooleanFunction) → List[int][source]

Find “dummy voters” in a weighted voting system.

A dummy voter has zero influence - their vote never matters.

Parameters:: f – Boolean function (should be an LTF)
Returns:: List of variable indices with zero influence

boofun.analysis.ltf_analysis.chow_distance(f: BooleanFunction, g: BooleanFunction) → float[source]

Compute distance between Chow parameters of two functions.

If both are LTFs, distance = 0 implies f ≡ g.

Parameters:

f – Boolean functions
g – Boolean functions

Returns:

L2 distance between Chow parameter vectors

boofun.analysis.ltf_analysis.find_closest_ltf(f: BooleanFunction) → Tuple[BooleanFunction, float][source]

Find the LTF closest to a given function (by Chow parameters).

Uses Chow parameters to find the best LTF approximation. This is a fundamental result: the LTF with matching Chow parameters is the closest LTF in many senses.

Parameters:: f – Boolean function (may or may not be an LTF)
Returns:: Tuple of (closest LTF, distance)