Let $f$ be a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}$.We say that $f$ is randomly approximated with error probability $\epsilon$by a family of polynomials $P$ if \begin{equation}\forall x\in\{0,1\}^{n}\Pr_{p\in P}[p(x)=f(x)]\geq1-\epsilon\end{equation}It is known that if $f:\{0,1\}^{n}\rightarrow\{0,1\}$ is computedby an $s$ size bounded and $d$ depth bounded circuit of unboundedfan-in, then $f$ can be randomly approximated with error probability$\epsilon$ by a family of polynomials of degree $O(\log^{d}(\frac{s}{\epsilon})\cdot\log^{d}(s))$.If $f$ can be computed by an $\textrm{AC}^{0}$ circuit then $s$ is polynomiallybounded by $n$ and $d$ is constant, hence $f$ can be randomly approximatedwith constant error probability by a family of polynomials of degree$\textrm{poly}(\log(n))$, which is low degree. The number of monomials in these approximating polynomials may still be quasi-polynomial though. Whatif we want to approximate such $f\in\textrm{AC}^{0}$ by not low degree polynomialsbut by family of polynomials which are sparse? Here, by sparse we would ideallymean that number of monomial is something like $\textrm{poly}(n)$.Can we find a family  of sparse polynomials $P$ such that such $f$ is randomly approximated  with error probability $\epsilon$ by $P$ ?If not for $\textrm{AC}^{0}$,  what are other non trivial class of functions which can be approximated  by families of sparse polynomials. 
Approximating $\textrm{AC}^{0}$ by sparse polynomials
cc.complexity theory;circuit complexity