ECCC-Report TR16-025https://eccc.weizmann.ac.il/report/2016/025Comments and Revisions published for TR16-025en-usTue, 15 Mar 2016 16:33:33 +0200
Revision 1
| The Fourier structure of low degree polynomials |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2016/025#revision1The 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$.Tue, 15 Mar 2016 16:33:33 +0200https://eccc.weizmann.ac.il/report/2016/025#revision1
Paper TR16-025
| The Fourier structure of low degree polynomials |
Shachar Lovett
https://eccc.weizmann.ac.il/report/2016/025We 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$.
Sat, 27 Feb 2016 08:45:42 +0200https://eccc.weizmann.ac.il/report/2016/025