Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR16-025 | 15th March 2016 16:33

The Fourier structure of low degree polynomials


Revision #1
Authors: Shachar Lovett
Accepted on: 15th March 2016 16:33
Downloads: 1076


The paper was removed due to a mistake in the proof. Theorem 4.2 as stated is not correct. We thank Qian Li for finding that.

An example is: let $x,y \in \mathbb{F}_2^d, z \in \mathbb{F}_2^{d^2}$, take the order 3 tensor
$T(x,y,z)=\sum_{i,j \in [d]} x_i y_j z_{i,j}$. It has linear dimension $d$ when fixing any of $x,y$ or $z$, but its overall linear dimension is $d^2$.

Changes to previous version:

Paper removed due to a mistake in the proof.


TR16-025 | 26th February 2016 22:49

The Fourier structure of low degree polynomials

Authors: Shachar Lovett
Publication: 27th February 2016 08:45
Downloads: 1501


We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero Fourier coefficients. For quadratic polynomials, tight relations are known between all three quantities. In this work, we extend this relation to higher degree polynomials. Specifically, for degree $d$ polynomials, we show that the three quantities are equivalent up to factors exponential in $d$.

ISSN 1433-8092 | Imprint