Fourier sparsity of GF(2) polynomials

DOI10.1007/978-3-319-34171-2_29MaRDI QIDQ5740202zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• Binomial Coefficients Modulo a Prime
• Communication Complexity
• Communication complexities of symmetric XOR functions
• Composition theorems in communication complexity
• Spectral norm of symmetric functions
• Testing Fourier dimensionality and sparsity
• 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)