boofun

BooFun: A comprehensive Boolean function analysis library.

This library provides tools for creating, analyzing, and visualizing Boolean functions using multiple representations and advanced mathematical techniques.

Key Features: - Multiple Boolean function representations (truth tables, circuits, BDDs, etc.) - Spectral analysis and Fourier transforms - Property testing algorithms - Visualization tools - Built-in Boolean function generators

Basic Usage:

>>> import boofun as bf
>>>
>>> # Create functions from any input
>>> xor = bf.create([0, 1, 1, 0])     # From truth table
>>> maj = bf.majority(5)              # Built-in majority
>>> parity = bf.parity(4)             # Built-in parity (XOR)
>>>
>>> # Natural operations
>>> g = xor & maj                     # AND
>>> h = ~xor                          # NOT
>>>
>>> # Spectral analysis
>>> xor.fourier()                     # Fourier coefficients
>>> xor.influences()                  # Variable influences
>>> xor.degree()                      # Fourier degree

Functions

`AND`(n)	Create AND function on n variables: f(x) = x_1 ∧ x_2 ∧ .
`OR`(n)	Create OR function on n variables: f(x) = x_1 ∨ x_2 ∨ .
`constant`(value, n)	Create constant function: f(x) = value for all x.
`dictator`(n[, i])	Create dictator function on variable i: f(x) = x_i.
`f2_polynomial`(n, monomials)	Create f(x) = (-1)^{p(x)} where p is a polynomial over GF(2).
`from_weights`(weights[, threshold_value])	Create LTF (Linear Threshold Function) from weight vector.
`majority`(n)	Create majority function on n variables: Maj_n(x) = 1 iff \|{i: x_i=1}\| > n/2.
`parity`(n)	Create parity (XOR) function on n variables: ⊕_n(x) = x_1 ⊕ x_2 ⊕ .
`random`(n[, balanced, seed])	Create a random Boolean function on n variables.
`threshold`(n, k)	Create k-threshold function on n variables.
`tribes`(k, n)	Create tribes function: AND of ORs on groups of k variables.
`weighted_majority`(weights[, threshold_value])	Create a weighted majority (LTF) function.

boofun.create(data=None, storage: str = 'auto', **kwargs)[source]

Create a Boolean function from various data sources.

This is the main entry point for creating Boolean functions. It accepts truth tables, functions, distributions, and other representations.

Parameters:

data – Input data for the Boolean function. Can be: - List/array of boolean values (truth table) - Callable function - Dict (polynomial coefficients) - None (creates empty function)
storage – Storage strategy hint: - ‘auto’: Automatically select best representation (default) - ‘dense’: Use dense truth table (fast for n <= 14) - ‘packed’: Use 1-bit per entry (good for n > 14) - ‘sparse’: Store only exceptions (good for skewed functions) - ‘lazy’: Never materialize, compute on demand (for oracles)
**kwargs – Additional arguments: - n: Number of variables (auto-detected if not provided) - space: Mathematical space (default: BOOLEAN_CUBE) - rep_type: Representation type override

Returns:

A Boolean function object

Return type:

BooleanFunction

Examples

>>> # Create XOR function from truth table
>>> xor = create([0, 1, 1, 0])

