Fourier sparsity, spectral norm, and the Log-rank conjecture

Hing Yin Tsang, Chung Hoi Wong, Ning Xie +1

We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fair…