
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
Enroute of constructing our PRG, we prove two structural results for low degree polynomials over finite fields that can be of independent interest.
egin{enumerate} item Let $f$ be an $n$variate degree $d$ polynomial over $mathbb{F}_p$. Then, for every $epsilon>0$ there exists a subset $S subset [n]$, whose size depends only on $d$ and $epsilon$, such that $sum_{alpha in mathbb{F}_p^n: alpha e 0, alpha_S=0}hat{f}(alpha)^2 leq epsilon$. Namely, there is a constant size subset $S$ such that the total weight of the nonzero Fourier coefficients that do not involve any variable from $S$ is small.
item Let $f$ be an $n$variate degree $d$ polynomial over $mathbb{F}_p$. If the distribution of $f$ when applied to uniform zeroone bits is $epsilon$far (in statistical distance) from its distribution when applied to biased bits, then for every $delta>0$, $f$ can be approximated over zeroone bits, up to error $delta$, by a function of a small number (depending only on $epsilon,delta$ and $d$) of lower degree polynomials. end{enumerate}