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 x M ) = OMB ( f ( x 1 ) f ( x M )) to be the function on M 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 = 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 ( n 2 5 ) 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 ( n 1 3 ) and dimension complexity \poly ( n ) .