ECCC-Report TR14-150https://eccc.weizmann.ac.il/report/2014/150Comments and Revisions published for TR14-150en-usSun, 27 Mar 2016 21:32:43 +0300
Revision 3
| Lower Bounds for the Approximate Degree of Block-Composed Functions |
Justin Thaler
https://eccc.weizmann.ac.il/report/2014/150#revision3We 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).Sun, 27 Mar 2016 21:32:43 +0300https://eccc.weizmann.ac.il/report/2014/150#revision3
Revision 2
| Lower Bounds for the Approximate Degree of Block-Composed Functions |
Justin Thaler
https://eccc.weizmann.ac.il/report/2014/150#revision2We 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)$.Tue, 27 Jan 2015 01:42:20 +0200https://eccc.weizmann.ac.il/report/2014/150#revision2
Revision 1
| Lower Bounds for the Approximate Degree of Block-Composed Functions |
Justin Thaler
https://eccc.weizmann.ac.il/report/2014/150#revision1We 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)$.Mon, 10 Nov 2014 22:21:08 +0200https://eccc.weizmann.ac.il/report/2014/150#revision1
Paper TR14-150
| Lower Bounds for the Approximate Degree of Block-Composed Functions |
Justin Thaler
https://eccc.weizmann.ac.il/report/2014/150We 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)$.Mon, 10 Nov 2014 16:56:38 +0200https://eccc.weizmann.ac.il/report/2014/150