Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Lower Bounds for the Approximate Degree of Block-Composed Functions

RSS-Feed

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


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


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
Downloads: 2287
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