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