Log-rank conjecture ·Rank lower bound*1 Log Rank Conjecture*2 log2rank(Mr)≤D(F)≤log(1rank(Mp) The rank lower bound is tight. combinatorial measuree 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(Me). -Conditional*8:D(F)<O(rank(ME)/logrank(Mr)) *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. 6
Log-rank conjecture • Rank lower bound* 1 log2 𝑟𝑎𝑛𝑘 𝑀𝐹 ≤ 𝐷 𝐹 • The rank lower bound is tight. • 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 6
Log-rank conjecture for XOR functions Since Log-rank conjecture appears too hard in its full generality,... let's try some special class of functions. ·XOR functions:f(x⊕y). --F=∫o⊕ The linear composition of x and y. Include important functions such as Equality, Hamming Distance,Gap Hamming Distance. Connection to Fourier:rank(M)=f
Log-rank conjecture for XOR functions • Since Log-rank conjecture appears too hard in its full generality,… • let’s try some special class of functions. • XOR functions: 𝑓(𝑥 ⊕ 𝑦). --- 𝐹 = 𝑓 ∘⊕ – The linear composition of 𝑥 and 𝑦. – Include important functions such as Equality, Hamming Distance, Gap Hamming Distance. • Connection to Fourier: 𝑟𝑎𝑛𝑘 𝑀𝑓∘⊕ = 𝑓 መ 0
Log-rank conjecture for XOR functions Goal:D(f⊕)≤log2fl Even this special case seems very hard. ·One approach*:D(fo⊕)≤2D⊕(f). -D):Parity decision tree complexity.(DT with queries like“x1⊕x3⊕x4=?") -simulating 1 -query by 2 bits of communication. *Zhang and Shi.Theoretical Computer Science,2009
Log-rank conjecture for XOR functions • Goal: 𝐷 𝑓 ∘⊕ ≤ log2 𝑂(1) 𝑓 መ 0 . • Even this special case seems very hard. • One approach*: 𝐷 𝑓 ∘⊕ ≤ 2𝐷⊕ 𝑓 . – 𝐷⊕ 𝑓 : Parity decision tree complexity. (DT with queries like “𝑥1 ⊕ 𝑥3 ⊕ 𝑥4 =?”) – simulating 1 ⊕-query by 2 bits of communication. *. Zhang and Shi. Theoretical Computer Science, 2009
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. 9
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. 9
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. 10
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. 10