Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+
 All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only \$99

 Relative Articles Five Constructions of Permutation Polynomials over \$\gf(q^2)\$ Efficiently Testing Sparse GF(2) Polynomials An approach to the problem of generating irreducible polynomials over the finite field GF(2) and its relationship with the problem of periodicity on the space of binary sequences R-Hash: Hash Function Using Random Quadratic Polynomials Over GF(2) Discrete Fourier Analysis and Chebyshev Polynomials with G2 Group Discrete Fourier Analysis and Chebyshev Polynomials with \$G_2\$ Group Polynomial Fourier Domain as a Domain of Signal Sparsity LIMIT DISTRIBUTION OF A RANK OF RANDOM SATURATED MATRIX ABOVE A FIELD GF(2) ПРЕДЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ РАНГА СИЛЬНОЗАПОЛНЕННОЙ СЛУЧАЙНОЙ МАТРИЦЫ НАД ПОЛЕМ GF(2) ГРАНИЧНИЙ РОЗПОД Л РАНГУ СИЛЬНОЗАПОВНЕНО ВИПАДКОВО МАТРИЦ В ПОЛ GF(2) Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity Fast Fourier Optimization: Sparsity Matters More...

# Fourier Sparsity of GF(2) Polynomials

 Full-Text   Cite this paper

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-Text