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 computed by an $s$ size bounded and $d$ depth bounded circuit of unbounded fan-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 polynomially bounded by $n$ and $d$ is constant, hence $f$ can be randomly approximated with 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.

What if we want to approximate such $f\in\textrm{AC}^{0}$ by not low degree polynomials but by family of polynomials which are sparse? Here, by sparse we would ideally mean 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.

  • $\begingroup$ something's wrong with your first equation. Are you sure you meant to write $Pr_{p \in P}$? Are you sure you meant to require p(x)=f(x)? (Hint: it's pretty hard for a polynomial over $\{0,1\}^n$ to be equal to $0$ or $1$.) Please make sure that your definition of "being approximated by a family of polynomials" makes sense and, if it is not a standard definition, try to explain how it differs from standard definitions: otherwise I suspect no one will understand the particular notion of approximation you're interested in. $\endgroup$ – mobius dumpling Apr 16 '14 at 1:35
  • 4
    $\begingroup$ Yes, such sparse polynomials would resolve many open problems... :) $\endgroup$ – Ryan Williams Apr 16 '14 at 4:33
  • 1
    $\begingroup$ @mobiusdumpling: The definition is actually standard. It originates in work of Toda & Ogiwara, Tarui, and Beigel, Reingold & Spielman. $\endgroup$ – Kristoffer Arnsfelt Hansen Apr 16 '14 at 8:54
  • $\begingroup$ @KristofferArnsfeltHansen Ah, I see. So this is in some approximation-theory sense, and not in the Fourier sense. In the Fourier sense such approximation can probably be shown to not exist by considering the $L_1$ norm: the $L_1$ norm of $AC0$ can be $n^{\Omega(\log n)}$ IIRC, while the $L_1$ norm of a sparse polynomial must be $poly(n)$. So I'm guessing something in the approximation-theoretic sense of the definition allows the $L_1$ norm to explode. Probably the permission that in the $\epsilon$ fraction of the space where they're not equal, the polynomials can take any value. $\endgroup$ – mobius dumpling Apr 16 '14 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.