24
$\begingroup$

EDIT (v2): Added a section at the end on what I know about the problem.

EDIT (v3): Added discussion on threshold degree at the end.

Question

This question is mainly a reference request. I don't know much about the problem. I want to know if there has been previous work on this problem, and if so, can someone point me to any papers that talk about this problem? I'd also like to know the current best bounds on the approximate degree of $\textrm{AC}^0$. Any other information would also be appreciated (e.g., historical information, motivation, relation to other problems, etc.).

Definitions

Let $f:\{0,1\}^n \to \{0,1\}$ be a Boolean function. Let $p$ be a polynomial over the variables $x_1$ to $x_n$ with real coefficients. The degree of a polynomial is the maximum degree over all monomials. The degree of a monomial is the sum of exponents of the various $x_i$ that appear in that monomial. For example $\textrm{deg}(x_1^7x_3^2) = 9$.

A polynomial $p$ is said to $\epsilon$-approximate $f$ if $|f(x)-p(x)|<\epsilon$ for all $x$. The $\epsilon$-approximate degree of a Boolean function $f$, denoted as $\widetilde{\textrm{deg}}_{\epsilon}(f)$, is the minimum degree of a polynomial that $\epsilon$-approximates $f$. For a set of functions, $F$, $\widetilde{\textrm{deg}}_{\epsilon}(F)$ is the minimum degree $d$ such that every function in $F$ can be $\epsilon$-approximated by a polynomial of degree at most $d$.

Note that every function can be represented with no error by a degree $n$ polynomial. Some functions really do need a degree $n$ polynomial to approximate to any constant error. Parity is an example of such a function.

Problem statement

What is $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$? (The constant 1/3 is arbitrary.)

Notes

I encountered this problem in the paper The Quantum Query Complexity of AC0 by Paul Beame and Widad Machmouchi. They say

Also, our results do nothing to close the gap in the lower bound on the approximate degree of AC0 functions.

They mention "the problem of the approximate degree of AC0" in their acknowledgements too.

So I assume there has been some work on this problem before? Can someone point me to a paper that talks about the problem? And what are the best known upper and lower bounds?

What I know about the problem (This section was added in v2 of the question)

The best known upper bound on $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$ that is know is the trivial upper bound $n$. The best lower bound I know comes from Aaronson and Shi's lower bound for the collision and element distinctness problems, which gives a lower bound of $\tilde{\Omega}(n^{2/3})$. (For severely restricted versions of $\textrm{AC}^0$, like formulas with $o(n^2)$ formula size, or depth-2 circuits with $o(n^2)$ gates, we can prove a $o(n)$ upper bound using quantum query complexity.)

Related: threshold degree (Added in v3)

As Tsuyoshi points out in the comments, this problem is related to the problem of determining the threshold degree of $\textrm{AC}^0$. The threshold degree of a function $f$ is the minimum degree of a polynomial $p$ such that $f(x)=1 \implies p(x)>0$ and $f(x)=0 \implies p(x)<0$.

Lower bounds for the threshold degree of $\mathrm{AC}^0$ have now been improved by Sherstov. He exhibits a family of constant-depth read-once formulas on $n$ variables whose threshold degree approaches $\Omega(\sqrt{n})$ as the depth goes to infinity, which is almost tight since read-once formulas have threshold (and even approximate) degree $O(\sqrt{n})$. See http://eccc.hpi-web.de/report/2014/009/. (Jan, 2014)

$\endgroup$
  • 7
    $\begingroup$ A lower bound Ω(n^(1/3)) is known even for threshold degree (the minimum degree of a polynomial p such that f(x)=1 ⇒ p(x)>0 and f(x)=0 ⇒ p(x)<0). See the end of Section 3.1 of “Communication lower bounds using dual polynomials” by Sherstov. $\endgroup$ – Tsuyoshi Ito Jul 19 '12 at 12:59
  • 4
    $\begingroup$ @Tsuyoshi: Thanks. The threshold degree (which lower bounds the approximate degree) of AC0 is also an interesting question. The best lower bounds that I know for the threshold degree of AC0 are in New degree bounds for polynomial threshold functions by O'Donnell and Servedio. The lower bound is better than Ω(n^(1/3)) by a log factor that grows with the depth of the circuit. $\endgroup$ – Robin Kothari Jul 26 '12 at 2:23
  • 4
    $\begingroup$ Oops, you are right, the $\tilde{\Omega}(n^{2/3})$ lower bound on the approximation degree for AC0 is obvious from Aaronson and Shi. Silly me. Thanks for the pointer to O’Donnell and Servedio, too. $\endgroup$ – Tsuyoshi Ito Jul 29 '12 at 0:07
  • $\begingroup$ A recent paper by Mark Bun and Justin Thaler titled "Hardness Amplification and the Approximate Degree of Constant-Depth Circuits" also discusses this problem briefly. They say that the lower bound of Aaronson and Shi is the best known lower bound for a function in AC<sup>0</sup> and that lower bound even holds in a slightly more general model. $\endgroup$ – Robin Kothari Apr 4 '14 at 17:49
4
$\begingroup$

A paper by Mark Bun and Justin Thaler has been posted on ECCC very recently (mid-March 2017) that precisely answers this question: "A Nearly Optimal Lower Bound on the Approximate Degree of AC0"

They claim that for any $\delta > 0$, there exists a function $f$ in $\mathrm{AC}^0$ such that $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$, nearly closing the gap with the trivial $O(n)$ upper bound. They achieve this with a general method to boost the approximate degree of a function with sublinear approximate degree, keeping the number of variables quasi-linear. From the abstract :

Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} · d^{2/3} )$. In particular, if $d = n^{1−Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$.

That is the most recent update on the lower bound end of this problem, and it is quite a significant step forward. The Introduction and Application sections of the paper are also good sources of references for prior works and related problems.

Disclaimer: I haven't read the paper carefully yet.

$\endgroup$
  • $\begingroup$ Indeed, this almost closes the problem. They also show a DNF of quasipolynomial size with approximate degree $\Omega(n^{1-\delta})$. $\endgroup$ – Robin Kothari Apr 4 '17 at 18:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.