>>> # Create majority function
>>> maj = create(lambda x: sum(x) > len(x)//2, n=3)

>>> # Create with storage hint for large function
>>> f = create(truth_table, storage='packed')

>>> # Create lazy function that computes on demand
>>> f = create(oracle_func, n=20, storage='lazy')

>>> # Create from polynomial coefficients
>>> poly = create({frozenset([0]): 1, frozenset([1]): 1}, rep_type='polynomial')

class boofun.BooleanFunction(space: str = 'plus_minus_cube', error_model: Any | None = None, storage_manager=None, **kwargs)[source]

__init__(space: str = 'plus_minus_cube', error_model: Any | None = None, storage_manager=None, **kwargs)[source]

compose(other: BooleanFunction) → BooleanFunction[source]

Compose this function with another BooleanFunction.

Semantics mirror the legacy BooleanFunc.compose: if self depends on n variables and other depends on m variables, the result is a function on n * m variables obtained by substituting other into each input of self on disjoint variable blocks.

get_representation(rep_type: str)[source]: Retrieve or compute representation

add_representation(data, rep_type=None)[source]: Add a representation to this boolean function

evaluate(inputs, rep_type=None, **kwargs)[source]

Evaluate function with automatic input type detection and representation selection.

Parameters:

inputs – Input data (array, list, or scipy random variable)
rep_type – Optional specific representation to use
**kwargs – Additional evaluation parameters

Returns:

Boolean result(s) or distribution (with error model applied)

Raises:

InvalidInputError – If inputs are empty or have unsupported type
EvaluationError – If evaluation fails

evaluate_range(inputs)[source]

rvs(size=1, rng=None)[source]: Generate random samples (like scipy.stats)

pmf(x)[source]: Probability mass function

cdf(x)[source]: Cumulative distribution function

get_n_vars()[source]

property num_variables: int: Alias for n_vars for backwards compatibility.

property num_vars: int: Alias for n_vars for backwards compatibility.

has_rep(rep_type)[source]

get_conversion_options(max_cost: float | None = None) → Dict[str, Any][source]

Get available conversion options from current representations.

Parameters:: max_cost – Maximum acceptable conversion cost
Returns:: Dictionary with conversion options and costs

estimate_conversion_cost(target_rep: str) → Any | None[source]

Estimate cost to convert to target representation.

Parameters:: target_rep – Target representation name
Returns:: Conversion cost estimate or None if impossible

to(representation_type: str)[source]

Convert to specified representation (convenience method).

Parameters:: representation_type – Target representation type
Returns:: Self (for method chaining)

fix(var, val)[source]

Fix variable(s) to specific value(s), returning a new function on fewer variables.

This is a fundamental operation for Boolean function analysis, used in: - Decision tree computation - Certificate analysis - Influence computation via derivatives

Parameters:

var – Variable index (int) or list of variable indices
val – Value (0 or 1) or list of values to fix variables to

Returns:

New BooleanFunction with fixed variables removed

Example

>>> f = bf.create([0, 1, 1, 0])  # XOR on 2 vars
>>> g = f.fix(0, 1)  # Fix x_0 = 1, get function on x_1 only

restrict(var: int, val: int) → BooleanFunction[source]

Alias for fix() - restrict a variable to a specific value.

This terminology is often used in the literature (e.g., random restrictions).

derivative(var: int) → BooleanFunction[source]

Compute the discrete derivative with respect to variable var.

The derivative D_i f is defined as:: D_i f(x) = f(x) XOR f(x ⊕ e_i)

where e_i is the i-th unit vector. The derivative is 1 exactly when variable i is influential at input x.

Parameters:: var – Variable index to differentiate with respect to
Returns:: New BooleanFunction representing the derivative

Note

The influence of variable i equals E[D_i f] = Pr[D_i f(x) = 1]

shift(s: int) → BooleanFunction[source]

Shift the function: f_s(x) = f(x ⊕ s).

This applies an XOR mask to all inputs, effectively translating the function in the Boolean cube.

Parameters:: s – Shift mask (integer representing the XOR offset)
Returns:: New BooleanFunction with shifted inputs

negation() → BooleanFunction[source]

Return the negation of this function: NOT f.

Returns:: New BooleanFunction where all outputs are flipped

bias() → float[source]

Compute the bias of the function: E[(-1)^f(x)] = 1 - 2*Pr[f(x)=1].

The bias is in [-1, 1]: - bias = 1 means f is constantly 0 - bias = -1 means f is constantly 1 - bias = 0 means f is balanced

Returns:: Bias value in [-1, 1]

is_balanced() → bool[source]

Check if the function is balanced (equal 0s and 1s in truth table).

Returns:: True if the function outputs 0 and 1 equally often

query_model(max_queries: int = 10000000) → QueryModel[source]

Get the query model for this function.

The query model helps understand computational costs and prevents accidentally running exponential-time operations on huge functions.

Parameters:: max_queries – Maximum acceptable number of function evaluations
Returns:: QueryModel instance with cost estimation methods

Example

>>> f = bf.create(huge_neural_net, n=100)
>>> qm = f.query_model()
>>> qm.can_compute("is_linear")  # True - O(k) queries
>>> qm.can_compute("fourier")     # False - would need 2^100 queries

access_type() → AccessType[source]

Get the access type for this function.

Returns:: AccessType.EXPLICIT if we have the full truth table AccessType.QUERY if we can only evaluate on demand AccessType.SYMBOLIC if we have a formula

is_explicit() → bool[source]: Check if we have explicit access (full truth table).

is_query_access() → bool[source]: Check if this is a query-access function (no truth table).

fourier(force_recompute: bool = False) → ndarray[source]

Compute Fourier coefficients f̂(S) for all subsets S ⊆ [n].

The Fourier expansion is: f(x) = Σ_S f̂(S) χ_S(x) where χ_S(x) = ∏_{i∈S} x_i are the Walsh characters.

Returns:: Array of Fourier coefficients indexed by subset bitmask

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> coeffs = xor.fourier()
>>> coeffs[3]  # f̂({0,1}) = -1 for XOR

spectrum(force_recompute: bool = False) → ndarray[source]: Alias for fourier() - returns Fourier spectrum.

degree(gf2: bool = False) → int[source]

Compute the degree of the function.

Parameters:: gf2 – If True, compute GF(2) (algebraic) degree If False, compute Fourier (real) degree
Returns:: Maximum degree of non-zero coefficient

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> xor.degree()        # Fourier degree = 2
>>> xor.degree(gf2=True)  # GF(2) degree = 1

influences(force_recompute: bool = False) → ndarray[source]

Compute influences of all variables: Inf_i[f] = Pr[f(x) ≠ f(x ⊕ e_i)].

Returns:: Array of influences, one per variable

Example

>>> maj = bf.majority(3)
>>> maj.influences()  # All equal for symmetric function

influence(var: int) → float[source]

Compute influence of a single variable.

Parameters:: var – Variable index (0-indexed)
Returns:: Influence value in [0, 1]

total_influence() → float[source]

Compute total influence: I[f] = Σ_i Inf_i[f].

Also called average sensitivity.

Returns:: Sum of all variable influences

noise_stability(rho: float) → float[source]

Compute noise stability at correlation ρ.

Stab_ρ[f] = E[f(x)f(y)] where y is ρ-correlated with x. In Fourier: Stab_ρ[f] = Σ_S f̂(S)² ρ^|S|

Parameters:: rho – Correlation parameter in [-1, 1]
Returns:: Noise stability value

W(k: int) → float[source]

Compute Fourier weight at exactly degree k: W^{=k}[f] = Σ_{|S|=k} f̂(S)².

Parameters:: k – Degree level
Returns:: Sum of squared Fourier coefficients at degree k

W_leq(k: int) → float[source]

Compute Fourier weight up to degree k: W^{≤k}[f] = Σ_{|S|≤k} f̂(S)².

This measures spectral concentration on low-degree coefficients.

Parameters:: k – Maximum degree
Returns:: Sum of squared Fourier coefficients up to degree k

sparsity(threshold: float = 1e-10) → int[source]

Count non-zero Fourier coefficients.

From O’Donnell: degree-k functions have at most 4^k non-zero coefficients.

Parameters:: threshold – Minimum magnitude to count as non-zero
Returns:: Number of significant Fourier coefficients

spectral_weight_by_degree() → dict[source]

Compute spectral weight at each degree level.

Returns:: Dict mapping degree k -> W^{=k}[f] = Σ_{|S|=k} f̂(S)²

Example

>>> maj = bf.majority(5)
>>> maj.spectral_weight_by_degree()
{0: 0.0, 1: 0.625, 3: 0.3125, 5: 0.0625}

heavy_coefficients(tau: float = 0.1) → list[source]

Find Fourier coefficients with |f̂(S)| ≥ τ.

Parameters:: tau – Threshold for “heavy” coefficient
Returns:: List of (subset_tuple, coefficient) pairs sorted by magnitude

Example

>>> maj = bf.majority(3)
>>> maj.heavy_coefficients(0.3)
[((0,), 0.5), ((1,), 0.5), ((2,), 0.5)]

variance() → float[source]

Compute variance: Var[f] = E[f²] - E[f]² = Σ_{S≠∅} f̂(S)².

Returns:: Variance of the function (0 for constant, 1 for balanced ±1 function)

max_influence() → float[source]

Compute maximum influence: max_i Inf_i[f].

Important for KKL theorem: max_i Inf_i[f] ≥ Ω(log n / n) for balanced f.

Returns:: Maximum influence value

analyze() → dict[source]

Quick analysis returning common metrics.

Returns:

n_vars, is_balanced, variance, degree,: total_influence, max_influence, noise_stability_0.5

Return type:

Dict with

Example

>>> bf.majority(5).analyze()
{'n_vars': 5, 'is_balanced': True, 'variance': 1.0, ...}

negate_inputs() → BooleanFunction[source]

Compute g(x) = f(-x) where -x flips all bits.

In Fourier: ĝ(S) = (-1)^|S| f̂(S) (odd-degree coefficients flip sign)

Returns:: New function with negated inputs

is_linear(num_tests: int = 100) → bool[source]

Test if function is linear (affine over GF(2)).

Uses BLR linearity test.

is_monotone(num_tests: int = 100) → bool[source]: Test if function is monotone: x ≤ y implies f(x) ≤ f(y).

is_junta(k: int) → bool[source]: Test if function depends on at most k variables.

is_global(alpha: float, max_set_size: int = 3) → bool[source]

Check if f has alpha-small generalized influences (is alpha-global).

A function is alpha-global if I_S(f) <= alpha * E[f^2] for all small sets S. Global functions satisfy hypercontractivity under p-biased measures (Keevash-Lifshitz-Long-Minzer).

Parameters:

alpha – Threshold for generalized influences
max_set_size – Maximum |S| to check (default 3)

Returns:

True if all generalized influences are <= alpha * E[f^2]

References

Keevash, Lifshitz, Long & Minzer (arXiv:1906.05039)

is_symmetric(num_tests: int = 100) → bool[source]: Test if function is symmetric (invariant under variable permutations).

hamming_weight() → int[source]

Count number of 1s in truth table (outputs where f(x) = 1).

Also called the “weight” or “on-set size” of the function.

Returns:: Number of inputs x where f(x) = 1

Example

>>> bf.majority(3).hamming_weight()  # 4 (inputs with ≥2 ones)
>>> bf.AND(3).hamming_weight()       # 1 (only 111)

support() → list[source]

Return all inputs where f(x) = 1.

Also called the “on-set” or “satisfying assignments”.

Returns:: List of input indices (as integers) where f(x) = 1

Example

>>> bf.AND(2).support()  # [3] (binary 11)
>>> bf.OR(2).support()   # [1, 2, 3] (01, 10, 11)

restriction(fixed_vars: dict) → BooleanFunction[source]

Create restriction of f by fixing some variables.

Alias for fix() with more standard mathematical terminology.

Parameters:: fixed_vars – Dict mapping variable index -> fixed value (0 or 1)
Returns:: Restricted function on remaining variables

Example

>>> f = bf.majority(3)
>>> g = f.restriction({0: 1})  # Fix x₀=1, get 2-variable function

cofactor(var: int, val: int) → BooleanFunction[source]

Compute Shannon cofactor f|_{x_i=b}.

The cofactor is the restriction of f with variable i fixed to val. Shannon expansion: f = x_i · f|_{x_i=1} + (1-x_i) · f|_{x_i=0}

Parameters:

var – Variable index to fix
val – Value to fix it to (0 or 1)

Returns:

Cofactor function (one fewer variable)

Example

>>> f = bf.majority(3)
>>> f0 = f.cofactor(0, 0)  # f with x₀=0
>>> f1 = f.cofactor(0, 1)  # f with x₀=1

sensitivity_at(x: int) → int[source]

Compute sensitivity of f at input x.

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

Parameters:: x – Input (as integer)
Returns:: Number of sensitive coordinates at x

sensitivity() → int[source]

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

Maximum number of sensitive bits over all inputs. Huang’s theorem: s(f) ≥ √deg(f)

Returns:: Maximum sensitivity

xor(other: BooleanFunction) → BooleanFunction[source]

XOR with another function (chainable).

Equivalent to f ^ g but more readable in chains.

Example

>>> f.xor(g).fourier()
>>> f.restrict(0, 1).xor(g).influences()

and_(other: BooleanFunction) → BooleanFunction[source]

AND with another function (chainable).

Named with underscore to avoid Python keyword conflict. Equivalent to f & g.

or_(other: BooleanFunction) → BooleanFunction[source]

OR with another function (chainable).

Named with underscore to avoid Python keyword conflict. Equivalent to f | g.

not_() → BooleanFunction[source]

Negate output (chainable).

Equivalent to ~f. Returns function g where g(x) = NOT f(x).

apply_noise(rho: float, samples: int = 100) → BooleanFunction[source]

Apply noise to get a new Boolean function via sampling.

For each input x, outputs the majority vote of f(y) over multiple y, where each y is independently ρ-correlated with x.

This gives a Boolean approximation to the noise operator T_ρ.

Parameters:

rho – Correlation parameter in [-1, 1]
samples – Number of samples for majority vote (default: 100)

Returns:

New Boolean function representing noisy version of f

Example

>>> f = bf.parity(5)
>>> noisy_f = f.apply_noise(0.9)  # High noise correlation
>>> # Noisy version has lower degree (high-degree parts attenuated)

noise_expectation(rho: float) → ndarray[source]

Compute (T_ρ f)(x) = E_y[f(y)] for all inputs x.

This returns the real-valued expectations, not a Boolean function. Useful for analysis of noise stability.

In Fourier: (T_ρ f)^(S) = ρ^|S| · f̂(S)

Parameters:: rho – Correlation parameter in [-1, 1]
Returns:: Array of expectations E[f(y)|x] in {-1,+1} representation

Example

>>> f = bf.parity(5)
>>> expectations = f.noise_expectation(0.9)
>>> # All values close to 0 (noise destroys parity signal)

permute(perm: list) → BooleanFunction[source]

Permute variables according to given permutation.

Creates g where g(x_{perm[0]}, …, x_{perm[n-1]}) = f(x_0, …, x_{n-1}).

Parameters:: perm – List defining the permutation, where perm[i] = j means variable i in the new function corresponds to variable j in self.
Returns:: New function with permuted variables

Example

>>> f = bf.dictator(3, 0)  # f(x) = x_0
>>> g = f.permute([2, 0, 1])  # g(x) = x_2 (old position 0 → new position 2)

dual() → BooleanFunction[source]

Compute the dual function f*(x) = 1 - f(1-x) = NOT f(NOT x).

The dual swaps the roles of AND and OR. For monotone functions, f* is the De Morgan dual.

Returns:: Dual function

Example

>>> bf.AND(3).dual()  # Returns OR(3)
>>> bf.OR(3).dual()   # Returns AND(3)

extend(new_n: int, method: str = 'dummy') → BooleanFunction[source]

Extend function to more variables.

Parameters:

new_n – New number of variables (must be >= current n)
method – How to extend: - “dummy”: New variables don’t affect output (default) - “xor”: XOR new variables with output

Returns:

Extended function

Example

>>> f = bf.AND(2)  # f(x0, x1) = x0 AND x1
>>> g = f.extend(4)  # g(x0,x1,x2,x3) = x0 AND x1 (x2,x3 ignored)

named(name: str) → BooleanFunction[source]

Return same function with a descriptive name (for display/debugging).

This is a fluent method that returns self with updated nickname.

Example

>>> f = bf.majority(5).named("MAJ_5")
>>> f.nickname
'MAJ_5'

pipe(func, *args, **kwargs)[source]

Apply an arbitrary function to self (for maximum fluency).

Allows inserting custom transformations into a chain.

Parameters:

func – Function to apply, receives self as first argument
*args – Additional arguments to func
**kwargs –
Additional arguments to func

Returns:

Result of func(self, *args, **kwargs)

Example

>>> def custom_transform(f, scale):
...     return f.apply_noise(scale)
>>> f.pipe(custom_transform, 0.9).fourier()

boofun.partial(n: int, known_values: Dict[int, bool] | None = None, name: str | None = None) → PartialBooleanFunction[source]

Create a partial Boolean function with incremental/streaming support.

A partial function allows you to specify only some outputs, useful for: - Streaming data: adding function values incrementally - Sampling: knowing only a subset of outputs - Large functions: working with sections without full materialization

Parameters:

n – Number of input variables (determines domain size 2^n)
known_values – Optional dictionary mapping input indices to output values
name – Optional name for the function

Returns:

PartialBooleanFunction instance

Examples

>>> import boofun as bf
>>>
>>> # Create empty partial function
>>> p = bf.partial(n=20)
>>>
>>> # With initial values
>>> p = bf.partial(n=20, known_values={0: True, 1: False, 7: True})
>>>
>>> # Add more values incrementally
>>> p.add(5, False)
>>> p.add_batch({10: True, 11: True, 12: False})
>>>
>>> # Check status
>>> p.completeness  # Fraction known
>>> p.num_known  # Count of known values
>>>
>>> # Evaluate
>>> p.evaluate(0)  # True (known)
>>> p.evaluate(100)  # None (unknown)
>>> p[0]  # Indexing syntax also works
>>>
>>> # Estimate unknown values
>>> val, conf = p.evaluate_with_confidence(100)
>>>
>>> # Convert to full function when ready
>>> f = p.to_function(fill_unknown=False)

class boofun.PartialBooleanFunction(n_vars: int, known_values: Dict[int, bool] | None = None, name: str | None = None)[source]

A Boolean function with partial/incomplete specification.

This class wraps PartialRepresentation to provide a user-friendly interface for working with Boolean functions where only some outputs are known.

Key features: - Incremental value addition (streaming) - Completeness tracking - Confidence-based estimation for unknown values - Conversion to full BooleanFunction when complete

n_vars: Number of input variables

size: Total number of possible inputs (2^n_vars)

completeness: Fraction of known values (0.0 to 1.0)

num_known: Count of known values

num_unknown: Count of unknown values

Example

>>> partial = PartialBooleanFunction(n_vars=10)
>>> partial.add(0, True)
>>> partial.add(1, False)
>>> partial.completeness
0.001953125  # 2/1024

__init__(n_vars: int, known_values: Dict[int, bool] | None = None, name: str | None = None)[source]

Initialize a partial Boolean function.

Parameters:

n_vars – Number of input variables (determines domain size 2^n_vars)
known_values – Optional dictionary mapping input indices to output values
name – Optional name for the function

Raises:

ValueError – If n_vars < 0 or n_vars > 30

property n_vars: int: Number of input variables.

property size: int: Total number of possible inputs (2^n_vars).

property completeness: float: Fraction of values that are known (0.0 to 1.0).

property num_known: int: Number of known values.

property num_unknown: int: Number of unknown values.

property is_complete: bool: Check if all values are known.

property name: str | None: Optional name for this function.

add(idx: int, value: bool) → None[source]

Add a known value at a specific input index.

Parameters:

idx – Input index (0 to size-1)
value – Output value at this input

Raises:

IndexError – If idx is out of range

Example

>>> partial.add(5, True)
>>> partial.is_known(5)
True

add_batch(values: Dict[int, bool]) → None[source]

Add multiple known values at once.

Parameters:: values – Dictionary mapping input indices to output values
Raises:: IndexError – If any index is out of range

Example

>>> partial.add_batch({0: True, 1: False, 7: True})

add_from_samples(inputs: ndarray, outputs: ndarray) → None[source]

Add values from arrays of inputs and outputs.

Parameters:

inputs – Array of input indices or binary vectors
outputs – Array of corresponding output values

Example

>>> inputs = np.array([0, 1, 2, 3])
>>> outputs = np.array([True, False, False, True])
>>> partial.add_from_samples(inputs, outputs)

is_known(idx: int) → bool[source]

Check if a specific input’s output is known.

Parameters:: idx – Input index
Returns:: True if the output at this index is known

evaluate(idx: int) → bool | None[source]

Evaluate the function at a specific input.

Parameters:: idx – Input index
Returns:: The output value if known, None if unknown

Example

>>> partial.add(5, True)
>>> partial.evaluate(5)
True
>>> partial.evaluate(6)
None

evaluate_with_confidence(idx: int) → Tuple[bool, float][source]

Evaluate with confidence estimate for unknown values.

For known values, returns (value, 1.0). For unknown values, estimates based on Hamming neighbors.

Parameters:: idx – Input index
Returns:: Tuple of (estimated_value, confidence) - confidence is 1.0 for known values - confidence < 1.0 for estimated values

Example

>>> partial.add(0, True)
>>> partial.add(2, True)
>>> val, conf = partial.evaluate_with_confidence(1)
>>> # val might be True (neighbors are True), conf < 1.0

get_known_indices() → ndarray[source]

Get indices of all known values.

Returns:: Array of input indices where output is known

get_unknown_indices() → ndarray[source]

Get indices of all unknown values.

Returns:: Array of input indices where output is unknown

get_known_values() → Dict[int, bool][source]

Get dictionary of all known (index, value) pairs.

Returns:: Dictionary mapping known indices to their values

to_function(fill_unknown: bool = False, estimate_unknown: bool = False) → BooleanFunction[source]

Convert to a full BooleanFunction.

Parameters:

fill_unknown – Value to use for unknown entries (default False)
estimate_unknown – If True, estimate unknown values using neighbors

Returns:

Complete BooleanFunction

Raises:

ValueError – If not complete and neither fill_unknown nor estimate_unknown

Example

>>> partial = bf.partial(n=2, known_values={0: True, 1: False, 2: False, 3: True})
>>> f = partial.to_function()  # Complete, so this works

to_dense_array(fill_value: bool = False) → ndarray[source]

Convert to dense numpy array, filling unknown with specified value.

Parameters:: fill_value – Value to use for unknown entries
Returns:: Boolean numpy array of shape (2^n_vars,)

sample_unknown(n_samples: int = 1, seed: int | None = None) → ndarray[source]

Randomly sample from unknown indices.

Useful for active learning or guided sampling.

Parameters:

n_samples – Number of indices to sample
seed – Random seed for reproducibility

Returns:

Array of sampled unknown indices

summary() → str[source]

Return human-readable summary of the partial function.

Returns:: Multi-line summary string

boofun.from_hex(hex_str: str, n: int, *, storage: str = 'auto', **kwargs) → BooleanFunction[source]

Create a Boolean function from a hexadecimal truth table string.

This is compatible with thomasarmel/boolean_function’s format where the truth table is represented as a hex string.

Parameters:

hex_str – Hexadecimal string (with or without ‘0x’ prefix)
n – Number of input variables
storage – Storage strategy hint (‘auto’, ‘dense’, ‘packed’, ‘sparse’)
**kwargs – Additional arguments passed to create()

Returns:

BooleanFunction instance

Examples

>>> import boofun as bf
>>>
>>> # From thomasarmel example - 4-bit bent function
>>> f = bf.from_hex("0xac90", n=4)
>>> f.is_bent()  # True
>>>
>>> # 6-bit function
>>> f = bf.from_hex("0113077C165E76A8", n=6)
>>>
>>> # Export back to hex
>>> f.to_hex()

Cross-validation:: This format is compatible with thomasarmel/boolean_function: - BooleanFunction::from_hex_string_truth_table(“0113077C165E76A8”) - SmallBooleanFunction::from_truth_table(0xac90, 4)

boofun.to_hex(f: BooleanFunction) → str[source]

Export a Boolean function to a hexadecimal truth table string.

This produces output compatible with thomasarmel/boolean_function format.

Parameters:: f – BooleanFunction to export
Returns:: Hexadecimal string representation of the truth table

Examples

>>> import boofun as bf
>>>
>>> f = bf.from_hex("ac90", n=4)
>>> bf.to_hex(f)
'ac90'

boofun.load(path: str | Path, format: str | None = None, **kwargs) → BooleanFunction[source]

Load a Boolean function from file.

Parameters:

path – Path to the file
format – Optional format override (“json”, “bf”, “dimacs_cnf”)
**kwargs – Format-specific options

Returns:

BooleanFunction instance

Raises:

FileIOError – If file cannot be loaded
FileNotFoundError – If file does not exist

boofun.save(func: BooleanFunction, path: str | Path, format: str | None = None, **kwargs) → None[source]

Save a Boolean function to file.

Parameters:

func – BooleanFunction to save
path – Destination path
format – Optional format override (“json”, “bf”, “dimacs_cnf”)
**kwargs – Format-specific options

Raises:

FileIOError – If file cannot be saved

boofun.majority(n: int) → BooleanFunction[source]

Create majority function on n variables: Maj_n(x) = 1 iff |{i: x_i=1}| > n/2.

Example

>>> maj5 = bf.majority(5)
>>> maj5([1, 1, 1, 0, 0])  # True (3 > 2.5)

boofun.parity(n: int) → BooleanFunction[source]

Create parity (XOR) function on n variables: ⊕_n(x) = x_1 ⊕ x_2 ⊕ … ⊕ x_n.

Example

>>> xor3 = bf.parity(3)
>>> xor3([1, 1, 0])  # False (even number of 1s)

boofun.tribes(k: int, n: int) → BooleanFunction[source]

Create tribes function: AND of ORs on groups of k variables.

Tribes_{k,n}(x) = ⋀_{j=1}^{⌈n/k⌉} ⋁_{i∈T_j} x_i

This is the dual tribes convention (AND-of-ORs). The textbook tribes (O’Donnell Ch. 4) uses OR-of-ANDs; the two are related by negation.

Parameters:

k – Size of each tribe (number of variables per group)
n – Total number of variables (if not divisible by k, last group is smaller)

Examples

>>> t = bf.tribes(2, 4)  # (x₀ ∨ x₁) ∧ (x₂ ∨ x₃), 4 variables
>>> t = bf.tribes(3, 9)  # (x₀∨x₁∨x₂) ∧ (x₃∨x₄∨x₅) ∧ (x₆∨x₇∨x₈), 9 variables

boofun.dictator(n: int, i: int = 0) → BooleanFunction[source]

Create dictator function on variable i: f(x) = x_i.

Parameters:

n – Number of variables
i – Index of dictating variable (default 0)

Examples

>>> d = bf.dictator(5)     # 5-var dictator on x₀
>>> d = bf.dictator(5, 2)  # 5-var dictator on x₂

boofun.constant(value: bool, n: int) → BooleanFunction[source]

Create constant function: f(x) = value for all x.

Example

>>> zero = bf.constant(False, 3)
>>> one = bf.constant(True, 3)

boofun.AND(n: int) → BooleanFunction[source]

Create AND function on n variables: f(x) = x_1 ∧ x_2 ∧ … ∧ x_n.

Example

>>> and3 = bf.AND(3)

boofun.OR(n: int) → BooleanFunction[source]

Create OR function on n variables: f(x) = x_1 ∨ x_2 ∨ … ∨ x_n.

Example

>>> or3 = bf.OR(3)

boofun.threshold(n: int, k: int) → BooleanFunction[source]

Create k-threshold function on n variables.

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

Special cases: - threshold(n, n) = AND - threshold(n, 1) = OR - threshold(n, (n+1)/2) = MAJORITY (for odd n)

Example

>>> at_least_2 = bf.threshold(4, 2)  # True if ≥2 inputs are 1

boofun.weighted_majority(weights, threshold_value=None) → BooleanFunction[source]

Create a weighted majority (LTF) function.

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

LTFs are also called “halfspaces” - they represent hyperplanes cutting through the Boolean hypercube.

Example

# Nassau County voting system >>> nassau = bf.weighted_majority([31, 31, 28, 21, 2, 2])

# Standard majority (all equal weights) >>> maj = bf.weighted_majority([1, 1, 1, 1, 1])

boofun.random(n: int, balanced: bool = False, seed: int | None = None) → BooleanFunction[source]

Create a random Boolean function on n variables.

Parameters:

n – Number of variables
balanced – If True, output has equal 0s and 1s (default False)
seed – Random seed for reproducibility

Returns:

Random Boolean function

Example

>>> f = bf.random(4)                    # Random 4-variable function
>>> g = bf.random(4, balanced=True)     # Random balanced function
>>> h = bf.random(4, seed=42)           # Reproducible random function

boofun.from_weights(weights, threshold_value=None) → BooleanFunction[source]

Create LTF (Linear Threshold Function) from weight vector.

Alias for weighted_majority() with more intuitive name for LTF creation.

f(x) = 1 iff w₁x₁ + w₂x₂ + … + wₙxₙ ≥ θ

Parameters:

weights – List of integer/float weights for each variable
threshold_value – Threshold (default: sum(weights)/2)

Returns:

LTF (Linear Threshold Function)

Example

>>> # Electoral college with 3 states: CA(55), TX(38), NY(29)
>>> electoral = bf.from_weights([55, 38, 29], threshold=61)

class boofun.SpectralAnalyzer(function: BooleanFunction)[source]

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)[source]

