Lower Bounds for the Approximate Degree of Block-Composed Functions

J. Thaler

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, ..., x_M)=OMB(f(x_1), ..., f(x_M)) to be the function on MN 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 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 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 P^NP and 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).