REVIEW 7 cited by
Analysis of Boolean Functions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : \{0,1\}^n \to \{0,1\}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a "highlight" showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the book's chapters.
Forward citations
Cited by 7 Pith papers
-
Pessimal Elections for Approximately Dominating Sets
For every ε>0 there exists an election in which every approximately dominating committee has size at least about 1/(32π ε^2), matching the known upper bound up to a constant factor.
-
Hardness of Learning Fixed Parities with Neural Networks
Any fixed parity of size at least logarithmic in the dimension requires exponentially many perturbed-gradient steps before the expected correlation loss moves away from its trivial value.
-
State $k$-designs from Hamiltonian evolution
Under time evolution with a fixed Hamiltonian, a state 1-design of initial states grows into an approximate state k-design, with a proven recursion for GUE Hamiltonians and numerical evidence for a mixed-field Ising chain.
-
From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs
The Any Kernel algorithm, a randomized extension of Vovk's K29*, achieves online outcome indistinguishability for any RKHS and yields the first O(√T) online omnipredictors for infinite real-valued comparator classes.
-
Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergence
For orthogonal hidden directions, gradient flow provably sends each neuron to the nearest direction and a log-factor overparameterization suffices, but for equiangular directions with overlap above beta_c = (p*-2)/(k+...
-
A Shank Angle-Based Control System Enables Soft Exoskeleton to Assist Human Non-Steady Locomotion
A dual-Gaussian assistance profile driven by shank angle and updated every stride is proposed so an IMU-only soft exoskeleton can assist non-steady locomotion; the claimed validation experiments reside in an unavailab...
-
Analysis of Higher-Order Ising Hamiltonians
IsingSim uses Walsh-Fourier expansion and convolution to efficiently evaluate and differentiate higher-order Ising Hamiltonians, and its experiments suggest Type I spins outperform Type II and III on parity learning w...
Discussion (0). Continue with ORCID to comment.