Fourier sparsity,spectral norm, and the Log-rank conjecture arXiv:1304.1245 Hing Yin Tsang',Chung Hoi Wong1,Ning Xie2,Shengyu Zhang 1.The Chinese University of Hong Kong 2.Florida International University 1
arXiv:1304.1245 Hing Yin Tsang1 , Chung Hoi Wong1 , Ning Xie2 , Shengyu Zhang1 1. The Chinese University of Hong Kong 2. Florida International University 1
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? 2
Motivation 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
Some known results Results on learnability*1,testability*2,etc. A structural result by Green and Sanders. 。Theorem*3.f:{0,1r→{0,1}can be written as - ±1v where L1 =fl,and Vi's are subspaces. Question:Improve the doubly exponential bound? *1.Kushilevitz,Mansour,SIAMJ.on Computing,1993. *2.Gopalan,O'Donnell,Servedio,Shpilka,Wimmer,SIAM J.on Computing,2011. *3.Green and Sanders.Geometric and Functional Analysis,2008. 3
Some known results • Results on learnability* 1 ,testability* 2 , etc. • A structural result by Green and Sanders. • Theorem* 3 . ∀𝑓: 0,1 𝑛 → {0,1} can be written as 𝑓 = σ𝑖=1 2 2 𝑂 𝐿1 4 ±𝟏𝑉𝑖 , where 𝐿1 = 𝑓መ 1 and 𝑉𝑖 ’s are subspaces. • Question: Improve the doubly exponential bound? *1. Kushilevitz, Mansour, SIAM J. on Computing, 1993. *2. Gopalan, O’Donnell, Servedio, Shpilka, Wimmer, SIAM J. on Computing, 2011. *3. Green and Sanders. Geometric and Functional Analysis, 2008. 3
Motivation 2: Communication complexity X f(x,y) Two parties,Alice and Bob,jointly compute a function f(x,y). -x known only to Alice and y only to Bob. Communication complexity*1:how many bits are needed to be exchanged?---D() *1.Ya0.ST0C,1979
Motivation 2: Communication complexity • Two parties, Alice and Bob, jointly compute a function 𝑓(𝑥, 𝑦). – 𝑥 known only to Alice and 𝑦 only to Bob. • Communication complexity* 1 : how many bits are needed to be exchanged? --- 𝐷(𝑓) 𝑓(𝑥, 𝑦) 𝑥 𝑦 *1. Yao. STOC, 1979
Log-rank conjecture Not only interesting on its own,but also important because of numerous applications. to prove lower bounds. Ouestion:How to lower bound communication complexity itself? y Communication matrix X→ F(x,y) ME [F(x,y)x: 5
Log-rank conjecture • Not only interesting on its own, but also important because of numerous applications. – to prove lower bounds. • Question: How to lower bound communication complexity itself? • Communication matrix 𝑀𝐹 ≝ 𝐹 𝑥, 𝑦 𝑥,𝑦: 5 𝑥 → 𝑦 ↓ 𝐹(𝑥, 𝑦)