boofun.core.base
Classes
|
|
|
|
|
|
|
- class boofun.core.base.BooleanFunction(*args, **kwargs)[source]
- compose(other: BooleanFunction) BooleanFunction[source]
Compose this function with another BooleanFunction.
Semantics mirror the legacy
BooleanFunc.compose: ifselfdepends onnvariables andotherdepends onmvariables, the result is a function onn * mvariables obtained by substitutingotherinto each input ofselfon disjoint variable blocks.
- 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
- 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
- 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_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:
Example
>>> def custom_transform(f, scale): ... return f.apply_noise(scale) >>> f.pipe(custom_transform, 0.9).fourier()