<p>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}</p>

<p>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))$.</p>

<p>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. </p>

<p>The number of monomials in these approximating polynomials may still be quasi-polynomial though. </p>

<p>What
if we want to approximate such $f\in\textrm{AC}^{0}$ by not low degree polynomials
but by family of polynomials which are <strong>sparse</strong>? Here, by sparse we would ideally
mean that number of monomial is something like $\textrm{poly}(n)$.</p>

<blockquote>
  <p>Can we find a family
  of sparse polynomials $P$ such that such $f$ is randomly approximated
  with error probability $\epsilon$ by $P$ ?</p>
  
  <p>If not for $\textrm{AC}^{0}$,
  what are other non trivial class of functions which can be approximated
  by families of sparse polynomials. </p>
</blockquote>

CC BY-SA 3.0
2014-04-16T01:35:09.400Z
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.
greg
CC BY-SA 3.0
2014-04-16T04:33:57.273Z
Yes, such sparse polynomials would resolve many open problems... :)
Ryan Williams
CC BY-SA 3.0
2014-04-16T08:54:27.337Z
@mobiusdumpling: The definition is actually standard. It originates in work of Toda & Ogiwara, Tarui, and Beigel, Reingold  & Spielman.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-04-16T11:22:31.843Z
@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.
greg
<cc.complexity-theory><circuit-complexity>
Approximating $\textrm{AC}^{0}$ by sparse polynomials
Gorav Jindal
# Approximating $\textrm{AC}^{0}$ by sparse polynomials

(Asked by: username_0 on 2014-04-15)

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.

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: 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.  
> **username_2**: Yes, such sparse polynomials would resolve many open problems... :)  
> **username_3**: @mobiusdumpling: The definition is actually standard. It originates in work of Toda & Ogiwara, Tarui, and Beigel, Reingold  & Spielman.  
> **username_1**: @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.  

---

## 0 answers

