Boofun
A toolkit for teaching, learning, and doing research in Boolean function analysis. Fourier analysis, property testing, query complexity, hypercontractivity, pseudorandomness, and more
Install / Use
/learn @GabbyTab/BoofunREADME
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, Tal's toolkit, and known closed-form results.
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, 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
- 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.
<details> <summary><strong>Lecture Notebooks (11)</strong></summary>| 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 | [