boofun 1.1.1

A Python library for Boolean function analysis and spectral methods

Boolean Function Analysis in Python

What This Is

A toolkit for Boolean function analysis: Fourier analysis, property testing, query complexity, and more. Built while studying O'Donnell's Analysis of Boolean Functions.

Full Documentation · Quick Start

Installation

pip install boofun

Quick Start

import boofun as bf

# Create functions
maj = bf.majority(5)
xor = bf.create([0, 1, 1, 0])

# Evaluate
maj.evaluate([1, 1, 0, 0, 1])  # → 1

# Fourier analysis
maj.fourier()           # Fourier coefficients
maj.influences()        # Per-variable influences
maj.total_influence()   # I[f]
maj.noise_stability(0.9)

# Properties and complexity
maj.is_monotone()
maj.is_balanced()

from boofun.analysis import complexity
complexity.decision_tree_depth(maj)  # D(f)
complexity.max_sensitivity(maj)      # s(f)

# Full analysis
maj.analyze()  # dict with all metrics

Features

Category	What's Included
Built-in Functions	Majority, Parity, AND, OR, Tribes, Threshold, Dictator, weighted LTF, random
Representations	Truth tables (dense/sparse/packed), Fourier, ANF, DNF/CNF, BDD, circuits, LTF
Fourier Analysis	WHT, influences, noise stability, spectral concentration, p-biased analysis
Query Complexity	D(f), R(f), Q(f), sensitivity, block sensitivity, certificates, Ambainis bound
Property Testing	BLR linearity, junta, monotonicity, symmetry, balance
Hypercontractivity	Noise operator, Bonami's Lemma, KKL theorem, Friedgut's junta theorem
Learning Theory	Goldreich-Levin, PAC learning, junta learning, LMN algorithm
Cryptographic	Nonlinearity, bent functions, Walsh spectrum, LAT/DDT, S-box analysis
Advanced	Gaussian analysis, invariance principle, communication complexity, LTF analysis
Visualization	Influence plots, Fourier spectrum, truth table heatmaps, decision trees

Guides

Detailed documentation for each topic:

• Spectral Analysis: Fourier, influences, p-biased, sensitivity, sampling
• Query Complexity: D/R/Q, certificates, decision trees, Huang's theorem
• Hypercontractivity: KKL, Bonami, Friedgut, global hypercontractivity
• Learning Theory: Goldreich-Levin, PAC learning, junta learning, LMN
• Cryptographic Analysis: Nonlinearity, bent, LAT/DDT, S-box
• Representations: All formats, conversion graph, storage hints
• Operations: Boolean operators, composition, restriction, permutation
• Advanced Topics: Gaussian, invariance, communication complexity, LTF, restrictions

Flexible Input

bf.create([0, 1, 1, 0])              # List → truth table
bf.create(lambda x: x[0] ^ x[1], n=2) # Callable
bf.create("x0 and not x1", n=2)      # String → symbolic
bf.load("function.cnf")              # DIMACS CNF

Built-in Functions

majority(n), parity(n), tribes(k, n), threshold(n, k), AND(n), OR(n), dictator(n, i), weighted_majority(weights), random(n)

Examples

File	Topic
01_getting_started.py	Basics
02_fourier_basics.py	WHT, Parseval
03_common_families.py	Majority, Parity, Tribes
04_property_testing.py	BLR, junta tests
05_query_complexity.py	Sensitivity, certificates

Course Notebooks

Interactive notebooks following CS294-92 (Analysis of Boolean Functions). Click Topic to view or Play to run in Colab.

Lecture Notebooks (11)

Lecture	Topic	Play
1	Fourier Expansion
2	Linearity Testing
3	Social Choice & Influences
4	Influences & Effects
5	Noise Stability
6	Spectral Concentration
7	Goldreich-Levin
8	Learning Juntas
9	DNFs & Restrictions
10	Fourier Concentration
11	Invariance Principle

Homework Notebooks (4)

HW	Topic	Play
1	Fourier Expansion
2	LTFs & Decision Trees
3	DNFs & Restrictions
4	Hypercontractivity

Performance

• NumPy vectorization throughout
• Optional Numba JIT, CuPy GPU acceleration
• Sparse/packed representations for large n
• Most operations complete in milliseconds for n ≤ 14

Testing

pytest tests/
pytest --cov=boofun tests/

3000+ tests with 72% coverage. Cross-validation against known results in tests/test_cross_validation.py.

Convention

O'Donnell standard: Boolean 0 → +1, Boolean 1 → −1. This ensures f̂(∅) = E[f].

Contributing

See CONTRIBUTING.md. Bug reports and test cases are especially valuable.

Acknowledgments

• Avishay Tal: Course instructor, sensitivity analysis, p-biased measures, decision tree algorithms
• Patrick Bales: Course materials and notebook review
• O'Donnell's Analysis of Boolean Functions (Cambridge, 2014): Theoretical foundation
• Scott Aaronson's Boolean Function Wizard (2000): Query complexity foundations

License

MIT. See LICENSE.

Citation

@software{boofun2026,
  title={BooFun: A Python Library for Boolean Function Analysis},
  author={Gabriel Taboada},
  year={2026},
  url={https://github.com/GabbyTab/boofun}
}