boofun.analysis.block_sensitivity

Block sensitivity analysis for Boolean functions.

Block sensitivity is a fundamental complexity measure that counts the maximum number of disjoint sensitive blocks at any input. It is closely related to decision tree complexity through the block sensitivity theorem.

This module provides both exact and efficient algorithms: - Exact backtracking search for small functions - Fast minimal block computation using sieve-like filtering - Optimized max block sensitivity with pruning via sensitivity/certificates

Functions

block_sensitivity_at(f, x)	Compute the block sensitivity of f at input x.
block_sensitivity_profile(f)	Compute block sensitivity profile of f.
max_block_sensitivity(f[, value, use_pruning])	Compute the maximum block sensitivity of f.
minimal_sensitive_blocks(f, x)	Find all minimal sensitive blocks at input x.
sensitive_coordinates(f, x)	Find coordinates where f is sensitive at input x.

boofun.analysis.block_sensitivity.block_sensitivity_at(f: BooleanFunction, x: int) → int

Compute the block sensitivity of f at input x.

The block sensitivity bs(f, x) is the maximum number of pairwise disjoint blocks B such that flipping all bits in each B changes f(x).

This implementation uses minimal blocks for efficiency: 1. Find all minimal sensitive blocks (fast sieve algorithm) 2. Find maximum packing of disjoint blocks (backtracking)

Parameters:

• f – BooleanFunction to analyze

• x – Input index (integer representation)

Returns:

Block sensitivity at x

Example

>>> and_func = bf.create([0, 0, 0, 1])
>>> block_sensitivity_at(and_func, 3)  # At (1,1)
2  # Both single-bit blocks are sensitive

boofun.analysis.block_sensitivity.max_block_sensitivity(f: BooleanFunction, value: int | None = None, use_pruning: bool = True) → int

Compute the maximum block sensitivity of f.

The block sensitivity bs(f) = max_x bs(f, x).

This implementation uses several optimizations: 1. Early termination when bs reaches n (the maximum possible) 2. Optional pruning: skip inputs where sensitivity = certificate

(since bs(x) >= s(x) and bs(x) <= C(x))

Parameters:

• f – BooleanFunction to analyze

• value – If specified (0 or 1), only consider inputs where f(x) = value

• use_pruning – Whether to use sensitivity/certificate pruning

Returns:

Maximum block sensitivity across all (relevant) inputs

Note

Block sensitivity satisfies: - s(f) <= bs(f) <= C(f) (sensitivity <= block sensitivity <= certificate) - D(f) <= bs(f)^2 (Nisan’s theorem, superseded) - bs(f) = Theta(s(f)^4) (Huang’s theorem, 2019)

boofun.analysis.block_sensitivity.minimal_sensitive_blocks(f: BooleanFunction, x: int) → List[int]

Find all minimal sensitive blocks at input x.

A block B is a minimal sensitive block if flipping all bits in B changes the output, but no proper subset of B is sensitive.

This uses an efficient sieve-like algorithm: 1. Mark all sensitive blocks 2. For each block, check if any proper subset is also sensitive 3. Keep only blocks with no sensitive proper subsets

Parameters:

• f – BooleanFunction to analyze

• x – Input index (integer representation)

Returns:

List of minimal sensitive blocks (as bitmasks)

Note

Time complexity: O(n * 2^n) where n is the number of variables.

boofun.analysis.block_sensitivity.sensitive_coordinates(f: BooleanFunction, x: int) → List[int]

Find coordinates where f is sensitive at input x.

A coordinate i is sensitive at x if flipping bit i changes f(x). This is the set of coordinates that contribute to sensitivity(f, x).

Parameters:

• f – BooleanFunction to analyze

• x – Input index

Returns:

List of sensitive coordinate indices

boofun.analysis.block_sensitivity.block_sensitivity_profile(f: BooleanFunction) → Tuple[int, int, List[int]]

Compute block sensitivity profile of f.

Returns:

• bs0: max block sensitivity on inputs where f(x) = 0

• bs1: max block sensitivity on inputs where f(x) = 1

• per_input_bs: list of bs(f, x) for each input x

Return type:

Tuple of (bs0, bs1, per_input_bs) where