boofun.families.builtins

Built-in function families with known asymptotic behavior.

Each family has: - Generation for any valid n - Known theoretical formulas for key properties - Universal properties that always hold

Classes

ANDFamily()	AND function family: AND_n(x) = 1 iff all x_i = 1.
DictatorFamily([variable])	Dictator function family: DICT_i(x) = x_i.
IteratedMajorityFamily([group_size])	Iterated Majority function family.
LTFFamily(weight_pattern, int], float] = >, ...)	General LTF (Linear Threshold Function) family.
MajorityFamily()	Majority function family: MAJ_n(x) = 1 if Σx_i > n/2.
ORFamily()	OR function family: OR_n(x) = 1 iff at least one x_i = 1.
ParityFamily()	Parity/XOR function family: XOR_n(x) = Σx_i mod 2.
RandomDNFFamily([term_width, num_terms])	Random DNF (Disjunctive Normal Form) function family.
RecursiveMajority3Family()	Recursive Majority of 3 function family.
SboxFamily([sbox, bit])	Cryptographic S-box component function family.
ThresholdFamily([k_function])	Threshold function family: THR_k(x) = 1 if Σx_i ≥ k.
TribesFamily()	Tribes function family: Balanced DNF with k tribes of size s.

class boofun.families.builtins.MajorityFamily

Majority function family: MAJ_n(x) = 1 if Σx_i > n/2.

Well-known asymptotics: - Total influence: I[MAJ_n] ≈ √(2/π) · √n ≈ 0.798√n - Each influence: Inf_i[MAJ_n] ≈ √(2/(πn)) - Noise stability: Stab_ρ[MAJ_n] → (1/2) + (1/π)arcsin(ρ) - Fourier degree: n (but most weight on lower degrees)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

validate_n(n: int) → bool

Check if n is valid for this family.

class boofun.families.builtins.ParityFamily

Parity/XOR function family: XOR_n(x) = Σx_i mod 2.

Parity is the “opposite” of Majority in many ways: - NOT an LTF (not linearly separable) - All Fourier weight on a single coefficient - Maximum noise sensitivity

Asymptotics: - Total influence: I[XOR_n] = n (each variable is pivotal always) - Noise stability: Stab_ρ[XOR_n] = ρ^n → 0 for ρ < 1 - Fourier: f̂(S) = 1 only for S = [n], else 0

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.TribesFamily

Tribes function family: Balanced DNF with k tribes of size s.

Standard choice: s = log(n) - log(log(n)) for k = n/s tribes. This achieves Pr[TRIBES = 1] ≈ 1/2.

Asymptotics: - Total influence: I[TRIBES] ≈ log(n)/n · n = log(n) - Each influence: Inf_i[TRIBES] ≈ log(n)/n - Noise stability: Complex, depends on parameters

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, k: int | None = None, w: int | None = None, **kwargs) → BooleanFunction

Generate tribes function.

Parameters:

• n – Total number of variables

• k – Number of tribes (optional, auto-computed if not provided)

• w – Width of each tribe (optional, auto-computed if not provided)

Note: bf.tribes(tribe_size, total_vars) so we call bf.tribes(w, n)

class boofun.families.builtins.ThresholdFamily(k_function: Callable[[int], int] | None = None)

Threshold function family: THR_k(x) = 1 if Σx_i ≥ k.

This is a symmetric LTF (uniform weights).

Special cases: - k = 1: OR function - k = n: AND function - k = (n+1)/2: Majority (for odd n)

__init__(k_function: Callable[[int], int] | None = None)

Initialize threshold family.

Parameters:

k_function – Function n -> k specifying threshold for each n. Default: k = n//2 + 1 (majority-like)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, k: int | None = None, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.ANDFamily

AND function family: AND_n(x) = 1 iff all x_i = 1.

Extreme threshold function (k = n).