Initialize analyzer with a Boolean function.

Parameters:: function – BooleanFunction instance to analyze

fourier_expansion(force_recompute: bool = False) → ndarray[source]

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[source]

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[source]

Compute total influence (sum of all variable influences).

Returns:: Total influence = Σ_i Inf_i(f)

noise_stability(rho: float) → float[source]

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[source]

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[source]

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][source]

Compute summary statistics for the Boolean function.

Returns:: Dictionary with various spectral properties and confidence information

class boofun.PropertyTester(function: BooleanFunction, random_seed: int | None = None)[source]

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)[source]

constant_test() → bool[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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][source]

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[source]

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

local_correct(x: int, repetitions: int = 10) → int[source]

Local correction for functions close to linear.

If f is ε-close to some linear function χ_S, then for random y:: f(y) ⊕ f(x⊕y) = χ_S(x) with probability ≥ 1-2ε

Uses majority voting over multiple random samples to improve accuracy.

From O’Donnell Lecture 2 / BLR Theorem: This is the “self-correction” property of linear functions. Even if f has some errors, we can compute χ_S(x) correctly with high probability.

Parameters:

x – Input to correct (integer index in {0, 1, …, 2^n - 1})
repetitions – Number of random samples for majority vote

Returns:

Corrected value in {-1, +1} (±1 representation)

