most citedFourier sparsity, spectral norm, and the Log-rank conjecture

6 citations · 6 across the 1 of their papers we have counts for

collaborators

1 paper

cs.CC2013★ 6 cited

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…