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 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.Yao.ST0C,1979. 4
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. 4
Log-rank conjecture ME世[F(x,y)]x,y Rank lower bound*1 Log Rank Conjecture*2 log2rank(Mp)≤D(F)≤logo(1rank(MF) combinatorial measure linear algebra measure. Equivalent to a bunch of other conjectures. -related to graph theory*2;nonnegative rank*3,Boolean roots of polynomials*4,quantum sampling complexity*5. Largest known gap*6:D(F)=0(log263rank(Mp)). Best previous upper bound*7:D(F)<log(4/3).rank(Mr). -Conditional*8:D(F)<0(rank(Mr)/logrank(ME)) *1.Melhorn,Schmidt.STOC,1982. *5.Ambainis,Schulman,Ta-Shma,Vazirani,Wigderson,S/COMP 2003. *2.Lovasz,Saks.FOCS,1988. *6.Nisan and Wigderson.Combinatorica,1995. *3.Lovasz.Book Chapter,1990. *7.Kotlov.Journal of Graph Theory,1982. *4.Valiant.Info.Proc.Lett.,2004. *8.Ben-Sasson,Lovett,Ron-Zewi,FOCS,2012. 5
Log-rank conjecture • Rank lower bound* 1 log2 𝑟𝑎𝑛𝑘 𝑀𝐹 ≤ 𝐷 𝐹 • combinatorial measure ⇔ linear algebra measure. • Equivalent to a bunch of other conjectures. – related to graph theory*2 ; nonnegative rank*3 , Boolean roots of polynomials*4 , quantum sampling complexity*5 . • Largest known gap*6 : 𝐷 𝐹 = 𝑂 log2 1.63… 𝑟𝑎𝑛𝑘 𝑀𝐹 . • Best previous upper bound*7 : 𝐷 𝐹 ≤ log 4/3 ⋅ 𝑟𝑎𝑛𝑘 𝑀𝐹 . – Conditional*8 : 𝐷 𝐹 ≤ 𝑂 𝑟𝑎𝑛𝑘(𝑀𝐹)/log 𝑟𝑎𝑛𝑘(𝑀𝐹) *1. Melhorn, Schmidt. STOC, 1982. *2. Lovász, Saks. FOCS, 1988. *3. Lovász. Book Chapter, 1990. *4. Valiant. Info. Proc. Lett., 2004. *5. Ambainis, Schulman, Ta-Shma, Vazirani, Wigderson, SICOMP 2003. *6. Nisan and Wigderson. Combinatorica, 1995. *7. Kotlov. Journal of Graph Theory, 1982. *8. Ben-Sasson, Lovett, Ron-Zewi, FOCS, 2012. ≤ log𝑂 1 𝑟𝑎𝑛𝑘 𝑀𝐹 𝑀𝐹 ≝ 𝐹 𝑥, 𝑦 𝑥,𝑦 Log Rank Conjecture* 2 5
Special class of functions Since Log-rank conjecture appears too hard in its full generality,... ·XOR functions:f(x⊕y). -F=fo① Include important functions such as Equality, Hamming Distance,Gap Hamming Distance. Connection to Fourier:rank(M)=fo . ·One approach*1:D(fo⊕)≤2Def) -Df):Parity decision tree complexity. (DT with queries like“x1⊕x3⊕x4=?") *1.Zhang and Shi.Theoretical Computer Science,2009. 6
Special class of functions • Since Log-rank conjecture appears too hard in its full generality,… • XOR functions: 𝑓(𝑥 ⊕ 𝑦). --- 𝐹 = 𝑓 ∘⊕ – Include important functions such as Equality, Hamming Distance, Gap Hamming Distance. • Connection to Fourier: 𝑟𝑎𝑛𝑘 𝑀𝑓∘⊕ = 𝑓 መ 0 . • One approach*1 : 𝐷 𝑓 ∘⊕ ≤ 2𝐷⊕ 𝑓 – 𝐷⊕ 𝑓 : Parity decision tree complexity. (DT with queries like “𝑥1 ⊕ 𝑥3 ⊕ 𝑥4 =?”) *1. Zhang and Shi. Theoretical Computer Science, 2009. 6
One easy case ·deg(f)=max{la:f(a)≠0} The (total)degree of f as a multi-linear polynomial over R. If deg(f)=log()f,then even the standard decision tree complexity is small *1,2. -DT(f)=0(deg3(f)=log(I‖fl。 Question:Are all nonzero Fourier coefficients always located in low levels? Answer*3:Not even after change of basis. There are f with De(f)n/4. *1.Nisan and Smolensky.Unpublished. *2.Midrijanis.arXiv/quant-ph/0403168,2004. *3.Zhang and Shi.Theoretical Computer Science,2009. 7
One easy case • deg 𝑓 = max{ 𝛼 : 𝑓መ 𝛼 ≠ 0} – The (total) degree of 𝑓 as a multi-linear polynomial over ℝ. • If deg 𝑓 = log𝑂(1) 𝑓መ 0 , then even the standard decision tree complexity is small *1,2 . – 𝐷𝑇 𝑓 = 𝑂 deg3 𝑓 = log𝑂(1) 𝑓መ 0 . • Question: Are all nonzero Fourier coefficients always located in low levels? • Answer* 3 : Not even after change of basis. – There are 𝑓 with 𝐷⊕ 𝑓 ≤ log 𝑛 but min 𝐿 𝐷𝑇 𝐿𝑓 ≥ 𝑛/4. *1. Nisan and Smolensky. Unpublished. *2. Midrijanis. arXiv/quant-ph/0403168, 2004. *3. Zhang and Shi. Theoretical Computer Science, 2009. 7
Previous work ● Special cases for f. f:Symmetric o() -f:LTF *2 -f:monotone *2 -f:AC0*3 degf)=o(l.） Hard case:deg(f)much larger than logf not touched yet. *1.Zhang and Shi.Quantum Information Computation,2009. *2.Montanaro and Osborne.arXiv:0909.3392v2,2010. *3.Kulkarni and Santha.ClAC,2013. 8
Previous work • Special cases for 𝑓. – 𝑓: Symmetric *1 – 𝑓: LTF *2 – 𝑓: monotone *2 – 𝑓: 𝐴𝐶 0 * 3 • Hard case: deg(𝑓) much larger than log 𝑓መ 0 – not touched yet. log 𝑓መ 0 = Ω 𝑛 deg 𝑓 = 𝑂෨ log 𝑓መ 0 *1. Zhang and Shi. Quantum Information & Computation, 2009. *2. Montanaro and Osborne. arXiv:0909.3392v2, 2010. *3. Kulkarni and Santha. CIAC, 2013. 8
Our results:starting point While deg(f)is not a good bridge between D(f)and logf,another degree may be. deg2(f):degree of f as a polynomial over F2. 0( Compared to Fourier sparsity,deg2(f)is always small. Fact*1.deg2(f)s loglflo *1.Bernasconi and Codenotti.IEEE Transactions on Computers,1999. 9
Our results: starting point • While deg(𝑓) is not a good bridge between 𝐷⊕(𝑓) and log 𝑓 መ 0 , another degree may be. • deg2 (𝑓): degree of 𝑓 as a polynomial over 𝔽2 . • Compared to Fourier sparsity, deg2 (𝑓) is always small. – Fact*1 . deg2(𝑓) ≤ log 𝑓መ 0 . *1. Bernasconi and Codenotti. IEEE Transactions on Computers, 1999. 9
Our results:constant degree Theorem 1.For f with deg2(f)=0(1): 1)Log-rank conjecture holds for fo. Dependence on d:"only"singly exponential. Def)≤2a221oga-2f1 2）Fourier sparse2'horM⊕-DT logllfll。≤De⊕f)≤logo(llf‖o 3)f depends only on log(f linear functions of input variables. 10
Our results: constant degree • Theorem 1. For 𝑓 with deg2 𝑓 = 𝑂(1): 1) Log-rank conjecture holds for 𝑓 ∘⊕. Dependence on 𝑑: “only” singly exponential. 𝐷⊕ 𝑓 ≤ 2 𝑑 2/2 log𝑑−2 𝑓መ 1 2) Fourier sparse 𝑝𝑜𝑙𝑦 short ⊕-DT log 𝑓መ 0 ≤ 𝐷⊕ 𝑓 ≤ log𝑂 1 𝑓መ 0 3) 𝑓 depends only on log𝑂 1 𝑓መ 0 linear functions of input variables. 10