Raises:

ValueError – If x is out of range or repetitions < 1

Example

>>> f = bf.parity(4)  # Linear function
>>> tester = PropertyTester(f)
>>> tester.local_correct(5)  # Should return χ_S(5)
1 or -1

local_correct_all(repetitions: int = 10) → ndarray[source]

Apply local correction to all inputs.

Returns the corrected function values for all 2^n inputs.

Parameters:: repetitions – Number of random samples per input
Returns:: numpy array of shape (2^n,) with values in {-1, +1}

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

Run all available property tests.

Returns:: Dictionary mapping test names to results

class boofun.ErrorCode(value)[source]

Machine-readable error codes for BooFun exceptions.

Error codes enable programmatic error handling and logging aggregation. Each code maps to a specific error condition.

Ranges:: E1000-E1999: Validation errors E2000-E2999: Evaluation errors E3000-E3999: Conversion errors E4000-E4999: Configuration errors E5000-E5999: Resource errors E9000-E9999: Internal errors

VALIDATION_ERROR = 'E1000'

INVALID_INPUT = 'E1100'

INVALID_PARAMETER_VALUE = 'E1101'

INVALID_PARAMETER_TYPE = 'E1102'

PARAMETER_OUT_OF_RANGE = 'E1103'

EMPTY_INPUT = 'E1104'

INVALID_REPRESENTATION = 'E1200'

UNKNOWN_REPRESENTATION = 'E1201'

REPRESENTATION_NOT_AVAILABLE = 'E1202'

INVALID_TRUTH_TABLE = 'E1300'

TRUTH_TABLE_WRONG_SIZE = 'E1301'

TRUTH_TABLE_EMPTY = 'E1302'

TRUTH_TABLE_INVALID_VALUES = 'E1303'

EVALUATION_ERROR = 'E2000'

EVALUATION_FAILED = 'E2001'

CALLABLE_RAISED = 'E2002'

INDEX_OUT_OF_BOUNDS = 'E2003'

CORRUPTED_DATA = 'E2004'

CONVERSION_ERROR = 'E3000'

NO_CONVERSION_PATH = 'E3001'

CONVERSION_FAILED = 'E3002'

INCOMPATIBLE_REPRESENTATIONS = 'E3003'

NO_REPRESENTATIONS = 'E3004'

CONFIGURATION_ERROR = 'E4000'

INVALID_ERROR_MODEL = 'E4001'

INCOMPATIBLE_SPACE = 'E4002'

INVALID_OPTIMIZATION = 'E4003'

RESOURCE_UNAVAILABLE = 'E5000'

NUMBA_UNAVAILABLE = 'E5001'

CUPY_UNAVAILABLE = 'E5002'

MATPLOTLIB_UNAVAILABLE = 'E5003'

SCIPY_UNAVAILABLE = 'E5004'

SYMPY_UNAVAILABLE = 'E5005'

INTERNAL_ERROR = 'E9000'

INVARIANT_VIOLATION = 'E9001'

STATE_CORRUPTION = 'E9002'

ALGORITHM_ERROR = 'E9003'

