Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR14-150 | 27th March 2016 21:32

#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revision #3
Authors: Justin Thaler
Accepted on: 27th March 2016 21:32
Keywords:

Abstract:

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).

Changes to previous version:

Substantially tightened applications to communication and query complexity.

Revision #2 to TR14-150 | 27th January 2015 01:42

#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revision #2
Authors: Justin Thaler
Accepted on: 27th January 2015 01:42
Keywords:

Abstract:

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

Changes to previous version:

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).

Revision #1 to TR14-150 | 10th November 2014 22:21

#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revision #1
Authors: Justin Thaler
Accepted on: 10th November 2014 22:21
Keywords:

Abstract:

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

Changes to previous version:

Added minor clarification regarding prior work.

### Paper:

TR14-150 | 10th November 2014 16:09

#### Lower Bounds for the Approximate Degree of Block-Composed Functions

TR14-150
Authors: Justin Thaler
Publication: 10th November 2014 16:56
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint