Source-linked AI summary
Analysis of Boolean Functions
Li-Yang Tan
TL;DR
The notes ask how Fourier structure, testing, expansion, and noise stability illuminate Boolean functions and their applications. They develop Fourier-analytic and probabilistic tools, including BLR testing and noise-stability arguments, and report hardness and robust social-choice conclusions. The material also records scope boundaries concerning F2 degree and the impartial-culture assumption.
Problem
The notes address how Boolean-function structure can support analysis of property testing, voting, pseudorandomness, Gaussian geometry, and hardness of approximation.
Method
They represent Boolean functions through Fourier expansions and use hybrid, noise-operator, and stability arguments to analyze testing, expansion, and aggregation.
Results
Approximating MAX-3NAE-SAT to a factor of 0.91226 . . . + ε is NP-hard, while robust Arrow analysis links mostly rational aggregation to functions close to dictators or anti-dictators.
Takeaways & Limitations
Fourier and noise-stability viewpoints unify results about testing, small-set expansion, voting, and hardness within Boolean-function analysis.
Takeaways & Limitations
The notes state that F2 degree cannot be inferred from a Boolean function's Fourier expansion and use impartial culture, with voters choosing independently and uniformly, for Arrow analysis.
Abstract
from arXiv · showhide
Scribe notes from the 2012 Barbados Workshop on Computational Complexity. A series of lectures on Analysis of Boolean Functions by Ryan O'Donnell, with a guest lecture by Per Austrin.
1 Linearity testing and Arrow’s theorem
These notes develop Fourier-analytic tools for Boolean functions and apply them to linearity testing, influence, noise stability, and voting. They show that BLR acceptance implies closeness to a linear function, while robust Arrow results connect rational aggregation to dictatorships.
- Foundations: Analysis of Boolean functions studies Boolean functions as multilinear polynomials and applies their structure to testing, voting, pseudorandomness, Gaussian geometry, and hardness of approximation.Recurring themes include small-set expansion of the noisy hypercube and decomposition into junta and Gaussian parts.
- Fourier expansion: Every real-valued function on the Boolean cube has a unique Fourier expansion in parity functions, and Fourier degree is the largest nonzero parity-set size.The parity functions form an orthonormal basis, so coefficients encode the function's representation.
- Fourier expansion: Fourier coefficients recover basic combinatorial quantities: the constant coefficient gives the mean, while the nonconstant squared coefficients determine variance and influence-related bounds.For Boolean functions, variance is 4·Pr[f(x)=1]·Pr[f(x)=-1], and the Poincaré inequality gives Var(f) ≤ Inf(f).
- Linearity testing: If BLR accepts f with probability at least 1−ε, then f is ε-close to a linear parity function χS*; approximate linearity notions are consequently equivalent under the test.The proof identifies a Fourier coefficient at least 1−2ε and converts it into Hamming distance at most ε.
- Voting and influence: MAJ maximizes the sum of first-level Fourier coefficients among Boolean functions, and for monotone functions this yields an upper bound on total influence.Influence also has a Fourier expression, connecting voting power to low-degree coefficients.
- Noise stability and Arrow’s theorem: Robust Arrow theory expresses rational aggregation under impartial culture through noise stability and concludes that near-universal rationality forces the aggregator close to a dictator or anti-dictator.Exact rational aggregation already implies ±DICTi, while the robust statement gives O(ε)-closeness when irrational outcomes occur with probability at most ε.
2 Noise stability and small set expansion
Noise stability measures how often correlated inputs remain jointly in a set, while hypercontractivity and Gaussian limits yield small-set expansion and influence bounds. These tools connect Fourier structure to threshold-function behavior.
- Gaussian comparison: Sheppard’s formula gives Pr[sgn(G) ≠ sgn(H)] = arccos(ρ)/π for ρ-correlated Gaussians.This Gaussian sign comparison supports asymptotic analyses of majority and noise stability.
- Noise stability: The ρ-noisy hypercube assigns edge weights according to pairs of ρ-correlated Boolean strings, interpreting stability as weight retained inside a set.For an indicator 1_A, Stab_ρ(1_A) equals the probability that both correlated samples lie in A.
- Small Set Expansion: Small Set Expansion bounds Stab_ρ(1_A) by α^2/(1+ρ), equivalently making conditional retention at most α^(1−ρ)/(1+ρ).For small-density sets, the corresponding random walk leaves the set with very high probability.
- Fourier consequences: The level-1 inequality gives W1(f) = O(α^2 ln(1/α)) for Boolean indicators of density α.A dual statement relates sufficiently large first-level Fourier weight to closeness to a linear threshold function.
- Hypercontractivity: Bonami hypercontractivity shows that degree-d multilinear Rademacher polynomials satisfy E[f^4] ≤ 9^d · E[f^2]^2.The proof proceeds by induction on the number of variables using the decomposition f = g + x_n h.
3 KKL and quasirandomness
The KKL theorem forces a balanced Boolean function to have a variable with logarithmically large influence, while noisy influences control quasirandomness and dictatorship tests. These results support tests with explicit completeness and soundness guarantees.
- KKL: KKL states that a balanced Boolean function with maximum influence α has total influence Ω(log(1/α)).Equivalently, the maximum influence is bounded below logarithmically in the number of variables, and the bound is tight for TRIBES.
- KKL: The TRIBES function matches the maximum-influence bound, although the resulting log(n) improvement over the Poincaré bound can be crucial in applications.The notes identify Khot and Vishnoi’s counterexample to the Goemans–Linial conjecture as one such application.
- Noisy influence: If Var(f) ≤ 1, at most 1/(εδ) coordinates can have noisy influence at least ε.This bounds the number of coordinates that remain significant after noise smoothing.
- Dictator testing: Combining NAE and BLR tests yields a 6-query dictatorship test with perfect completeness and soundness 1 − Ω(ε), reducible to 3 queries with constant-factor rejection loss.The NAE test rules out much of the non-dictator structure, while BLR addresses functions close to anti-dictators.
- Dictator versus quasirandom tests: For hardness-of-approximation applications, distinguishing dictators from (ε, ε)-quasirandom functions can suffice instead of testing distance from dictators.The notes present this weaker target as sufficient for UGC-hardness applications.
- Dictator versus quasirandom tests: The NAE test is a (1, 0.91226 . . .) dictator-versus-quasirandom test under the oddness promise.The framework uses O(1) non-adaptive queries and distinguishes dictators from (ε, ε)-quasirandom functions.
4 CSPs and hardness of approximation
The section connects dictator-versus-quasirandom tests to weighted CSPs and Unique-Label-Cover reductions, yielding UGC-based hardness results. It also develops Berry–Esséen bounds through smoothing and hybrid replacement arguments.
- CSP formulation: A string tester is equivalent to a weighted CSP whose variables are truth-table bits, predicates are constraints, and query probabilities are weights.Maximizing the tester’s acceptance probability becomes finding an assignment satisfying the largest weighted fraction of constraints.
- Dictator tests: An explicit (c, s) dictator-versus-quasirandom test induces a weighted CSP with special dictator assignments, while quasirandom assignments suggest none of their coordinates.Assignments achieving at least s+Ω(1) satisfaction must be slightly suggestive of one of the dictator assignments.
- UGC hardness: Under the UGC, an explicit (c, s) dictator-versus-quasirandom test implies NP-hardness of ((s/c) + ε)-factor approximation for CSPs using its predicates.The formal connection runs through Unique-Label-Cover and the reduction stated in Theorem 53.
- Berry–Esséen: Berry–Esséen is proved with a hybrid argument replacing independent variables by Gaussians one at a time, using matching first and second moments and Taylor error bounds.Threshold indicators are first replaced by smooth approximators with bounded fourth derivative.
- Berry–Esséen: Taking λ = (Bτ)^1/5 yields the weak Berry–Esséen bound |Pr[S < t] − Pr[G < t]| = O(Bτ/λ^4) + O(λ).The result applies to independent B-reasonable, mean-zero variables under the proposition’s variance and moment conditions.
5 Majority Is Stablest
The section develops Gaussian noise stability, rotation sensitivity, and the invariance principle underlying Majority Is Stablest. Borell’s inequality identifies halfspaces as extremal, while low-influence Boolean polynomials transfer to Gaussian space.
- Gaussian stability: Gaussian noise stability is defined using ρ-correlated Gaussian inputs and agrees with Boolean noise stability for multilinear polynomials.The equality follows by expanding the polynomial and using coordinate independence and E[GiHi] = ρ.
- Borell’s inequality: For balanced Gaussian Boolean functions, Borell’s theorem upper-bounds noise stability, with equality for halfspaces through the origin.The theorem is presented as a Gaussian isoperimetric statement, and the halfspace case is tight.
- Rotation sensitivity: Rotation sensitivity measures the probability that a Gaussian vector and its cos(δ)-correlated noisy copy receive different values, serving as a boundary-size measure.For sufficiently nice sets, its small-δ scaling is within a constant factor of Gaussian surface area.
- Borell’s inequality: Borell’s theorem equivalently gives a lower bound on rotation sensitivity for balanced functions, and halfspaces attain the corresponding bound via Sheppard’s formula.The supplied passages state the boundary interpretation and the halfspace comparison.
- Majority Is Stablest: The Majority Is Stablest theorem states that balanced Boolean functions with all influences at most ε have noise stability at most the Gaussian halfspace bound.Its proof outline smooths the function, truncates to low degree, applies invariance, and then truncates back to [−1, 1].
- The invariance principle: The invariance principle compares threshold probabilities of low-degree multilinear polynomials under independent Rademacher and Gaussian inputs.Its proof uses a low-degree hybrid replacement, extending the Berry–Esséen strategy; smoothing is needed for test functions with bounded fourth derivatives.
6 Testing dictators and UGC-hardness
The section formalizes how dictator-versus-quasirandom tests yield CSP hardness through Unique-Label-Cover reductions. Dictator assignments give completeness, while test soundness recovers a labeling from any sufficiently good CSP assignment.
- Unique-Label-Cover: Unique-Label-Cover assigns labels to vertices subject to edge permutations, and the Unique Games Conjecture posits hardness of distinguishing almost-satisfiable from highly unsatisfiable instances.The conjecture states NP-hardness of distinguishing opt(Ψ) ≥ 1−ε from opt(Ψ) < ε for a suitable label count L.
- Reduction: The reduction maps an L-Unique-Label-Cover instance to MAX-CSP(T) with |V|·2^L Boolean variables, one truth-table block for each vertex.Constraints sample a vertex, neighboring vertices, and tester-induced tuples, then apply the corresponding edge permutations.
- Reduction: Predicates extend from Boolean inputs to bounded functions through their multilinear expectation extension, allowing dictator-versus-quasirandom tests to operate on [−1, 1]-valued functions.The extension agrees with the original predicate on Boolean inputs and returns acceptance probabilities in [0, 1].
- Completeness: If opt(Ψ) ≥ 1−δ, dictator assignments yield opt(R(Ψ)) ≥ c·(1−kδ) ≥ c−ε for sufficiently small δ.This uses the fact that all k sampled incident edges are satisfied with probability at least 1−kδ and the test accepts the corresponding dictator with probability at least c.
- Soundness: If the CSP optimum is at least s+ε, averaging and test soundness produce many vertices whose associated functions have a coordinate with noticeably large influence.These suggestive coordinates are then used to construct a labeling satisfying an Ωε(1) fraction of edges.