Introduction to Analysis of Boolean Functions 2
summary
Defines convolution and proves its Fourier transform becomes a pointwise product so averaging operators (Hamming balls, measures) translate cleanly into Fourier multipliers. Introduces the noise operator T_delta and shows it multiplies each Fourier coefficient by delta^{|S|}, damping high frequencies. Applies this to BLR linearity testing: multiplicative ±1 lift passes with probability 1 for a character and if f is ε‑far then the test accepts with probability at most 1−ε (amplify by repetition). Counts 3‑term APs ≈ α^3 ± O(ε) for ε‑pseudorandom sets and states Chang’s lemma: large coefficients lie in a low‑dimensional span (log dependence).
AI-written summary · about