Log-rank conjecture ·Rank lower bound*1 Log Rank Conjecture*2 log2rank(MF)≤CC(F)≤log(1 rank(MF) 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. *1.Melhorn,Schmidt.STOC,1982.*4.Valiant.Info.Proc.Lett.,2004. *2.Lovasz,Saks.FOCS,1988. *5.Ambainis,Schulman,Ta-Shma,Vazirani,Wigderson,S/AM J. *3.Lovasz.Book Chapter,1990. Comp.2003. 11
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 . *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, SIAM J. Comp. 2003. ≤ log𝑂 1 𝑟𝑎𝑛𝑘 𝑀𝐹 Log Rank Conjecture* 2 11
Composed functions Even special cases are highly nontrivial. Composed functions:f(g1,...gn) Further restriction:all gi are some function {0,1}×{0,1}→{0,1. ·XOR functions:f(x⊕y). -F=fo① -Examples:Equality,(Gapped)Hamming Distance. AND functions:f(xAy). -F=fo∧ Examples:Disjointness,Inner Product,Nisan- Wigderson-Kushilevitz functions
Composed functions • Even special cases are highly nontrivial. • Composed functions: 𝑓 𝑔1,…𝑔𝑛 • Further restriction: all 𝑔𝑖 are some function 0,1 × 0,1 → 0,1 . • XOR functions: 𝑓(𝑥 ⊕ 𝑦). --- 𝐹 = 𝑓 ∘⊕ – Examples: Equality, (Gapped) Hamming Distance. • AND functions: 𝑓(𝑥 ∧ 𝑦). --- 𝐹 = 𝑓 ∘∧ – Examples: Disjointness, Inner Product, NisanWigderson-Kushilevitz functions
Polynomial sparsity o Fourier:Using±1，anyf:{+l,-1}n→R can be written as a multi-linear polynomial f(x)=∑sEIn]fsxs rank(M)=f the number of non-zero Fourier coefficients fs. Mobius:Using {0,1),any f:(0,1]7-R can be written as a multi-linear polynomial f(x)=>sEIn]asxs 0 rank (M)=llallo,the number of non-zero Mobius coefficients as
Polynomial sparsity • Fourier: Using ±1, any 𝑓: +1, −1 𝑛 → ℝ can be written as a multi-linear polynomial 𝑓 𝑥 = σ𝑆⊆ 𝑛 𝑓መ 𝑆𝑥𝑆 • 𝑟𝑎𝑛𝑘 𝑀𝑓∘⊕ = 𝑓መ 0 , the number of non-zero Fourier coefficients 𝑓መ 𝑆 . • Mobius: Using 0,1 , any 𝑓: 0,1 𝑛 → ℝ can be written as a multi-linear polynomial 𝑓 𝑥 = σ𝑆⊆ 𝑛 𝛼𝑆𝑥𝑆 • 𝑟𝑎𝑛𝑘 𝑀𝑓∘∧ = 𝛼 0 , the number of non-zero Mobius coefficients 𝛼𝑆
Special case:monotone Both Sensitivity Conjecture and Log-rank Conjecture are notoriously hard. But the following hold for all monotone functions f. -s(f)=bs(f)for monotone f. -CC(f )=0(logzrank(Mf))for monotone f. -Cc(f n)=0(log2 rank(M))for monotone f
Special case: monotone • Both Sensitivity Conjecture and Log-rank Conjecture are notoriously hard. • But the following hold for all monotone functions 𝑓. – 𝑠 𝑓 = 𝑏𝑠(𝑓) for monotone 𝑓. – 𝐶𝐶 𝑓 ∘⊕ = 𝑂 log2 𝑟𝑎𝑛𝑘 𝑀𝑓∘⊕ for monotone 𝑓. – 𝐶𝐶 𝑓 ∘∧ = 𝑂 log2 𝑟𝑎𝑛𝑘 𝑀𝑓∘∧ for monotone 𝑓