%0 Journal Article
%T Fourier Sparsity of GF(2) Polynomials
%A Hing Yin Tsang
%A Ning Xie
%A Shengyu Zhang
%J Computer Science
%D 2015
%I arXiv
%X 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 a GF(2) polynomial, then the Fourier sparsity (i.e. number of non-zero Fourier coefficients) of the polynomial must be large. We notice that the conjecture implies a surprising phenomenon that if the highest degree monomials of a GF(2) polynomial satisfy a certain condition, then the Fourier sparsity of the polynomial is large regardless of the monomials of lower degrees -- whose number is generally much larger than that of the highest degree monomials. We develop a new technique for proving lower bound on the Fourier sparsity of GF(2) polynomials, and apply it to certain special classes of polynomials to showcase the above phenomenon.
%U http://arxiv.org/abs/1508.02158v1