Fourier Sparsity of GF(2) Polynomials

Hing Yin Tsang, Ning Xie, Shengyu Zhang

We study a conjecture called "linear rank conjecture" recently raised in (Tsang et al., FOCS'13), which asserts that if many linear constraints are required to lower the degree of…