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)<logn but min DT(Lf)>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