View article

We study Boolean functions with sparse Fourier spectrum or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x ⊕ y) - a fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix M _f for such functions is exactly the Fourier sparsity of f. Let d = deg ₂ (f) be the F ₂ -degree of f and DCC(f · ⊕) stand for the deterministic communication complexity for f(x ⊕ y). We show that 1) DCC(f · ⊕) = O(2 ^d2/2 log ^d- 2 ∥f̂∥ ₁ ). In particular, the Log-rank conjecture holds for XOR functions with constant F ₂ -degree. 2) D ^CC (f · ⊕) = O(d∥f̂∥ ₁ ) = O(√(rank(M _f ))). This improves the (trivial) linear bound by nearly a quadratic factor. We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that the communication cost of our protocol is at most log …