Asymptotics: - Total influence: I[AND_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[AND_n] = 2^{-(n-1)} - Pr[AND_n = 1] = 2^{-n}

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.ORFamily

OR function family: OR_n(x) = 1 iff at least one x_i = 1.

Extreme threshold function (k = 1). Dual of AND: OR_n(x) = ¬AND_n(¬x).

Asymptotics: - Total influence: I[OR_n] = n · 2^{-(n-1)} → 0 - Each influence: Inf_i[OR_n] = 2^{-(n-1)} - Pr[OR_n = 1] = 1 - 2^{-n}

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.DictatorFamily(variable: int = 0)

Dictator function family: DICT_i(x) = x_i.

The “simplest” Boolean function - just returns one variable.

Asymptotics: - Total influence: I[DICT] = 1 (only one influential variable) - Inf_i[DICT] = 1, Inf_j[DICT] = 0 for j ≠ i - Noise stability: Stab_ρ[DICT] = ρ

__init__(variable: int = 0)

Initialize dictator family.

Parameters:

variable – Which variable to use (default: 0)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.LTFFamily(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')

General LTF (Linear Threshold Function) family.

LTF_w(x) = sign(w₁x₁ + … + wₙxₙ - θ)

This is a more flexible version of WeightPatternFamily with additional convenience methods.

__init__(weight_pattern: ~typing.Callable[[int, int], float] = <function LTFFamily.<lambda>>, threshold_pattern: ~typing.Callable[[int], float] | None = None, name: str = 'LTF')

Initialize LTF family.

Parameters:

• weight_pattern – Function (i, n) -> weight of variable i

• threshold_pattern – Function n -> threshold

• name – Family name

property metadata: FamilyMetadata

Return metadata about this family.

classmethod uniform(name: str = 'UniformLTF') → LTFFamily

Create LTF with uniform weights (= Majority).

classmethod geometric(ratio: float = 0.5, name: str = 'GeometricLTF') → LTFFamily

Create LTF with geometrically decaying weights.

classmethod harmonic(name: str = 'HarmonicLTF') → LTFFamily

Create LTF with harmonic weights 1/(i+1).

classmethod power_law(power: float = 2.0, name: str = 'PowerLTF') → LTFFamily

Create LTF with power-law weights.

class boofun.families.builtins.RecursiveMajority3Family

Recursive Majority of 3 function family.

REC_MAJ3 on n = 3^k variables is defined recursively: - Base case: n=3 is MAJ_3 - Recursive: REC_MAJ3(x) = MAJ_3(REC_MAJ3(x[0:m]), REC_MAJ3(x[m:2m]), REC_MAJ3(x[2m:3m]))

This is a key function in complexity theory, with interesting properties: - Total influence: I[REC_MAJ3] = Θ(n^(log_3(2))) ≈ n^0.631 - More “noise sensitive” than flat majority - Used in lower bounds for branching programs

Note: Only defined for n = 3^k (k ≥ 1).

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate recursive majority of 3 function.

theoretical_properties(n: int) → dict

Return known theoretical properties.

class boofun.families.builtins.IteratedMajorityFamily(group_size: int = 3)

Iterated Majority function family.

ITER_MAJ builds majority functions in layers: - Layer 0: n input variables - Layer i: majority of groups from layer i-1 - Continue until single output

Different from RecursiveMajority3 which specifically uses groups of 3. This allows general group sizes.

__init__(group_size: int = 3)

Initialize iterated majority.

Parameters:

group_size – Size of each majority group (must be odd)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

validate_n(n: int) → bool

Check if n is valid for this family.

class boofun.families.builtins.RandomDNFFamily(term_width: int = 3, num_terms: int | None = None)

Random DNF (Disjunctive Normal Form) function family.

Generates random k-DNF functions with m terms.

A k-DNF is an OR of terms, where each term is an AND of at most k literals.

__init__(term_width: int = 3, num_terms: int | None = None)

Initialize random DNF family.

Parameters:

• term_width – Maximum number of literals per term (k)

• num_terms – Number of terms (default: 2^{n/2})

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int, seed: int | None = None, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

class boofun.families.builtins.SboxFamily(sbox: List[int] | None = None, bit: int = 0)

Cryptographic S-box component function family.

S-boxes are nonlinear components in block ciphers. This family provides access to standard S-boxes and their component Boolean functions.

AES_SBOX = [99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22]

__init__(sbox: List[int] | None = None, bit: int = 0)

Initialize S-box family.

Parameters:

• sbox – Custom S-box (default: AES S-box)

• bit – Output bit to extract (0-7 for 8-bit S-box)

property metadata: FamilyMetadata

Return metadata about this family.

generate(n: int = None, **kwargs) → BooleanFunction

Generate the function for n variables.

Parameters:

• n – Number of variables

• **kwargs – Additional family-specific parameters

Returns:

BooleanFunction instance

get_component(bit: int) → BooleanFunction

Get specific bit component.

all_components() → List[BooleanFunction]

Get all component functions.

classmethod aes(bit: int = 0) → SboxFamily

Create AES S-box family.

validate_n(n: int) → bool

Check if n is valid for this family.