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. 9One 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. 9