Library Comparison

How BooFun compares to other Boolean function libraries.

Summary

BooFun focuses on theoretical computer science: Fourier analysis (O’Donnell style), property testing, query complexity. Other libraries have different strengths.

Library	Focus	Fourier	Property Testing	Query Complexity
BooFun	TCS theory	✓	✓	✓
SageMath	Cryptography	Walsh only	✗	✗
pyeda	Logic/SAT/BDD	✗	✗	✗
BoolForge	Biology	✗	✗	✗
CANA	Network control	✗	✗	✗

What BooFun Has

Query Complexity (based on Aaronson’s Boolean Function Wizard):

• Deterministic: D(f), D_avg(f)

• Randomized: R₀(f), R₁(f), R₂(f), nondeterministic variants

• Quantum: Q₂(f), QE(f), nondeterministic variants

• Sensitivity: s(f), bs(f), es(f) (everywhere sensitivity)

• Certificates: C(f), C₀(f), C₁(f)

• Lower bounds: Ambainis, spectral adversary, polynomial method, general adversary

• Degree measures: exact, approximate, threshold, nondeterministic

Property Testing:

• BLR linearity

• Junta testing

• Monotonicity, unateness, symmetry

Fourier Analysis:

• Influences, total influence

• Noise stability

• Spectral weight by degree

• KKL theorem bounds

Quantum (theoretical estimation only):

• Grover speedup

• Quantum walk analysis

What BooFun Lacks

Features better served by other libraries:

• Cryptographic analysis (bent, correlation immunity) → SageMath

• SAT solving, BDD operations → pyeda

• Boolean networks, attractors → BoolForge

• Network control theory → CANA

• Canalization analysis → BoolForge/CANA

Comparison Tables

Fourier Analysis

Feature	BooFun	SageMath
Walsh-Hadamard	✓	✓
Influences	✓	✗
Total influence	✓	✗
Noise stability	✓	✗
Bent functions	✗	✓
Correlation immunity	✗	✓

Different focus: BooFun follows O’Donnell; SageMath focuses on cryptographic properties.

Property Testing

Test	BooFun	BoolForge
Linearity (BLR)	✓	✗
Junta	✓	✗
Monotonicity	✓ (probabilistic)	✓ (exact)
Dictator proximity	✓	✗

Representations

Format	BooFun	pyeda
Truth table	✓	✓
BDD	✓ (basic)	✓ (full ROBDD)
CNF/DNF	✓	✓
Fourier	✓	✗

pyeda’s BDD implementation is more mature.

When to Use What

BooFun:

• Studying Boolean function theory (O’Donnell book)

• Query complexity research

• Property testing algorithms

• Influence/noise stability analysis

SageMath:

• Cryptographic analysis

• Bent functions, nonlinearity

pyeda:

• SAT solving

• BDD manipulation

• Logic minimization

BoolForge:

• Gene regulatory networks

• Canalization

CANA:

• Network control theory

Cross-Validation

We’ve validated against known results where possible:

• Parseval’s identity

• Majority function influences (compare to theoretical √(2/πn))

• Parity function properties

See tests/test_cross_validation.py for details. Not everything has been cross-validated.

Installation

pip install git+https://github.com/GabbyTab/boofun  # BooFun
pip install git+https://github.com/ckadelka/BoolForge  # BoolForge
pip install cana  # CANA
pip install pyeda  # pyeda

Prior Art

BooFun’s query complexity module builds on:

• Scott Aaronson’s Boolean Function Wizard (2000): C implementation of D(f), R(f), Q(f), sensitivity, block sensitivity, certificate complexity, approximate degrees. See Aaronson, “Algorithms for Boolean Function Query Measures.”

• Avishay Tal’s library: Python implementation of Fourier transforms, sensitivity, decision trees, polynomial representations over F₂ and reals.

These tools inspired BooFun’s design but were either no longer maintained or not publicly distributed. BooFun aims to provide a modern, documented, tested implementation of these ideas.

References

• Aaronson, S. (2000). “Algorithms for Boolean Function Query Measures.”

• O’Donnell, R. (2014). Analysis of Boolean Functions. Cambridge.

• Buhrman, H. & de Wolf, R. (2002). “Complexity Measures and Decision Tree Complexity.”

• Correia et al. (2018). CANA. Frontiers in Physiology.