Motivation 1:Fourier analysis f:0,1→R f(x)=∑af(a)Xa(x) f01”-A 食 f(a)=Ex[f(x)xa(x)] (Xa(x)=(-1)rx) Bool Fourier (sparsified) Parseval::If Range(f)={±1，then fl2=1. Spectral norm:f=Ealf(a) Fourier sparsity:.lfl。=l{ac:f(a)≠0l Oustion:What can we say about Boolean f with smallforf? Characterization? 2Motivation 1: Fourier analysis Bool Fourier 𝑓(𝑥) = σ𝛼 𝑓መ 𝛼 𝜒𝛼(𝑥) 𝑓መ 𝛼 = 𝐄𝑥 𝑓 𝑥 𝜒𝛼(𝑥) 𝜒𝛼 𝑥 = −1 𝛼⋅𝑥 Parseval: If 𝑅𝑎𝑛𝑔𝑒 𝑓 = ±1 , then 𝑓መ 2 = 1. Spectral norm: 𝑓መ 1 = σ𝛼 𝑓መ 𝛼 . Fourier sparsity: 𝑓መ 0 = 𝛼: 𝑓መ 𝛼 ≠ 0 Qustion: What can we say about Boolean 𝑓 with small 𝑓መ 1 or 𝑓መ 0 ? Characterization? 𝑓: 0,1 𝑛 → ℝ 𝑓መ : 0,1 𝑛 → ℝ (sparsified) ±1 2