Fourier sparsity of GF(2) polynomials

DOI10.1007/978-3-319-34171-2_29zbMATH Open1482.12001arXiv1508.02158OpenAlexW2215158699MaRDI QIDQ5740202FDOQ5740202

Authors: Hing Yin Tsang, Ning Xie, Shengyu Zhang 

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1508.02158

Recommendations

• Fourier sparsity and dimension
• Efficiently Testing Sparse GF(2) Polynomials
• Efficiently testing sparse \(\text{GF}(2)\) polynomials
• Improved bounds on Fourier entropy and min-entropy
• The log-rank conjecture and low degree polynomials

Mathematics Subject Classification ID

Finite fields (field-theoretic aspects) (12E20) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Polynomials in general fields (irreducibility, etc.) (12E05)

Cites Work

• Communication Complexity
• Binomial Coefficients Modulo a Prime
• Testing Fourier dimensionality and sparsity
• Communication complexities of symmetric XOR functions
• Spectral norm of symmetric functions
• Composition theorems in communication complexity
• Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models

Cited In (3)

• A generalization of a theorem of Rothschild and van Lint
• A generalization of a theorem of Rothschild and van Lint
• On the decision tree complexity of threshold functions

This page was built for publication: Fourier sparsity of \(\mathrm{GF}(2)\) polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740202)