Approximate degree of $\textrm{AC}^0$

Question

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)

Answer 1

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.