2026-07-20T11:02:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6313 2024-03-06T10:37:39Z ddc:004 open_access

Lower Bounds for the Approximate Degree of Block-Composed Functions Thaler, Justin approximate degree one-sided approximate degree polynomial approx- imations threshold degree communication complexity 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 function 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 (Computational Complexity, 1994), 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Justin Thaler 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.17 urn:nbn:de:0030-drops-63133 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.17 eng https://creativecommons.org/licenses/by/3.0/legalcode