We study a conjecture called "linear rank conjecture" recently raised in (Tsang et al.), 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 (Specifically, the highest degree monomials do not vanish under a small number of linear restrictions.), 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.
展开▼
