Analysis of Boolean Functions

By Li-Yang Tan. 2012

1,370 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “…{ 0 , 1 } D → R , its Fourier transform is given by the we deﬁne the level-k Fourier weight as For convenience, for s ∈ { 0 , 1 } D , we will also write ˆ f ( s ) to denote f ( χ s ), where χ s is the set { i One key technical lemma is the Level-1 Inequality from [37], which was also used in [27].”
Marginal Release Under Local Differential Privacy (2017, background): “These properties of HT are well-known due to its role in the theory of Boolean functions [30].”
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation (2019, methodology): “There is a long line of work investigating random classic spiking or hopfield networks, for example Landau & Sompolinsky (2018); Crisanti & Sompolinsky (2018); Kadmon & Sompolinsky (2015); Stern et al. (2014); Rajan et al.”
The Power of Linear Reconstruction Attacks (2012, background): “Let f : {0, 1}k+1 → {0, 1} represent the function that we want to evaluate on a databaseD.”
Competency Problems: On Finding and Removing Artifacts in Language Data (2021, background): “Our analysis of local edits additionally suggests a strong relationship to sensitivity in boolean functions (O’Donnell, 2014), and we identify gaps in the theory of sensitivity that need to be filled to properly account for bias in sampled datasets.”
Robust Optimality of Gaussian Noise Stability (2012, methodology): “To avoid all these difficulties, we will follow Kane [24] and Kindler and O’Donnell [29] to show if E1APt1A is almost as large as possible for t = log(1/ρ), then it is also large for certain values of t that are larger.”
A Fine-Grained Spectral Perspective on Neural Networks (2019, background): “Brief review of basic Fourier analysis on the boolean cube d ([40]).”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, methodology): “Note that by Cauchy-Schartz, Now we can apply Bonami’s Lemma (see Chapter 9 of O’Donnell [57]) along with the fact that ˆ f is a degree-4 polynomial in i.i.d. ± 1 variables z 1 , . . . , z d − 2 to obtain Combining this with Proposition 9.4 of O’Donnell [57] lets us conclude that if E holds, with…”
Pseudorandom Functions: Three Decades Later (2017, methodology): “It is convenient to view the range of the function as a multiplicative group, which allows for easier Fourier analysis [116].”
A Methodology for Formalizing Model-Inversion Attacks (2016, background): “More details regarding these concepts can be found in O’Donnell [11].”
Extra Samples can Reduce the Communication for Independence Testing (2018, background): “In the particular case of BSS(ρ), the entire hypercontractivity ribbon is characterized by ρ (see, for instance, [17]), and our bounds coincide.”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, unknown): “, [66]).”
Tensor Programs III: Neural Matrix Laws (2020, methodology): “We follow a presentation roughly given by O’Donnell [33].”
The Unintended Consequences of Overfitting: Training Data Inference Attacks (2017, background): “formalized the relevant property as functional influence [18], which is the probability that changing t will cause AS(x, t) to change when x is sampled uniformly.”