boofun.analysis.restrictions

Random restrictions for Boolean function analysis.

Random restrictions are a fundamental tool in circuit complexity and DNF analysis, as described in O’Donnell Chapter 4 and the Switching Lemma.

A p-random restriction ρ ∈ {0, 1, *}^n assigns each variable: - A fixed value (0 or 1) with probability 1-p each - The “free” symbol * with probability p

When applied to f, the restriction f|_ρ is a function on the remaining free variables.

Key applications: - DNF Fourier concentration (Mansour’s theorem) - Decision tree depth reduction - Switching lemma proofs - Shrinkage of formulas under random restrictions

Functions

`apply_restriction`(f, rho)	Apply a restriction to a Boolean function.
`average_restricted_decision_tree_depth`(f, p)	Estimate expected decision tree depth after random p-restriction.
`batch_random_restrictions`(n, p, num_restrictions)	Generate multiple random restrictions.
`min_fixing_to_constant`(f[, target_value, rng])	Find a minimum set of variable assignments that fixes f to a constant.
`random_restriction`(n, p[, rng])	Generate a random p-restriction on n variables.
`restriction_shrinkage`(f, p[, num_samples, rng])	Estimate how much random restrictions shrink various complexity measures.
`restriction_to_inputs`(rho[, num_inputs])	Generate all inputs consistent with a restriction.
`shift_by_mask`(f, mask)	Shift a Boolean function by XORing all inputs with a mask.
`switching_lemma_probability`(width, p, ...)	Estimate probability bound from the Switching Lemma.

Classes

Restriction(fixed, free, n_vars)

A restriction that fixes some variables and leaves others free.

class boofun.analysis.restrictions.Restriction(fixed: Dict[int, int], free: Set[int], n_vars: int)[source]

A restriction that fixes some variables and leaves others free.

fixed

Dictionary mapping variable indices to fixed values (0 or 1)

Type:: Dict[int, int]

free

Set of variable indices left free

Type:: Set[int]

n_vars

Original number of variables

Type:: int

fixed: Dict[int, int]

free: Set[int]

n_vars: int

property p: float: Probability parameter (fraction of free variables).

__init__(fixed: Dict[int, int], free: Set[int], n_vars: int) → None

boofun.analysis.restrictions.random_restriction(n: int, p: float, rng: Generator | None = None) → Restriction[source]

Generate a random p-restriction on n variables.

Each variable is independently: - Fixed to 0 with probability (1-p)/2 - Fixed to 1 with probability (1-p)/2 - Left free (*) with probability p

Parameters:

n – Number of variables
p – Probability of leaving a variable free
rng – Random number generator

Returns:

Random Restriction object

Example

>>> rho = random_restriction(10, 0.3)
>>> len(rho.free)  # Approximately 3 variables

boofun.analysis.restrictions.apply_restriction(f: BooleanFunction, rho: Restriction) → BooleanFunction[source]

Apply a restriction to a Boolean function.

The restricted function f|_ρ is defined only on the free variables. Fixed variables are replaced by their assigned values.

Parameters:

f – BooleanFunction to restrict
rho – Restriction to apply

Returns:

Restricted BooleanFunction on the free variables

Note

The resulting function has fewer variables (only the free ones).

boofun.analysis.restrictions.restriction_shrinkage(f: BooleanFunction, p: float, num_samples: int = 100, rng: np.random.Generator | None = None) → Dict[str, float][source]

Estimate how much random restrictions shrink various complexity measures.

This is key to understanding DNF/decision tree complexity: - Random restrictions simplify functions - After restriction, DNFs become decision trees of small depth

Parameters:

f – BooleanFunction to analyze
p – Probability parameter for restrictions
num_samples – Number of random restrictions to sample
rng – Random number generator

Returns:

Dictionary with statistics about shrinkage

boofun.analysis.restrictions.average_restricted_decision_tree_depth(f: BooleanFunction, p: float, num_samples: int = 100, rng: np.random.Generator | None = None) → float[source]

Estimate expected decision tree depth after random p-restriction.

From O’Donnell Chapter 4: For width-w DNFs, after a p-restriction, the expected decision tree depth is O(log(1/p) * p^w).

Parameters:

f – BooleanFunction to analyze
p – Restriction probability
num_samples – Number of samples for estimation
rng – Random number generator

Returns:

Estimated expected decision tree depth after restriction

boofun.analysis.restrictions.switching_lemma_probability(width: int, p: float, depth_threshold: int) → float[source]

Estimate probability bound from the Switching Lemma.

The Switching Lemma (Håstad) states that for a width-w DNF f, after a random p-restriction:

Pr[DT-depth(f|_ρ) > s] ≤ (5pw)^s

Parameters:

width – Width of the DNF (max clause size)
p – Restriction probability
depth_threshold – Depth threshold s

Returns:

Upper bound on probability that restricted DT-depth exceeds threshold

Note

This is the theoretical bound, not empirical measurement.

boofun.analysis.restrictions.batch_random_restrictions(n: int, p: float, num_restrictions: int, rng: Generator | None = None) → List[Restriction][source]

Generate multiple random restrictions.

Parameters:

n – Number of variables
p – Probability of leaving variable free
num_restrictions – Number of restrictions to generate
rng – Random number generator

Returns:

List of Restriction objects

boofun.analysis.restrictions.restriction_to_inputs(rho: Restriction, num_inputs: int | None = None) → List[int][source]

Generate all inputs consistent with a restriction.

For a restriction ρ, returns all x such that x agrees with ρ on fixed vars.

Parameters:

rho – Restriction to expand
num_inputs – Maximum number of inputs to return (None = all)

Returns:

List of input indices (as integers)

boofun.analysis.restrictions.min_fixing_to_constant(f: BooleanFunction, target_value: int = 1, rng: np.random.Generator | None = None) → Dict[int, int] | None[source]

Find a minimum set of variable assignments that fixes f to a constant.

This implements Tal’s min_fixing algorithm: find the smallest partial assignment that makes f constant (always 0 or always 1).

Parameters:

f – BooleanFunction to analyze
target_value – Target constant value (0 or 1)
rng – Random number generator (for tie-breaking)

Returns:

value} of minimum fixing, or None if impossible

Return type:

Dictionary {var_index

Note

This is related to certificate complexity. The size of the minimum fixing to 1 is the 1-certificate complexity at the all-zeros input.

Reference:: Tal’s library: min_fixing(go_up) function

boofun.analysis.restrictions.shift_by_mask(f: BooleanFunction, mask: int) → BooleanFunction[source]

Shift a Boolean function by XORing all inputs with a mask.

Returns g where g(x) = f(x ⊕ mask).

This is useful for: - Converting between different input conventions - Finding monotone representations - Analyzing function structure under affine transformations

Parameters:

f – BooleanFunction to shift
mask – Integer mask to XOR with inputs

Returns:

Shifted BooleanFunction

Reference:: Tal’s library: shift(sh) function