REVIEW 8 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
Analysis of Boolean Functions
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 8 Pith papers
-
Testing k-submodularity
Initiates property testing for k-submodular functions, yielding constant-query testers in l_p distance via hypergrid junta approximation and sub-exponential testers for component properties in Hamming distance, but wi...
-
Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
Coherent-state propagation enables quasi-polynomial classical simulation of bosonic circuits with logarithmically many Kerr gates at exponentially small trace-distance error, with polynomial runtime in the weak-nonlin...
-
Efficient simulation of noisy IQP circuits with amplitude-damping noise
A classical polynomial-time sampler exists for the output distribution of amplitude-damped IQP circuits with logarithmic depth and arbitrary l-local diagonal gates.
-
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 Characterization To Construction: Generative Quantum Circuit Synthesis from Gate Set Tomography Data
A generative QMLC framework tokenizes GST data, embeds it via curriculum-trained set-vision transformers into a context-aware latent space, and uses diffusion models to synthesize circuits conditioned on desired measu...
-
Further evidence towards the Fourier Entropy-Influence conjecture
The authors prove that δ-tribes functions, monotone Boolean functions with the tribe separation property, and Boolean functions with the semi-separation property satisfy the FEI conjecture using a stopping binary tree...
-
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...
-
IQPopt: Fast optimization of instantaneous quantum polynomial circuits in JAX
IQPopt is a JAX-based software tool enabling classical optimization of IQP circuits with thousands of qubits via efficient simulation of Pauli-Z expectation values, plus a module for quantum generative model training.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.