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. 6Log-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