boofun.core.builtins

Classes

BooleanFunctionBuiltins()

Collection of standard Boolean functions used in research and testing.

class boofun.core.builtins.BooleanFunctionBuiltins

Collection of standard Boolean functions used in research and testing.

classmethod majority(n: int) → BooleanFunction

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

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

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

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

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

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)