Our results:starting point While deg(f)is not a good bridge between D(f)and logf,another degree may be. deg2(f):degree of f as a polynomial over F2. 0( Compared to Fourier sparsity,deg2(f)is always small. Fact*1.deg2(f)s loglflo *1.Bernasconi and Codenotti.IEEE Transactions on Computers,1999. 11
Our results: starting point • While deg(𝑓) is not a good bridge between 𝐷⊕(𝑓) and log 𝑓 መ 0 , another degree may be. • deg2 (𝑓): degree of 𝑓 as a polynomial over 𝔽2 . • Compared to Fourier sparsity, deg2 (𝑓) is always small. – Fact*1 . deg2(𝑓) ≤ log 𝑓መ 0 . *1. Bernasconi and Codenotti. IEEE Transactions on Computers, 1999. 11
Our results:constant degree Theorem 1.For f with deg2(f)=0(1): 1)Log-rank conjecture holds for fo. Dependence on d:"only"singly exponential. Def)≤2a221oga-2f1 2）Fourier sparse2'horM⊕-DT logllfll。≤De⊕f)≤logo(llf‖o 3)f depends only on log(f linear functions of input variables. 12
Our results: constant degree • Theorem 1. For 𝑓 with deg2 𝑓 = 𝑂(1): 1) Log-rank conjecture holds for 𝑓 ∘⊕. Dependence on 𝑑: “only” singly exponential. 𝐷⊕ 𝑓 ≤ 2 𝑑 2/2 log𝑑−2 𝑓መ 1 2) Fourier sparse 𝑝𝑜𝑙𝑦 short ⊕-DT log 𝑓መ 0 ≤ 𝐷⊕ 𝑓 ≤ log𝑂 1 𝑓መ 0 3) 𝑓 depends only on log𝑂 1 𝑓መ 0 linear functions of input variables. 12
Our results:constant degree ·[GS08]f:{0,1}n→{0,1}can be written as () f= ±1V where L1 =f,and Vi's are subspaces. Theorem 2:If deg2(f)=0(1),then we improve doubly exponential bound to quasi-polynomial: -224→2010g4-21) [GS08]Green and Sanders.Geometric and Functional Analysis,2008. 13
Our results: constant degree • [GS08] ∀𝑓: 0,1 𝑛 → {0,1} can be written as 𝑓 = σ𝑖=1 2 2 𝑂 𝐿1 4 ±𝟏𝑉𝑖 , where 𝐿1 = 𝑓መ 1 and 𝑉𝑖 ’s are subspaces. • Theorem 2: If deg2 𝑓 = 𝑂(1), then we improve doubly exponential bound to quasi-polynomial: – 2 2 𝑂 𝐿1 4 → 2 𝑂(log𝑑−2 𝐿1) [GS08] Green and Sanders. Geometric and Functional Analysis, 2008. 13