Boolean Function Analysis in Python

What This Is

A toolkit for teaching, learning, and doing research in Boolean function analysis. Fourier analysis, property testing, query complexity, hypercontractivity, pseudorandomness, and more -- with 25 interactive notebooks aligned to O'Donnell's Analysis of Boolean Functions.

Built at UC Berkeley alongside Avishay Tal's CS 294-92. Cross-validated against SageMath (version-pinned fixtures), BoolForge (live CI job), published literature values, and known closed-form results — every claim, version, and tolerance is recorded in the claim matrix.

import boofun as bf

# Create functions, compute properties
maj = bf.majority(5)
maj.fourier()           # Fourier coefficients
maj.influences()        # Per-variable influences
maj.total_influence()   # I[f]
maj.noise_stability(0.9)

# Query complexity
from boofun.analysis import complexity
complexity.D(maj)       # Decision tree depth
complexity.s(maj)       # Max sensitivity

Full Docs | All 25 Notebooks | Try it in Colab

Installation

pip install boofun

Or run notebooks in Docker:

docker-compose up notebook  # localhost:8888, token: boofun

Quick Start

import boofun as bf

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

# Evaluate (callable syntax)
maj_5([1, 1, 0, 0, 1])  # → True (majority satisfied)
maj_5(7)                # → True (7 = 00111 in binary, 3 ones)

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

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

from boofun.analysis import complexity
complexity.D(maj_5)  # Decision tree depth D(f)
complexity.s(maj_5)  # Max sensitivity s(f)

# Full analysis
maj_5.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, LP-exact degree measures, certified adversary lower bounds
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
• Probabilistic View: Random variables, p-biased measures, estimation, pseudorandomness
• 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

Computational companion to O'Donnell's Analysis of Boolean Functions, following Avishay Tal's CS 294-92. Each notebook makes the theorems runnable so the focus stays on the math. Click Scribe for lecture notes, Topic to view the static notebook, or Play to run in Colab.

Lecture Notebooks (11)

Lecture	Scribe	Topic	Play
1	Joyce Lu	Fourier Expansion
2	Austin Pechan	Linearity Testing
3	Vivien Goyal	Social Choice & Influences
4	Patrick Bales	Influences & Effects
5	Prastik Mohanraj	Noise Stability
6	(upcoming)	Spectral Concentration
7	Thomas Culhane	Goldreich-Levin
8	Timothe Kasriel	Learning Juntas
9	Qinggao Hong	DNFs & Restrictions
10	Lucas Ericsson	Fourier Concentration
11	Thapen	Invariance Principle

Homework Notebooks (4)

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

Supplementary Notebooks (10)

Topic	Description	Play
LTF Visualization	3D hyperplane geometry, influences
Global Hypercontractivity	Keevash et al. threshold phenomena
Boolean Functions as Random Variables	P-biased measures, threshold curves, Russo
Cryptographic Analysis	Walsh spectrum, nonlinearity, SAC
Fractional PRGs	Fourier tails, pseudorandomness (CHLT 2019)
Flexible Inputs & Oracles	Input formats, lazy evaluation
Real World Applications	Cryptography, ML, voting
Asymptotic Visualization	Growth rates and scaling
Error Models	PAC, noise, linear error models
GPU Performance	GPU-accelerated WHT, influences (Colab GPU)

Performance

• NumPy vectorization throughout (always on)
• Numba JIT for 2-10x speedups: pip install boofun[performance]
• CuPy GPU acceleration for large n: pip install boofun[gpu]
• Sparse/packed representations for memory efficiency
• Most operations complete in milliseconds for n ≤ 14

Testing

pytest tests/
pytest --cov=boofun tests/

3,800+ tests with ~79% line-and-branch coverage, enforced as a CI gate alongside strict mypy (zero errors, no baseline) and a zero-warning Ruff profile. Cross-validation against pinned external references in tests/cross_validation/ (see the claim matrix).

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, and issues labeled good first issue are a good place to start. The roadmap lives on the issue tracker.

Questions? See SUPPORT.md for where to ask and what to expect.

Acknowledgments

• Avishay Tal: Course instructor, sensitivity analysis, p-biased measures, decision tree algorithms, Fourier analysis utilities. BooFun covers ~90% of Tal's BooleanFunc.py toolkit - see the migration guide for a complete mapping
• 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

Citation metadata lives in CITATION.cff (use the "Cite this repository" button on GitHub), or use:

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