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. 11Our 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