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.
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.
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)

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

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

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]

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

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

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.