Previous work ● Special cases for f. f:Symmetric o() -f:LTF *2 -f:monotone *2 -f:AC0*3 deg=o(ofl) 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. 10Previous 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. 10