Abstract
We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error. As our main application, we show that for every sequence of degrees \(d(n)\), there is an explicit depth-three circuit \(F: \{-1,1\}^n \rightarrow \{-1,1\}\) of polynomial-size such that any degree-\(d\) polynomial cannot pointwise approximate \(F\) to error better than \(1-\exp (-\tilde{\Omega }(nd^{-3/2}))\). As a consequence of our main result, we obtain an \(\exp (-\tilde{\Omega }(n^{2/5}))\) upper bound on the the discrepancy of a function in AC\(^{\text{0 }}\), and an \(\exp (\tilde{\Omega }(n^{2/5}))\) lower bound on the threshold weight of AC\(^{\text{0 }}\), improving over the previous best results of \(\exp (-\Omega (n^{1/3}))\) and \(\exp (\Omega (n^{1/3}))\) respectively.
Our techniques also yield a new lower bound of \(\Omega (n^{1/2}/\log ^{(d-2)/2}(n))\) on the approximate degree of the AND-OR tree of depth \(d\), which is tight up to polylogarithmic factors for any constant \(d\), as well as new bounds for read-once DNF formulas. In turn, these results imply new lower bounds on the communication and circuit complexity of these classes, and demonstrate strong limitations on existing PAC learning algorithms.
The full version of this paper is available at http://arxiv.org/abs/1311.1616.
Supported by an NDSEG Fellowship and NSF grant CNS-1237235.
Parts of this work were done while the author was a graduate student at Harvard University, and a Research Fellow at the Simons Institute for the Theory of Computing. This work was supported by an NSF Graduate Research Fellowship, NSF grants CNS-1011840 and CCF-0915922, and a Research Fellowship from the Simons Institute for the Theory of Computing.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aaronson, S.: The polynomial method in quantum and classical computing. In: FOCS (2008). (Slides available at www.scottaaronson.com/talks/polymeth.ppt)
Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM 51(4), 595–605 (2004)
Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory Comput. 1(1), 37–46 (2005)
Ambainis, A., Childs, A.M., Reichardt, B., Špalek, R., Zhang, S.: Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer. SIAM J. Comput. 39(6), 2513–2530 (2010)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bound by polynomials. J. ACM 48(4), 778–797 (2001)
Beigel, R.: Perceptrons, PP, and the polynomial hierarchy. Computational Complexity 4, 339–349 (1994)
Buhrman, H., Vereshchagin, N.K., de Wolf, R.: On computation and communication with small bias. CCC, pp. 24–32 (2007)
Bun, M., Thaler, J.: Dual lower bounds for approximate degree and markov-bernstein inequalities. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 303–314. Springer, Heidelberg (2013)
Gavinsky, D., Sherstov, A.A.: A separation of NP and coNP in multiparty communication complexity. Theory of Computing 6(1), 227–245 (2010)
Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: ICALP, pp. 291–299 (2003)
Kalai, A., Kanade, V., Mansour, Y.: Reliable agnostic learning. J. Comput. Syst. Sci. 78(5), 1481–1495 (2012)
Kalai, A., Klivans, A., Mansour, Y., Servedio, R.: Agnostically learning halfspaces. SIAM Journal on Computing 37(6), 1777–1805 (2008)
Kanade, V., Thaler, J.: Distribution-independent reliable learning. In: COLT (2014)
Klivans, A.R., Servedio, R.A.: Learning DNF in time \(2^{\tilde{O}(n^{1/3})}\). J. of Comput. and System Sci. 68(2), 303–318 (2004)
Klivans, A.R., Servedio, R.A.: Toward attribute efficient learning of decision lists and parities. Journal of Machine Learning Research 7, 587–602 (2006)
Krause, M.: On the computational power of Boolean decision lists. Computational Complexity 14(4), 362–375 (2005)
Krause, M., Pudlák, P.: On the computational power of depth-2 circuits with threshold and modulo gates. Theor. Comput. Sci. 174(1–2), 137–156 (1997)
Lee, T.: A note on the sign degree of formulas (2009). CoRR abs/0909.4607
Minsky, M.L., Papert, S.A.: Perceptions: An Introduction to Computational Geometry. MIT Press, Cambridge (1969)
Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity 4, 301–313 (1994)
O’Donnell, R., Servedio, R.: New degree bounds for polynomial threshold functions. Combinatorica 30(3), 327–358 (2010)
Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions (Preliminary Version). STOC, pp. 468–474 (1992)
Reichardt, B.: Reflections for quantum query algorithms. In: SODA (2011)
Servedio, R.A., Tan, L.-Y., Thaler, J.: Attribute-Efficient learning and weight-degree tradeoffs for polynomial threshold functions. COLT 23, 14.1–14.19 (2012)
Sherstov, A.A.: Approximating the AND-OR Tree. Theory of Computing (2013)
Sherstov, A.A.: Breaking the Minsky-Papert Barrier for constant-depth circuits. STOC (2014)
Sherstov, A.A.: Communication lower bounds using dual polynomials. Bulletin of the EATCS 95, 59–93 (2008)
Sherstov, A.A.: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. STOC, pp. 523–532 (2010)
Sherstov, A.A.: The pattern matrix method. SIAM J. Comput. 40(6), 1969–2000 (2011)
Sherstov, A.A.: Separating \(\text{ AC }^0\) from depth-2 majority circuits. SIAM J. Comput. 28(6), 2113–2129 (2009)
Sherstov, A.A.: Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput. 41(5), 1122–1165 (2012)
Sherstov, A.A.: The multiparty communication complexity of set disjointness. STOC, pp. 525–524 (2012)
Sherstov, A.A.: The intersection of two halfspaces has high threshold degree. FOCS, pp. 343–362 (2009). (To appear in SIAM J. Comput. (special issue for FOCS 2009))
Shi, Y.: Approximating linear restrictions of Boolean functions. Manuscript (2002) web.eecs.umich.edu/shiyy/mypapers/linear02-j.ps
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bun, M., Thaler, J. (2015). Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)