We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known as ODD-MAX-BIT. We show that, if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense (captured by a complexity measure known as \emph{positive one-sided approximate degree}), then $F$ requires large degree to approximate even to error $1-2^{-M}$. This generalizes a result of Beigel, who proved an identical result for the special case $f=\text{OR}$.

Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions $F$ that have low threshold degree.
Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function.
We describe several applications, including improved separations between the complexity classes $\textsc{P}^{\textsc{NP}}$ and $\textsc{PP}$ in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).

Substantially tightened applications to communication and query complexity.

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known as ODD-MAX-BIT. We show that, if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense (captured by a complexity measure known as \emph{positive one-sided approximate degree}), then $F$ requires large degree to approximate even to error $1-2^{-M}$. This generalizes a result of Beigel, who proved an identical result for the special case $f=\text{OR}$.

Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions $F$ that have low \emph{threshold degree}. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function.

As an application, we give an explicit AC$^0$ function with \emph{margin complexity} $\exp\left(\tilde{\Omega}(n^{2/5})\right)$ and \emph{dimension complexity} $\poly(n)$. The previous best separation was due to Buhrman et al., who gave an AC$^0$ function with margin complexity $\exp\left(\Omega(n^{1/3})\right)$ and dimension complexity $\poly(n)$.

Tightened the bound on the dimension complexity of the AC$^0$ function from $n^{O(\log n)}$ to $\poly(n)$. Included clarifications regarding prior works of Beigel, as well as Klivans and Servedio, on polynomial approximations to ODD-MAX-BIT (see Footnotes 2 and 3).

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known as ODD-MAX-BIT. We show that, if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense (captured by a complexity measure known as \emph{positive one-sided approximate degree}), then $F$ requires large degree to approximate even to error $1-2^{-M}$. This generalizes a result of Beigel, who proved an identical result for the special case $f=\text{OR}$.

Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions $F$ that have low \emph{threshold degree}. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function.

As an application, we give an explicit AC$^0$ function with \emph{margin complexity} $\exp\left(\tilde{\Omega}(n^{2/5})\right)$ and \emph{dimension complexity} $n^{O(\log n)}$. The previous best separation was due to Buhrman et al., who gave an AC$^0$ function with margin complexity $\exp\left(\Omega(n^{1/3})\right)$ and dimension complexity $\poly(n)$.

Added minor clarification regarding prior work.

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known as ODD-MAX-BIT. We show that, if $f$ requires large degree to approximate to error $2/3$ in a certain one-sided sense (captured by a complexity measure known as \emph{positive one-sided approximate degree}), then $F$ requires large degree to approximate even to error $1-2^{-M}$. This generalizes a result of Beigel, who proved an identical result for the special case $f=\text{OR}$.

Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions $F$ that have low \emph{threshold degree}. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function.

As an application, we give an explicit AC$^0$ function with \emph{margin complexity} $\exp\left(\tilde{\Omega}(n^{2/5})\right)$ and \emph{dimension complexity} $n^{O(\log n)}$. The previous best separation was due to Buhrman et al., who gave an AC$^0$ function with margin complexity $\exp\left(\Omega(n^{1/3})\right)$ and dimension complexity $\poly(n)$.