exception boofun.BooleanFunctionError(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Base exception for all BooFun library errors.

All library-specific exceptions inherit from this class, allowing users to catch all library errors with a single except clause.

message: Human-readable error description

code: Machine-readable error code (ErrorCode enum)

context: Dictionary with additional error context

suggestion: Optional suggestion for how to fix the error

Raised By:: This base class is not raised directly. Use specific subclasses.

Example

>>> try:
...     result = bf.create(data).fourier()
... except bf.BooleanFunctionError as e:
...     logger.error(f"[{e.code.value}] {e.message}")
...     if e.suggestion:
...         logger.info(f"Suggestion: {e.suggestion}")

default_code: ErrorCode = 'E9000'

__init__(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

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

Convert exception to dictionary for logging/serialization.

Returns:: Dictionary with error details suitable for JSON logging.

exception boofun.ValidationError(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when user input fails validation.

This is the parent class for all input validation errors. Use specific subclasses when possible for more precise error handling.

Raised By:

bf.create() when data format is unrecognized
Analysis functions when parameters are invalid
Any function receiving malformed input

Error Codes:

E1000: Generic validation error E1100-E1199: Input parameter errors E1200-E1299: Representation errors E1300-E1399: Truth table errors

Example

>>> try:
...     bf.create("invalid")
... except bf.ValidationError as e:
...     print(f"Invalid input: {e.message}")

default_code: ErrorCode = 'E1000'

Raised when function arguments are invalid.

Raised By:

bf.BooleanFunction.evaluate() with empty or wrong-type inputs
bf.BooleanFunction.fix() with invalid variable index or value
bf.BooleanFunction.noise_stability() with rho outside [-1, 1]
Any method receiving out-of-range parameters

Error Codes:

E1100: Generic invalid input E1101: Invalid parameter value E1102: Invalid parameter type E1103: Parameter out of range E1104: Empty input

Example

>>> f = bf.create([0, 1, 1, 0])
>>> f.fix(0, 5)  # Raises InvalidInputError (value must be 0 or 1)

default_code: ErrorCode = 'E1100'

__init__(message: str, code: ErrorCode | None = None, parameter: str | None = None, received: Any = None, expected: str | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when requesting an unsupported or unknown representation.

Raised By:

bf.create() with rep_type parameter set to unknown value
bf.BooleanFunction.get_representation() for unsupported type
Factory methods when representation cannot be determined

Error Codes:

E1200: Generic representation error E1201: Unknown representation type E1202: Representation not available

Example

>>> f = bf.create([0, 1, 1, 0])
>>> f.get_representation("unknown_type")  # Raises InvalidRepresentationError

default_code: ErrorCode = 'E1200'

__init__(message: str, code: ErrorCode | None = None, representation: str | None = None, available: List[str] | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when a truth table has invalid structure.

Raised By:

bf.create() with list/array that is not power of 2
bf.create() with empty list
Factory.from_truth_table() with malformed data

Error Codes:

E1300: Generic truth table error E1301: Wrong size (not power of 2) E1302: Empty truth table E1303: Invalid values (not boolean-convertible)

Example

>>> bf.create([0, 1, 1])  # Raises InvalidTruthTableError (size=3, not power of 2)

default_code: ErrorCode = 'E1300'

__init__(message: str, code: ErrorCode | None = None, size: int | None = None, expected_size: Any | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

exception boofun.EvaluationError(message: str, code: ErrorCode | None = None, input_value: Any = None, representation: str | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when function evaluation fails.

Raised By:

bf.BooleanFunction.evaluate() when underlying callable fails
TruthTableRepresentation.convert_from() during truth table generation
Any operation that evaluates the function on inputs

Error Codes:

E2000: Generic evaluation error E2001: Evaluation failed E2002: Underlying callable raised exception E2003: Index out of bounds E2004: Corrupted representation data

Example

>>> def bad_func(x):
...     raise ValueError("oops")
>>> f = bf.create(bad_func, n=2)
>>> f.get_representation("truth_table")  # Raises EvaluationError

default_code: ErrorCode = 'E2000'

__init__(message: str, code: ErrorCode | None = None, input_value: Any = None, representation: str | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when representation conversion fails.

Raised By:

bf.BooleanFunction.get_representation() when no path exists
bf.BooleanFunction._compute_representation() on conversion failure
Representation strategies during convert_to/convert_from

Error Codes:

E3000: Generic conversion error E3001: No conversion path exists E3002: Conversion algorithm failed E3003: Incompatible representations E3004: No representations available (empty function)

Example

>>> f = bf.BooleanFunction(n=2)  # No representations
>>> f.get_representation("fourier")  # Raises ConversionError

default_code: ErrorCode = 'E3000'

__init__(message: str, code: ErrorCode | None = None, source_repr: str | None = None, target_repr: str | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

exception boofun.ConfigurationError(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None, suggestion: str | None = None)[source]

Raised when library configuration is invalid.

Raised By:

Error model initialization with invalid parameters
Space configuration conflicts
Optimization settings that are incompatible

Error Codes:

E4000: Generic configuration error E4001: Invalid error model E4002: Incompatible space settings E4003: Invalid optimization settings

Example

>>> from boofun import PACErrorModel
>>> PACErrorModel(epsilon=2.0)  # Raises ConfigurationError (epsilon must be in (0,1))

default_code: ErrorCode = 'E4000'

exception boofun.ResourceUnavailableError(message: str, code: ErrorCode | None = None, resource: str | None = None, install_hint: str | None = None, context: Dict[str, Any] | None = None)[source]

Raised when an optional resource is unavailable.

Raised By:

GPU acceleration code when CuPy is not installed
JIT compilation when Numba is not installed
Visualization when Matplotlib is not installed
Any feature requiring optional dependencies

Error Codes:

E5000: Generic resource unavailable E5001: Numba unavailable E5002: CuPy unavailable E5003: Matplotlib unavailable E5004: SciPy unavailable E5005: SymPy unavailable

Example

>>> # When CuPy is not installed:
>>> f.to_gpu()  # Raises ResourceUnavailableError

default_code: ErrorCode = 'E5000'

__init__(message: str, code: ErrorCode | None = None, resource: str | None = None, install_hint: str | None = None, context: Dict[str, Any] | None = None)[source]

exception boofun.InvariantViolationError(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None)[source]

Raised when an internal invariant is violated.

This indicates a bug in the library itself, not a user error. If you encounter this exception, please report it as a bug.

Raised By:

Internal consistency checks that fail
Algorithm outputs that violate postconditions
State machine transitions to invalid states

Error Codes:

E9000: Generic internal error E9001: Invariant violation E9002: State corruption E9003: Algorithm error

Example

If you see this error, please report it at: https://github.com/boofun/boofun/issues

default_code: ErrorCode = 'E9001'

__init__(message: str, code: ErrorCode | None = None, context: Dict[str, Any] | None = None)[source]

class boofun.BooleanFunctionBuiltins[source]

Collection of standard Boolean functions used in research and testing.

classmethod majority(n: int) → BooleanFunction[source]

Create majority function on n variables.

Returns 1 if more than half of the inputs are 1, 0 otherwise. For even n, ties are broken by returning 0.

Parameters:: n – Number of input variables (must be positive)
Returns:: BooleanFunction implementing the majority function

classmethod dictator(n: int, i: int = 0) → BooleanFunction[source]

Create dictator function (output equals i-th input).

The function returns the value of the i-th input variable, ignoring all other inputs: f(x) = x_i.

Parameters:

n – Total number of input variables
i – Index of the dictating variable (0-indexed, default 0)

Returns:

BooleanFunction that outputs x_i

Examples

>>> bf.dictator(5)     # 5-var dictator on x₀
>>> bf.dictator(5, 2)  # 5-var dictator on x₂

classmethod tribes(k: int, n: int) → BooleanFunction[source]

Generate tribes function (AND of ⌈n/k⌉ ORs, each of size k).

The tribes function divides n variables into groups of k, computes OR within each group, then AND across groups:

Tribes_{k,n}(x) = ⋀_{j=1}^{⌈n/k⌉} ⋁_{i∈T_j} x_i

This is the dual tribes convention (AND-of-ORs). The textbook tribes (O’Donnell Ch. 4) uses OR-of-ANDs; the two are related by negation.

Parameters:

k – Size of each tribe (number of variables per group)
n – Total number of variables

Returns:

BooleanFunction implementing the tribes function

Note

If n is not divisible by k, the last group will have fewer variables.

classmethod parity(n: int) → BooleanFunction[source]

Create parity function on n variables.

Returns 1 if an odd number of inputs are 1, 0 otherwise.

Parameters:: n – Number of input variables
Returns:: BooleanFunction implementing the parity function

classmethod constant(value: bool, n: int) → BooleanFunction[source]

Create constant function.

Parameters:

value – Constant value to return (True or False)
n – Number of input variables (for compatibility)

Returns:

BooleanFunction that always returns the constant value

classmethod f2_polynomial(n: int, monomials) → BooleanFunction[source]

Create f(x) = (-1)^{p(x)} where p is a polynomial over GF(2).

The polynomial p(x) = sum of monomials (mod 2), where each monomial is a product of variables. The Boolean function outputs 0 when p(x)=0 and 1 when p(x)=1.

Central to pseudorandomness: F2-polynomials are the functions computed by AC0[parity] circuits.

Parameters:

n – Number of variables
monomials – Iterable of monomials, each a set/list of variable indices. E.g., [{0,1}, {2}] means x0*x1 + x2 (mod 2).

Returns:

BooleanFunction implementing (-1)^{p(x)}

Examples

>>> bf.f2_polynomial(3, [{0}])           # (-1)^{x0}
>>> bf.f2_polynomial(4, [{0,1}, {2,3}])  # (-1)^{x0*x1 + x2*x3}

References

O’Donnell Chapter 6 (pseudorandomness and F2-polynomials)
Chattopadhyay-Hatami-Lovett-Tal (ITCS 2019)

boofun.parseval_verify(f: BooleanFunction, tolerance: float = 1e-10) → Tuple[bool, float, float][source]

Verify Parseval’s identity for a Boolean function.

Parseval’s identity states that for f: {-1,1}^n → ℝ:: E[f(x)²] = Σ_S f̂(S)²
For Boolean functions f: {-1,1}^n → {-1,1}, this gives:: 1 = Σ_S f̂(S)² (since f(x)² = 1 always)

Parameters:

f – BooleanFunction to verify
tolerance – Maximum allowed deviation from expected value

Returns:

passes: True if |lhs - rhs| < tolerance
lhs_value: E[f(x)²] computed directly
rhs_value: Σ_S f̂(S)² from Fourier coefficients

Return type:

Tuple of (passes, lhs_value, rhs_value) where

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> passes, lhs, rhs = parseval_verify(xor)
>>> passes  # Should be True
True

boofun.plancherel_inner_product(f: BooleanFunction, g: BooleanFunction) → float[source]

Compute inner product using Plancherel’s theorem.

Plancherel’s theorem (generalization of Parseval):: ⟨f, g⟩ = E[f(x)g(x)] = Σ_S f̂(S)ĝ(S)

Parameters:

f – BooleanFunctions to compute inner product of
g – BooleanFunctions to compute inner product of

Returns:

Inner product ⟨f, g⟩

Raises:

ValueError – If f and g have different number of variables

boofun.convolution(f: BooleanFunction, g: BooleanFunction) → np.ndarray[source]

Compute the Fourier coefficients of the convolution of two Boolean functions.

The convolution is defined as:: (f * g)(x) = E_y[f(y)g(x ⊕ y)]

By the Convolution Theorem, in the Fourier domain this becomes pointwise multiplication:

(f * g)^(S) = f̂(S) · ĝ(S)

Parameters:

f – BooleanFunctions to convolve
g – BooleanFunctions to convolve

Returns:

numpy array of Fourier coefficients (f * g)^(S) indexed by S

Raises:

ValueError – If f and g have different number of variables

Note

The convolution of two Boolean functions is generally NOT a Boolean function - it’s a real-valued function with values in [-1, 1]. This function returns the exact Fourier coefficients without any loss of information.

Example

>>> f = bf.majority(3)
>>> g = bf.parity(3)
>>> conv_coeffs = convolution(f, g)
>>> # Verify: (f*g)^(S) = f̂(S) · ĝ(S)
>>> assert np.allclose(conv_coeffs, f.fourier() * g.fourier())

boofun.negate_inputs(f: BooleanFunction) → BooleanFunction[source]

Compute g(x) = f(-x) where -x flips all bits.

From HW1 Problem 1: If f(x) = Σ_S f̂(S) χ_S(x), then: g(x) = f(-x) = Σ_S (-1)^|S| f̂(S) χ_S(x)

This flips the sign of odd-degree Fourier coefficients.

Parameters:: f – BooleanFunction to transform
Returns:: New BooleanFunction g where g(x) = f(-x)

boofun.odd_part(f: BooleanFunction) → np.ndarray[source]

Compute the odd part of f: f^odd(x) = (f(x) - f(-x)) / 2.

From HW1 Problem 1: The odd part contains only odd-degree Fourier coefficients.: f^odd(x) = Σ_{|S| odd} f̂(S) χ_S(x)

Parameters:: f – BooleanFunction to analyze
Returns:: Array of function values for f^odd (real-valued, not Boolean)

Note

The result is real-valued, not necessarily Boolean.

boofun.even_part(f: BooleanFunction) → np.ndarray[source]

Compute the even part of f: f^even(x) = (f(x) + f(-x)) / 2.

From HW1 Problem 1: The even part contains only even-degree Fourier coefficients.: f^even(x) = Σ_{|S| even} f̂(S) χ_S(x)

Parameters:: f – BooleanFunction to analyze
Returns:: Array of function values for f^even (real-valued)

boofun.tensor_product(f: BooleanFunction, g: BooleanFunction) → BooleanFunction[source]

Compute tensor product: h(x₁, x₂) = f(x₁) · g(x₂).

From HW1 Problem 1: If f: {-1,1}^n → ℝ and g: {-1,1}^m → ℝ, then: h: {-1,1}^{n+m} → ℝ with h(x₁, x₂) = f(x₁) · g(x₂)
has Fourier expansion:: ĥ(S₁ ∪ S₂) = f̂(S₁) · ĝ(S₂)

where S₁ ⊆ [n] and S₂ ⊆ [m] (shifted to [n+1, n+m]).

Parameters:

f – First BooleanFunction on n variables
g – Second BooleanFunction on m variables

Returns:

Tensor product on n+m variables

boofun.restriction(f: BooleanFunction, fixed_vars: Dict[int, int]) → BooleanFunction[source]

Compute restriction of f by fixing some variables.

From HW1 Problem 1: If we fix the last (n-k) variables to -1:: g(x₁,…,x_k) = f(x₁,…,x_k, -1, -1, …, -1)
The Fourier coefficients satisfy:: ĝ(T) = Σ_{S⊇T, S⊆[k]} f̂(S ∪ {fixed vars where fixed = -1})

Parameters:

f – BooleanFunction to restrict
fixed_vars – Dictionary mapping variable indices to fixed values (0 or 1)

Returns:

Restricted BooleanFunction on remaining variables

Example

>>> f = bf.create([0, 1, 1, 0])  # XOR
>>> g = restriction(f, {0: 1})   # Fix x0 = 1
>>> # g is now NOT(x1) on 1 variable

boofun.fourier_degree(f: BooleanFunction) → int[source]

Compute the Fourier degree (real degree) of f.

The Fourier degree is the maximum |S| such that f̂(S) ≠ 0.

Parameters:: f – BooleanFunction to analyze
Returns:: Maximum degree of non-zero Fourier coefficient

Note

This is different from the GF(2) degree (algebraic degree). For f(x) = x₁x₂ (AND), both degrees are 2. For f(x) = x₁ ⊕ x₂ (XOR), real degree is 2 but GF(2) degree is 1.

boofun.spectral_norm(f: BooleanFunction, p: int = 2) → float[source]

Compute the L_p spectral norm of f.

Parameters:

f – BooleanFunction to analyze
p – Norm parameter (1, 2, or inf)

Returns:

‖f̂‖_p = (Σ_S |f̂(S)|^p)^{1/p}

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

Count the number of non-zero Fourier coefficients.

From HW1 Problem 7: Functions of degree k have at most 4^k non-zero Fourier coefficients.

Parameters:

f – BooleanFunction to analyze
threshold – Minimum absolute value to count as non-zero

Returns:

Number of Fourier coefficients with |f̂(S)| > threshold

boofun.dominant_coefficients(f: BooleanFunction, top_k: int = 10, threshold: float = 0.01) → List[Tuple[int, float]][source]

Find the dominant (largest magnitude) Fourier coefficients.

Parameters:

f – BooleanFunction to analyze
top_k – Maximum number of coefficients to return
threshold – Minimum magnitude to include

Returns:

List of (subset_mask, coefficient) pairs, sorted by magnitude

boofun.gf2_fourier_transform(f: BooleanFunction) → np.ndarray[source]

Compute the GF(2) Fourier transform (Möbius transform) of f.

The result is an array where result[S] = 1 if the monomial corresponding to subset S appears in the ANF of f, and 0 otherwise.

Parameters:: f – BooleanFunction to analyze
Returns:: numpy array of length 2^n where result[S] ∈ {0,1} is the coefficient of monomial S in the ANF representation.

Note

The index S encodes a subset: bit i is set iff variable i is in the monomial. E.g., S=3 (binary 11) represents the monomial x₀*x₁.

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> coeffs = gf2_fourier_transform(xor)
>>> # coeffs[0]=0 (no constant), coeffs[1]=1 (x0), coeffs[2]=1 (x1), coeffs[3]=0 (no x0*x1)

boofun.gf2_degree(f: BooleanFunction) → int[source]

Compute the GF(2) degree (algebraic degree) of f.

The GF(2) degree is the size of the largest monomial in the ANF:: deg_2(f) = max{|S| : c_S ≠ 0}

This is different from the “real” Fourier degree which uses Walsh coefficients.

Parameters:: f – BooleanFunction to analyze
Returns:: The algebraic degree of f over GF(2)

Note

Constant functions have degree 0
Linear functions have degree ≤ 1
XOR(x₁,…,xₙ) has degree 1
AND(x₁,…,xₙ) has degree n
Majority_n has degree n

boofun.gf2_monomials(f: BooleanFunction) → List[Set[int]][source]

Get all monomials with non-zero coefficients in the ANF of f.

Parameters:: f – BooleanFunction to analyze
Returns:: List of sets, where each set contains the variable indices in a monomial. E.g., [{0}, {1}, {0,2}] represents x₀ ⊕ x₁ ⊕ x₀*x₂

boofun.gf2_to_string(f: BooleanFunction, var_prefix: str = 'x') → str[source]

Get a string representation of the ANF of f.

Parameters:

f – BooleanFunction to analyze
var_prefix – Prefix for variable names (default: “x”)

Returns:

String like “1 ⊕ x0 ⊕ x1 ⊕ x0*x1”

boofun.is_linear_over_gf2(f: BooleanFunction) → bool[source]

Check if f is linear over GF(2) (i.e., degree ≤ 1).

A function is linear over GF(2) if it can be written as:: f(x) = c ⊕ a₁x₁ ⊕ a₂x₂ ⊕ … ⊕ aₙxₙ

for some constants c, a₁, …, aₙ ∈ {0,1}.

Note: This is different from being linear over ℝ (which would require all variables to have the same influence and specific Fourier structure).

boofun.correlation_with_parity(f: BooleanFunction, subset: Set[int]) → float[source]

Compute the correlation of f with the parity function on a subset.

The correlation is:: corr(f, χ_S) = E[(-1)^(f(x) ⊕ ⊕_{i∈S} x_i)]

This equals the (normalized) Walsh-Hadamard coefficient f̂(S).

Parameters:

f – BooleanFunction to analyze
subset – Set of variable indices for the parity function

Returns:

Correlation in [-1, 1]

boofun.noise_operator(f: BooleanFunction, rho: float) → np.ndarray[source]

Apply the noise operator T_ρ to a Boolean function.

The noise operator is defined as:

\[(T_\rho f)(x) = \mathbb{E}_y[f(y)]\]

where y is obtained by independently keeping each bit of x with probability (1+ρ)/2 and flipping it with probability (1-ρ)/2.

In Fourier domain: \(\widehat{T_\rho f}(S) = \rho^{|S|} \cdot \hat{f}(S)\)

Parameters:

f – BooleanFunction to apply noise to
rho – Correlation parameter in [-1, 1]

Returns:

Array of (T_ρ f)(x) values for all x

Note

Returns real values in [-1, 1], not Boolean values.

See also

max_influence_bound(): Computes bound for a specific function
friedgut_junta_bound(): Related junta approximation theorem

boofun.max_influence_bound(f: BooleanFunction) → Tuple[float, float, float][source]

Compute max influence and compare with KKL lower bound.

Parameters:: f – BooleanFunction to analyze
Returns:: Tuple of (max_influence, kkl_bound, total_influence)

boofun.friedgut_junta_bound(total_influence: float, epsilon: float) → int[source]

Friedgut’s Junta Theorem bound.

Friedgut’s Theorem (O’Donnell Theorem 9.40): If f: {±1}^n → {±1} has total influence I[f], then f is ε-close to a k-junta where k ≤ 2^{O(I[f]/ε)}.

Parameters:

total_influence – Total influence I[f]
epsilon – Distance threshold

Returns:

Upper bound on junta size k

boofun.junta_approximation_error(f: BooleanFunction, junta_vars: List[int]) → float[source]

Compute the error of approximating f by its projection onto junta variables.

The projection of f onto variables J is:: f_J(x) = E[f | x_J] = averaging f over non-J coordinates

The error is dist(f, f_J) = Pr[f(x) ≠ f_J(x)].

Parameters:

f – BooleanFunction to analyze
junta_vars – List of variable indices to keep

Returns:

Approximation error (probability of disagreement)

Note

This is related to the sum of influences of non-junta variables: dist(f, f_J) ≤ Σ_{i ∉ J} Inf_i[f]

boofun.level_d_inequality(f: BooleanFunction, d: int, q: float = 4) → Tuple[float, float][source]

Level-d inequality (O’Donnell Lemma 9.23).

For the degree-d part of f, denoted f^{=d}:: ‖f^{=d}‖_q ≤ (q-1)^{d/2} · ‖f^{=d}‖_2

This is a consequence of Bonami’s lemma.

Parameters:

f – BooleanFunction to analyze
d – Degree level
q – Norm parameter (q > 2)

Returns:

Tuple of (‖f^{=d}‖_q, (q-1)^{d/2} · ‖f^{=d}‖_2)

boofun.hypercontractive_inequality(f: BooleanFunction, rho: float, p: float = 2, q: float = 4) → Tuple[float, float, bool][source]

Verify the hypercontractive inequality.

Hypercontractive Inequality (O’Donnell Theorem 9.21): For 1 < p ≤ q < ∞ and ρ = √((p-1)/(q-1)):

‖T_ρ f‖_q ≤ ‖f‖_p

Parameters:

f – BooleanFunction to analyze
rho – Noise parameter
p – Input norm parameter
q – Output norm parameter

Returns:

Tuple of (‖T_ρ f‖_q, ‖f‖_p, inequality_satisfied)

class boofun.GlobalHypercontractivityAnalyzer(f: BooleanFunction, p: float = 0.5)[source]

Analyzer for global hypercontractivity properties.

This class provides comprehensive analysis of Boolean functions under p-biased measures, following the framework of Keevash et al.

__init__(f: BooleanFunction, p: float = 0.5)[source]

Initialize the analyzer.

Parameters:

f – Boolean function to analyze
p – Default bias parameter

sigma() → float[source]: Return σ(p) for the current bias.

lambda_p() → float[source]: Return λ(p) for the current bias.

is_global(alpha: float = 0.5, max_set_size: int = 3) → Tuple[bool, Dict][source]

Check if the function is α-global.

Parameters:

alpha – Threshold parameter
max_set_size – Maximum set size to check

Returns:

Tuple of (is_global, details)

generalized_influence(S: Set[int]) → float[source]

Compute I_S(f).

Parameters:: S – Set of variable indices
Returns:: Generalized S-influence

expectation(samples: int = 5000) → float[source]: Estimate E_μp[f].

total_influence(samples: int = 3000) → float[source]: Estimate I^p[f].

noise_stability(rho: float, samples: int = 5000) → float[source]: Estimate S_ρ(f) under μp.

hypercontractive_bound() → Dict[source]: Compute the hypercontractivity bound.

threshold_curve(p_range: ndarray | None = None, samples: int = 1000) → ndarray[source]

Compute the threshold curve μ_p(f) over a range of p.

Parameters:

p_range – Array of p values (default: 0.01 to 0.99)
samples – Monte Carlo samples per point

Returns:

Array of μ_p(f) values

summary(samples: int = 1000) → Dict[source]

Comprehensive summary of the function’s global hypercontractivity properties.

Parameters:: samples – Monte Carlo samples for numerical estimates
Returns:: Dictionary with all key properties

boofun.generalized_influence(f: BooleanFunction, S: Set[int], p: float = 0.5) → float[source]

Compute the generalized S-influence I_S(f) under μ_p.

From Definition I.1.2 and equation (2) in the paper: I_S(f) = σ^{-2|S|} ||D_S(f)||_2^2 = σ^{-2|S|} Σ_{T⊇S} f̂(T)^2

Parameters:

f – Boolean function to analyze
S – Set of variable indices
p – Bias parameter (default 0.5 for uniform measure)

Returns:

Generalized S-influence

boofun.is_alpha_global(f: BooleanFunction, alpha: float, max_set_size: int = 3, p: float = 0.5) → Tuple[bool, Dict][source]

Check if f has α-small generalized influences (Definition I.1.2).

A function has α-small generalized influences if: I_S(f) ≤ α·E[f^2] for all S ⊆ [n]

Parameters:

f – Boolean function to test
alpha – Threshold for generalized influences
max_set_size – Maximum |S| to check (for efficiency)
p – Bias parameter

Returns:

max_generalized_influence: Largest I_S found
worst_set: The set S achieving the maximum
threshold: α·E[f^2]
all_influences: Dictionary of all computed I_S values

Return type:

Tuple of (is_global, details_dict) where details_dict contains

boofun.p_biased_expectation(f: BooleanFunction, p: float, samples: int = 10000) → float[source]

Estimate E_μp[f(x)] via Monte Carlo sampling.

Parameters:

f – Boolean function
p – Bias parameter
samples – Number of Monte Carlo samples

Returns:

Estimated expectation under μ_p

boofun.p_biased_influence(f: BooleanFunction, i: int, p: float, samples: int = 5000) → float[source]

Estimate Inf_i^p[f] under the p-biased measure.

Inf_i^p[f] = Pr_{x~μp}[f(x) ≠ f(x^i)]

where x^i differs from x only in coordinate i.

Parameters:

f – Boolean function
i – Variable index
p – Bias parameter
samples – Number of Monte Carlo samples

Returns:

Estimated p-biased influence of variable i

boofun.p_biased_total_influence(f: BooleanFunction, p: float, samples: int = 3000) → float[source]

Estimate I^p[f] = Σ_i Inf_i^p[f] under the p-biased measure.

From equation (1) in the paper: I(f) = (p(1-p))^{-1} Σ_S |S| f̂(S)^2

Parameters:

f – Boolean function
p – Bias parameter
samples – Number of Monte Carlo samples per variable

Returns:

Estimated total influence under μ_p

boofun.noise_stability_p_biased(f: BooleanFunction, rho: float, p: float, samples: int = 5000) → float[source]

Estimate noise stability S_ρ(f) under the p-biased measure.

S_ρ(f) = E_{x~μp}[f(x)·(T_ρf)(x)]

where (T_ρf)(x) = E_{y~N_ρ(x)}[f(y)] and y is obtained by keeping each bit with probability ρ or resampling from μp.

Parameters:

f – Boolean function
rho – Noise correlation parameter
p – Bias parameter
samples – Number of Monte Carlo samples

Returns:

Estimated noise stability

boofun.threshold_curve(f: BooleanFunction, p_range: ndarray, samples: int = 2000) → ndarray[source]

Compute μ_p(f) for each p in the range.

This is useful for visualizing sharp threshold phenomena.

Parameters:

f – Boolean function
p_range – Array of p values to evaluate
samples – Number of samples per p value

Returns:

Array of μ_p(f) values

boofun.find_critical_p(f: BooleanFunction, samples: int = 3000, tolerance: float = 0.01) → float[source]

Find the critical probability p_c where μ_p(f) ≈ 0.5.

For monotone functions, this is the “threshold” of the function.

Parameters:

f – Boolean function (should be monotone for meaningful result)
samples – Number of samples for expectation estimation
tolerance – Tolerance for binary search

Returns:

Critical probability p_c

boofun.hypercontractivity_bound(f: BooleanFunction, p: float = 0.5) → Dict[source]

Compute the hypercontractivity bound for a function.

From Theorem I.1.3: If f has α-small generalized influences, then ||T_{1/5}f||_4 ≤ α^{1/4} ||f||_2

Parameters:

f – Boolean function
p – Bias parameter

Returns:

alpha: Maximum generalized influence / E[f^2]
bound: α^{1/4} (the hypercontractive bound)
is_global: Whether the function is global
details: Full globality check results

Return type:

Dictionary with

class boofun.BooleanFunctionValidator(function: BooleanFunction, verbose: bool = False)[source]

Comprehensive validator for Boolean function implementations.

Validates correctness, consistency, and performance of Boolean functions across different representations and operations.

__init__(function: BooleanFunction, verbose: bool = False)[source]

Initialize validator.

Parameters:

function – Boolean function to validate
verbose – Whether to print detailed validation messages

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

Run comprehensive validation suite.

Returns:: Dictionary with validation results

validate_basic_properties() → Dict[str, Any][source]: Validate basic Boolean function properties.

validate_representation_consistency() → Dict[str, Any][source]: Validate consistency across different representations.

validate_evaluation_correctness() → Dict[str, Any][source]: Validate evaluation correctness.

validate_space_handling() → Dict[str, Any][source]: Validate space conversion and handling.

validate_edge_cases() → Dict[str, Any][source]: Validate handling of edge cases.

print_validation_report() → None[source]: Print detailed validation report.

boofun.quick_validate(function: BooleanFunction, verbose: bool = False) → bool[source]

Quick validation of a Boolean function.

Parameters:

function – Function to validate
verbose – Whether to print detailed results

Returns:

True if validation passed, False otherwise

boofun.validate_representation(representation: BooleanFunctionRepresentation, n_vars: int = 3) → Dict[str, Any][source]

Quick validation of a representation implementation.

This is a utility function for validating representation implementations, not a pytest test.

Parameters:

representation – Representation to validate
n_vars – Number of variables for testing

Returns:

Validation results dictionary

class boofun.CallableAdapter(n_vars: int | None = None, input_type: str = 'binary_vector')[source]

Adapter for simple callable functions.

Wraps Python functions or lambdas to work with BooFun system.

__init__(n_vars: int | None = None, input_type: str = 'binary_vector')[source]

Initialize callable adapter.

Parameters:

n_vars – Number of variables
input_type – How to pass inputs (“binary_vector”, “individual_args”, “integer”)

adapt(callable_function: Callable) → BooleanFunction[source]: Adapt callable to BooleanFunction.

class boofun.LegacyAdapter(evaluation_method: str = 'evaluate', input_format: str = 'auto', output_format: str = 'auto', n_vars: int | None = None)[source]

Adapter for legacy Boolean function implementations.

Wraps legacy functions that may have different interfaces to work with the modern BooFun system.

__init__(evaluation_method: str = 'evaluate', input_format: str = 'auto', output_format: str = 'auto', n_vars: int | None = None)[source]

Initialize legacy adapter.

Parameters:

evaluation_method – Name of evaluation method in legacy function
input_format – Expected input format (“binary”, “integer”, “auto”)
output_format – Expected output format (“boolean”, “integer”, “auto”)
n_vars – Number of variables if known

adapt(legacy_function: Any) → BooleanFunction[source]: Adapt legacy function to BooFun interface.

class boofun.SymPyAdapter[source]

Adapter for SymPy Boolean expressions.

Integrates SymPy symbolic Boolean functions with BooFun.

__init__()[source]: Initialize SymPy adapter.

adapt(sympy_expr, variables: list | None = None) → BooleanFunction[source]

Adapt SymPy Boolean expression to BooleanFunction.

Parameters:

sympy_expr – SymPy Boolean expression
variables – List of variable symbols (auto-detected if None)

Returns:

BooleanFunction representing the SymPy expression

class boofun.NumPyAdapter(vectorized: bool = True)[source]

Adapter for NumPy-based Boolean function implementations.

Handles vectorized NumPy functions and makes them compatible with BooFun.

__init__(vectorized: bool = True)[source]

Initialize NumPy adapter.

Parameters:: vectorized – Whether the function supports batch evaluation

adapt(numpy_function: Callable, n_vars: int) → BooleanFunction[source]

Adapt NumPy function to BooleanFunction.

Parameters:

numpy_function – NumPy-based Boolean function
n_vars – Number of variables

Returns:

BooleanFunction wrapper

boofun.adapt_callable(func: Callable, n_vars: int, **kwargs) → BooleanFunction[source]: Adapt simple callable to BooleanFunction.

boofun.adapt_sympy_expr(expr, variables: list | None = None) → BooleanFunction[source]: Adapt SymPy Boolean expression.

boofun.adapt_numpy_function(func: Callable, n_vars: int, vectorized: bool = True) → BooleanFunction[source]: Adapt NumPy-based Boolean function.

class boofun.Space(value)[source]

BOOLEAN_CUBE = 1

PLUS_MINUS_CUBE = 2

REAL = 3

LOG = 4

GAUSSIAN = 5

static translate(input: int | float | ndarray, source_space: Space, target_space: Space) → int | float | ndarray[source]

Translate a scalar or array from one space to another.

Parameters:

input – Input value(s) to translate
source_space – Source mathematical space
target_space – Target mathematical space

Returns:

Translated value(s) in target space

Examples

>>> Space.translate([0, 1], Space.BOOLEAN_CUBE, Space.PLUS_MINUS_CUBE)
array([-1,  1])
>>> Space.translate([-1, 1], Space.PLUS_MINUS_CUBE, Space.BOOLEAN_CUBE)
array([0, 1])

static get_canonical_space() → Space[source]: Get the canonical space for internal computations.

static is_discrete(space: Space) → bool[source]: Check if space uses discrete values.

static is_continuous(space: Space) → bool[source]: Check if space uses continuous values.

static get_default_threshold(space: Space) → float[source]: Get default threshold for converting continuous to discrete.

class boofun.Measure(p: float = 0.5)[source]

A probability measure on the Boolean hypercube.

Supports uniform (p=0.5) and p-biased measures where each bit is 1 independently with probability p.

This unifies p-biased analysis: instead of calling separate functions from analysis/p_biased.py, pass a Measure to standard methods.

Examples

>>> uniform = Measure.uniform()
>>> biased = Measure.p_biased(0.3)
>>> biased.p       # 0.3
>>> biased.sigma    # sqrt(0.3 * 0.7)

__init__(p: float = 0.5)[source]

classmethod uniform() → Measure[source]: The uniform measure (p = 1/2).

classmethod p_biased(p: float) → Measure[source]: P-biased measure: each bit is 1 with probability p.

property p: float: Bias parameter.

property sigma: float

sqrt(p(1-p)).

Type:: Standard deviation of a single bit

property is_uniform: bool: True if this is the uniform measure (p = 0.5).

sample(n: int, rng=None) → ndarray[source]

Sample a random input from this measure.

Parameters:

n – Number of variables
rng – NumPy random generator (optional)

Returns:

Binary array of length n

sample_batch(n: int, n_samples: int, rng=None) → ndarray[source]

Sample multiple inputs from this measure.

Parameters:

n – Number of variables
n_samples – Number of samples
rng – NumPy random generator (optional)

Returns:

Array of shape (n_samples, n) with binary entries

weight(x) → float[source]

Probability of a specific input under this measure.

Parameters:: x – Input as integer index or binary array
Returns:: mu_p(x) = p^|x| * (1-p)^(n-|x|)

class boofun.Property(name, test_func=None, doc=None, closed_under=None)[source]

__init__(name, test_func=None, doc=None, closed_under=None)[source]

class boofun.ExactErrorModel[source]

Exact error model - no errors or uncertainty.

This model assumes perfect computation with no noise or approximation.

apply_error(result: Any) → Any[source]: Return result unchanged.

get_confidence(result: Any) → float[source]: Always return maximum confidence.

is_reliable(result: Any) → bool[source]: Always reliable for exact computations.

class boofun.PACErrorModel(epsilon: float = 0.1, delta: float = 0.1)[source]

PAC (Probably Approximately Correct) error model.

Provides probabilistic guarantees with specified error and confidence bounds.

__init__(epsilon: float = 0.1, delta: float = 0.1)[source]

Initialize PAC error model.

Parameters:

epsilon – Approximation error bound (0 < epsilon < 1)
delta – Confidence failure probability (0 < delta < 1)

apply_error(result: Any) → Dict[str, Any][source]

Apply PAC bounds to result.

Returns:: Dictionary with result and PAC bounds

get_confidence(result: Any) → float[source]: Return PAC confidence level.

is_reliable(result: Any) → bool[source]: Check if confidence meets threshold (>= 0.9).

combine_pac_bounds(error1: PACErrorModel, error2: PACErrorModel, operation: str) → PACErrorModel[source]

Combine PAC learning error bounds for two results.

Parameters:

error1 – PAC error models to combine
error2 – PAC error models to combine
operation – Type of operation (‘addition’, ‘multiplication’, etc.)

Returns:

Combined PAC error model

class boofun.NoiseErrorModel(noise_rate: float = 0.01, random_seed: int | None = None)[source]

Noise error model for handling bit-flip and measurement errors.

Simulates realistic noise in Boolean function evaluation and analysis.

__init__(noise_rate: float = 0.01, random_seed: int | None = None)[source]

Initialize noise error model.

Parameters:

noise_rate – Probability of bit flip (0 <= noise_rate <= 0.5)
random_seed – Random seed for reproducible noise

apply_error(result: bool | ndarray) → bool | ndarray[source]

Apply bit-flip noise to Boolean results.

Parameters:: result – Boolean result(s)
Returns:: Result(s) with noise applied

get_confidence(result: Any) → float[source]: Return confidence based on noise level.

is_reliable(result: Any) → bool[source]: Check if noise level allows reliable results.

boofun.get_gf_field(p: int = 2, m: int = 1) → GFField: Return a simple GF(p^m) descriptor.

class boofun.GFField(p: int, m: int = 1)[source]

Descriptor for GF(p^m).

p: int

m: int = 1

property order: int

element_type()[source]

__init__(p: int, m: int = 1) → None

class boofun.MajorityFamily[source]

Majority function family: MAJ_n(x) = 1 if Σx_i > n/2.

Well-known asymptotics: - Total influence: I[MAJ_n] ≈ √(2/π) · √n ≈ 0.798√n - Each influence: Inf_i[MAJ_n] ≈ √(2/(πn)) - Noise stability: Stab_ρ[MAJ_n] → (1/2) + (1/π)arcsin(ρ) - Fourier degree: n (but most weight on lower degrees)

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

validate_n(n: int) → bool[source]: Check if n is valid for this family.

class boofun.ParityFamily[source]

Parity/XOR function family: XOR_n(x) = Σx_i mod 2.

Parity is the “opposite” of Majority in many ways: - NOT an LTF (not linearly separable) - All Fourier weight on a single coefficient - Maximum noise sensitivity

Asymptotics: - Total influence: I[XOR_n] = n (each variable is pivotal always) - Noise stability: Stab_ρ[XOR_n] = ρ^n → 0 for ρ < 1 - Fourier: f̂(S) = 1 only for S = [n], else 0

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.TribesFamily[source]

Tribes function family: Balanced DNF with k tribes of size s.

Standard choice: s = log(n) - log(log(n)) for k = n/s tribes. This achieves Pr[TRIBES = 1] ≈ 1/2.

Asymptotics: - Total influence: I[TRIBES] ≈ log(n)/n · n = log(n) - Each influence: Inf_i[TRIBES] ≈ log(n)/n - Noise stability: Complex, depends on parameters

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, k: int | None = None, w: int | None = None, **kwargs) → BooleanFunction[source]

Generate tribes function.

Parameters:

n – Total number of variables
k – Number of tribes (optional, auto-computed if not provided)
w – Width of each tribe (optional, auto-computed if not provided)

Note: bf.tribes(tribe_size, total_vars) so we call bf.tribes(w, n)

class boofun.ThresholdFamily(k_function: Callable[[int], int] | None = None)[source]

Threshold function family: THR_k(x) = 1 if Σx_i ≥ k.

This is a symmetric LTF (uniform weights).

Special cases: - k = 1: OR function - k = n: AND function - k = (n+1)/2: Majority (for odd n)

__init__(k_function: Callable[[int], int] | None = None)[source]

Initialize threshold family.

Parameters:: k_function – Function n -> k specifying threshold for each n. Default: k = n//2 + 1 (majority-like)

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, k: int | None = None, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.ANDFamily[source]

AND function family: AND_n(x) = 1 iff all x_i = 1.

Extreme threshold function (k = n).

Asymptotics: - Total influence: I[AND_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[AND_n] = 2^{-(n-1)} - Pr[AND_n = 1] = 2^{-n}

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.ORFamily[source]

OR function family: OR_n(x) = 1 iff at least one x_i = 1.

Extreme threshold function (k = 1). Dual of AND: OR_n(x) = ¬AND_n(¬x).

Asymptotics: - Total influence: I[OR_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[OR_n] = 2^{-(n-1)} - Pr[OR_n = 1] = 1 - 2^{-n}

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.DictatorFamily(variable: int = 0)[source]

Dictator function family: DICT_i(x) = x_i.

The “simplest” Boolean function - just returns one variable.

Asymptotics: - Total influence: I[DICT] = 1 (only one influential variable) - Inf_i[DICT] = 1, Inf_j[DICT] = 0 for j ≠ i - Noise stability: Stab_ρ[DICT] = ρ

__init__(variable: int = 0)[source]

Initialize dictator family.

Parameters:: variable – Which variable to use (default: 0)

property metadata: FamilyMetadata: Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.LTFFamily(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')[source]

General LTF (Linear Threshold Function) family.

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

This is a more flexible version of WeightPatternFamily with additional convenience methods.

__init__(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')[source]

Initialize LTF family.

Parameters:

weight_pattern – Function (i, n) -> weight of variable i
threshold_pattern – Function n -> threshold
name – Family name

property metadata: FamilyMetadata: Return metadata about this family.

classmethod uniform(name: str = 'UniformLTF') → LTFFamily[source]: Create LTF with uniform weights (= Majority).

classmethod geometric(ratio: float = 0.5, name: str = 'GeometricLTF') → LTFFamily[source]: Create LTF with geometrically decaying weights.

classmethod harmonic(name: str = 'HarmonicLTF') → LTFFamily[source]: Create LTF with harmonic weights 1/(i+1).

classmethod power_law(power: float = 2.0, name: str = 'PowerLTF') → LTFFamily[source]: Create LTF with power-law weights.

class boofun.GrowthTracker(family: FunctionFamily)[source]

Track properties of a function family as n grows.

Usage:

tracker = GrowthTracker(MajorityFamily()) tracker.mark(“total_influence”) tracker.mark(“noise_stability”, rho=0.5)

results = tracker.observe([5, 7, 9, 11, 13, 15]) tracker.plot(“total_influence”, show_theory=True)

__init__(family: FunctionFamily)[source]

Initialize tracker for a function family.

Parameters:: family – The function family to track

mark(property_name: str, **kwargs) → GrowthTracker[source]

Add a property to track.

Parameters:

property_name – Built-in property name or “custom”
**kwargs – Parameters for the marker

Returns:

self (for chaining)

Built-in properties:

“total_influence”
“influences” or “influence_i” (with variable=i)
“noise_stability” (with rho=0.5)
“fourier_degree”
“spectral_concentration” (with k=degree)
“expectation”
“variance”
“is_<property>” (e.g., “is_monotone”, “is_balanced”)
“sensitivity”
“block_sensitivity”

observe(n_values: List[int] | None = None, n_range: range | None = None, n_min: int = 3, n_max: int = 15, step: int = 2, verbose: bool = False) → Dict[str, TrackingResult][source]

Observe the family over a range of n values.

Parameters:

n_values – Explicit list of n values
n_range – Range object for n values
n_min – Parameters for default range
n_max – Parameters for default range
step – Parameters for default range
verbose – Print progress

Returns:

Dictionary mapping marker name -> TrackingResult

get_result(marker_name: str) → TrackingResult | None[source]: Get tracking result for a specific marker.

plot(marker_name: str, show_theory: bool = True, log_scale: bool = False, ax=None, **plot_kwargs)[source]

Plot a tracked property vs n.

Parameters:

marker_name – Which marker to plot
show_theory – Show theoretical prediction line
log_scale – Use log scale for y-axis
ax – Matplotlib axes (creates new figure if None)
**plot_kwargs – Additional arguments for plt.plot

Returns:

Matplotlib axes

plot_all(show_theory: bool = True, figsize: Tuple[int, int] = (15, 4))[source]: Plot all tracked markers in subplots.

summary() → str[source]: Generate text summary of tracking results.

clear()[source]: Clear all tracking data.

class boofun.FunctionFamily[source]

Abstract base class for Boolean function families.

A function family is a parameterized collection f_n indexed by n. Examples: Majority_n, Parity_n, Tribes_{k,n}

Subclasses must implement: - generate(n) -> BooleanFunction - metadata property

Optional overrides: - theoretical_value(property_name, n) -> theoretical prediction

abstractmethod generate(n: int, **kwargs) → BooleanFunction[source]

Generate the function for n variables.

Parameters:

n – Number of variables
**kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

abstract property metadata: FamilyMetadata: Return metadata about this family.

validate_n(n: int) → bool[source]: Check if n is valid for this family.

theoretical_value(property_name: str, n: int, **kwargs) → float | None[source]

Get theoretical/asymptotic value for a property.

Parameters:

property_name – Name of the property (e.g., “total_influence”)
n – Number of variables
**kwargs – Additional parameters (e.g., rho for noise stability)

Returns:

Theoretical value if known, None otherwise

generate_range(n_values: List[int], **kwargs) → Dict[int, BooleanFunction][source]

Generate functions for a range of n values.

Parameters:

n_values – List of n values to generate
**kwargs – Additional parameters

Returns:

Dictionary mapping n -> BooleanFunction

class boofun.InductiveFamily(name: str = 'InductiveFamily', base_cases: Dict[int, BooleanFunction] | None = None, step_function: Callable | None = None, step_size: int = 1)[source]

A function family defined inductively/recursively.

The user provides: - base_case(n) -> BooleanFunction for small n - step(f_prev, n) -> how to extend from n-1 to n variables

This is useful for functions defined by their structure: - “Add a new variable with weight w_n” - “Apply a recursive construction”

Example

# Define Majority inductively class InductiveMajority(InductiveFamily):

def base_case(self, n):

if n == 1:
return bf.dictator(1, 0) # 1 variable, dictator on var 0

return None

def step(self, f_prev, n, n_prev):
# Majority_n from Majority_{n-1} # Requires knowing the recursive structure …

__init__(name: str = 'InductiveFamily', base_cases: Dict[int, BooleanFunction] | None = None, step_function: Callable | None = None, step_size: int = 1)[source]

Initialize an inductive family.

Parameters:

name – Family name
base_cases – Dictionary of {n: BooleanFunction} for base cases
step_function – Function (f_prev, n) -> f_n
step_size – Number of variables added per step (default 1)

property metadata: FamilyMetadata: Return metadata about this family.

base_case(n: int) → BooleanFunction | None[source]

Get base case for n, if it exists.

Override this in subclasses or provide base_cases dict.

step(f_prev: BooleanFunction, n: int, n_prev: int) → BooleanFunction[source]

Generate f_n from f_{n_prev}.

Override this in subclasses or provide step_function.

Parameters:

f_prev – Function at previous step
n – Target number of variables
n_prev – Previous number of variables

Returns:

Function with n variables

generate(n: int, **kwargs) → BooleanFunction[source]: Generate function for n variables using induction.

clear_cache()[source]: Clear the cached functions.

class boofun.BooleanFunctionVisualizer(function: BooleanFunction, backend: str = 'matplotlib')[source]

Comprehensive visualization toolkit for Boolean functions.

Provides static and interactive plots for Boolean function analysis, including influences, Fourier spectra, truth tables, and more.

__init__(function: BooleanFunction, backend: str = 'matplotlib')[source]

Initialize visualizer.

Parameters:

function – Boolean function to visualize
backend – Plotting backend (“matplotlib”, “plotly”)

plot_influences(figsize: Tuple[int, int] = (10, 6), save_path: str | None = None, show: bool = True) → Any[source]

Plot variable influences.

Parameters:

figsize – Figure size for matplotlib
save_path – Path to save the plot
show – Whether to display the plot

Returns:

Figure object

plot_fourier_spectrum(max_degree: int | None = None, figsize: Tuple[int, int] = (12, 8), save_path: str | None = None, show: bool = True) → Any[source]

Plot Fourier spectrum grouped by degree.

Parameters:

max_degree – Maximum degree to plot (None for all)
figsize – Figure size for matplotlib
save_path – Path to save the plot
show – Whether to display the plot

Returns:

Figure object

plot_truth_table(figsize: Tuple[int, int] = (10, 8), save_path: str | None = None, show: bool = True) → Any[source]

Plot truth table as a heatmap.

Parameters:

figsize – Figure size for matplotlib
save_path – Path to save the plot
show – Whether to display the plot

Returns:

Figure object

plot_noise_stability_curve(rho_range: ndarray | None = None, figsize: Tuple[int, int] = (10, 6), save_path: str | None = None, show: bool = True) → Any[source]

Plot noise stability as a function of correlation ρ.

Parameters:

rho_range – Range of ρ values to plot
figsize – Figure size for matplotlib
save_path – Path to save the plot
show – Whether to display the plot

Returns:

Figure object

create_dashboard(save_path: str | None = None, show: bool = True) → Any[source]

Create comprehensive analysis dashboard.

Parameters:

save_path – Path to save the dashboard
show – Whether to display the dashboard

Returns:

Dashboard figure

Modules

`analysis`	Boolean function analysis module providing spectral analysis tools.
`api`	API module providing user-friendly entry points for creating Boolean functions.
`core`
`families`	Boolean Function Families - Parameterized families that grow with n.
`quantum_complexity`	Classical estimation of quantum query complexity bounds for Boolean functions.
`testing`	Testing utilities and validation tools for BooFun library.
`utils`	Utility modules for boofun package.
`visualization`	Visualization module for Boolean function analysis.