Abstract
The ε-approximate degree of a Boolean function f: { − 1, 1}n → { − 1, 1} is the minimum degree of a real polynomial that approximates f to within ε in the ℓ ∞ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the ε-approximate degree of the two-level AND-OR tree for any constant ε > 0. We show that this quantity is \(\Theta(\sqrt{n})\), closing a line of incrementally larger lower bounds [3,11,21,30,32]. The same lower bound was recently obtained independently by Sherstov using related techniques [25]. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek [34]. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.
The full version of this paper is available at http://arxiv.org/abs/1302.6191
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: Proc. of Foundations of Computer Science (FOCS), p. 3 (2008), Slides available at http://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 of Computing 1(1), 37–46 (2005)
Chattopadhyay, A., Ada, A.: Multiparty communication complexity of disjointness. Electronic Colloquium on Computational Complexity (ECCC) 15(002) (2008)
Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bound by polynomials. Journal of the ACM 48(4), 778–797 (2001)
Beame, P., Machmouchi, W.: The quantum query complexity of AC0. Quantum Information & Computation 12(7-8), 670–676 (2012)
Beigel, R.: The polynomial method in circuit complexity. In: Proc. of the Conference on Structure in Complexity Theory, pp. 82–95 (1993)
Beigel, R.: Perceptrons, PP, and the polynomial hierarchy. In: Computational Complexity, vol. 4, pp. 339–349 (1994)
Bernstein, S.N.: On the V. A. Markov theorem. Trudy Leningr. Industr. In-ta, no 5, razdel fiz-matem nauk, 1 (1938)
Buhrman, H., Vereshchagin, N.K., de Wolf, R.: On computation and communication with small bias. In: Proc. of the Conference on Computational Complexity, pp. 24–32 (2007)
Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 291–299. Springer, Heidelberg (2003)
Gavinsky, D., Sherstov, A.A.: A separation of NP and coNP in multiparty communication complexity. Theory of Computing 6(1), 227–245 (2010)
Kalai, A., Klivans, A.R., Mansour, Y., Servedio, R.A.: Agnostically learning halfspaces. SIAM Journal on Computing 37(6), 1777–1805 (2008)
Klauck, H., Špalek, R., de Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing 36(5), 1472–1493 (2007)
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., Sherstov, A.A.: Lower bounds for agnostic learning via approximate rank. Computational Complexity 19(4), 581–604 (2010)
Lee, T., Shraibman, A.: Disjointness is hard in the multi-party number-on-the-forehead model. In: Proc. of the Conference on Computational Complexity, pp. 81–91 (2008)
Markov, V.: On functions which deviate least from zero in a given interval, St. Petersburg (1892) (Russian)
Minsky, M.L., Papert, S.A.: Perceptions: An Introduction to Computational Geometry. MIT Press, Cambridge (1969)
Open problems in analysis of Boolean functions. Compiled for the Simons Symposium. CoRR, abs/1204.6447, February 5-11 (2012)
Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity 4, 301–313 (1994)
Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions (Preliminary Version). In: Proc. of the Symp. on Theory of Computing (STOC), pp. 468–474 (1992)
Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, New York (1986)
Sherstov, A.A.: Approximate inclusion-exclusion for arbitrary symmetric functions. Computational Complexity 18(2), 219–247 (2009)
Sherstov, A.A.: Approximating the AND-OR tree. Electronic Colloquium on Computational Complexity (ECCC) 20(023) (2013)
Sherstov, A.A.: Communication lower bounds using dual polynomials. Bulletin of the EATCS 95, 59–93 (2008)
Sherstov, A.A.: The pattern matrix method. SIAM J. Comput. 40(6), 1969–2000 (2011)
Sherstov, A.A.: Making polynomials robust to noise. In: Proceedings of Symp. Theory of Computing, pp. 747–758 (2012)
Sherstov, A.A.: Separating AC0 from depth-2 majority circuits. SIAM Journal on Computing 28(6), 2113–2129 (2009)
Sherstov, A.A.: The intersection of two halfspaces has high threshold degree. In: Proc. of Foundations of Computer Science (FOCS), pp. 343–362 (2009); To appear in SIAM J. Comput. (special issue for FOCS 2009)
Sherstov, A.A.: The multiparty communication complexity of set disjointness. In: Proceedings of Symp. Theory of Computing, pp. 525–548 (2012)
Shi, Y.: Approximating linear restrictions of Boolean functions. Manuscript (2002), http://web.eecs.umich.edu/~shiyy/mypapers/linear02-j.ps
Shi, Y., Zhu, Y.: Quantum communication complexity of block-composed functions. Quantum Information & Computation 9(5), 444–460 (2009)
Špalek, R.: A dual polynomial for OR. Manuscript (2008), http://arxiv.org/abs/0803.4516
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bun, M., Thaler, J. (2013). Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)