Document Open Access Logo

Lower Bounds for the Approximate Degree of Block-Composed Functions

Author Justin Thaler

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.17.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Justin Thaler

Cite As Get BibTex

Justin Thaler. Lower Bounds for the Approximate Degree of Block-Composed Functions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.17

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

Subject Classification

Keywords
  • approximate degree
  • one-sided approximate degree
  • polynomial approx- imations
  • threshold degree
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory. TOCT, 1(1), 2009. Google Scholar
  2. Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595-605, 2004. Google Scholar
  3. Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(1):37-46, 2005. Google Scholar
  4. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In FOCS, pages 337-347, 1986. Google Scholar
  5. Theodore P. Baker, John Gill, and Robert Solovay. Relativizations of the P =? NP question. SIAM J. Comput., 4(4):431-442, 1975. Google Scholar
  6. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, 2001. Google Scholar
  7. Richard Beigel. Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity, 4:339-349, 1994. Google Scholar
  8. Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In CCC, pages 24-32, 2007. Google Scholar
  9. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and markov-bernstein inequalities. In ICALP (1), pages 303-314, 2013. Google Scholar
  10. Mark Bun and Justin Thaler. Hardness amplification and the approximate degree of constant-depth circuits. In ICALP, Part I, pages 268-280, 2015. Google Scholar
  11. Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan. Faster private release of marginals on small databases. In ITCS, pages 387-402, 2014. Google Scholar
  12. Arkadev Chattopadhyay and Anil Ada. Multiparty communication complexity of disjointness. Electronic Colloquium on Computational Complexity (ECCC), 15(002), 2008. Google Scholar
  13. Matei David and Toniann Pitassi. Separating NOF communication complexity classes RP and NP. Electronic Colloquium on Computational Complexity (ECCC), 15(014), 2008. Google Scholar
  14. Matei David, Toniann Pitassi, and Emanuele Viola. Improved separations between nondeterministic and randomized multiparty communication. TOCT, 1(2), 2009. Google Scholar
  15. R. de Wolf. A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Information & Computation, 8(10):943-950, 2010. Google Scholar
  16. Dmitry Gavinsky and A. A. Sherstov. A separation of NP and conp in multiparty communication complexity. Theory of Computing, 6(1):227-245, 2010. Google Scholar
  17. Dmitry Gavinsky and A. A. Sherstov. A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6(1):227-245, 2010. Google Scholar
  18. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. Electronic Colloquium on Computational Complexity (ECCC), 22:49, 2015. To appear in ICALP, 2016. Google Scholar
  19. Russell Impagliazzo and Ryan Williams. Communication complexity with synchronized clocks. In CCC, pages 259-269, 2010. Google Scholar
  20. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777-1805, 2008. Google Scholar
  21. Varun Kanade and Justin Thaler. Distribution-independent reliable learning. In COLT, pages 3-24, 2014. Google Scholar
  22. Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20-46, 2007. Google Scholar
  23. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2^\~o(n^1/3). J. Comput. Syst. Sci., 68(2):303-318, 2004. Google Scholar
  24. Adam R. Klivans and Rocco A. Servedio. Toward attribute efficient learning of decision lists and parities. Journal of Machine Learning Research, 7:587-602, 2006. Google Scholar
  25. Samuel Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing, 1(1):29-36, 2005. Google Scholar
  26. Troy Lee. A note on the sign degree of formulas. CoRR, abs/0909.4607, 2009. Google Scholar
  27. Troy Lee and Adi Shraibman. Disjointness is hard in the multiparty number-on-the-forehead model. Computational Complexity, 18(2):309-336, 2009. Google Scholar
  28. Nati Linial and Adi Shraibman. Learning complexity vs. communication complexity. In CCC, pages 53-63, 2008. Google Scholar
  29. Nati Linial and Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms, 34(3):368-394, 2009. Google Scholar
  30. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Google Scholar
  31. Periklis A. Papakonstantinou, Dominik Scheder, and Hao Song. Overlays and limited memory communication. In CCC, pages 298-308, 2014. Google Scholar
  32. Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In STOC, pages 468-474, 1992. Google Scholar
  33. Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. J. Comput. Syst. Sci., 33(1):106-123, 1986. Google Scholar
  34. Anup Rao and Amir Yehudayoff. Simplified lower bounds on the multiparty communication complexity of disjointness. In CCC, pages 88-101, 2015. Google Scholar
  35. A. A. Razborov and A. A. Sherstov. The sign-rank of ac⁰. SIAM J. Comput., 39(5):1833-1855, 2010. Google Scholar
  36. Rocco A. Servedio, Li-Yang Tan, and Justin Thaler. Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions. In COLT, pages 14.1-14.19, 2012. Google Scholar
  37. A. A. Sherstov. Halfspace matrices. Computational Complexity, 17(2):149-178, 2008. Google Scholar
  38. A. A. Sherstov. Approximate inclusion-exclusion for arbitrary symmetric functions. Computational Complexity, 18(2):219-247, 2009. Google Scholar
  39. A. A. Sherstov. Separating AC⁰ from depth-2 majority circuits. SIAM J. Comput., 38(6):2113-2129, 2009. Google Scholar
  40. A. A. Sherstov. The pattern matrix method. SIAM J. Comput., 40(6):1969-2000, 2011. Google Scholar
  41. A. A. Sherstov. Strong direct product theorems for quantum communication and query complexity. In STOC, pages 41-50, 2011. Google Scholar
  42. A. A. Sherstov. The multiparty communication complexity of set disjointness. In STOC, pages 525-548, 2012. Google Scholar
  43. A. A. Sherstov. Approximating the AND-OR tree. Theory of Computing, 9(20):653-663, 2013. Google Scholar
  44. A. A. Sherstov. Communication lower bounds using directional derivatives. In STOC, pages 921-930, 2013. Google Scholar
  45. A. A. Sherstov. The intersection of two halfspaces has high threshold degree. SIAM J. Comput., 42(6):2329-2374, 2013. Google Scholar
  46. A. A. Sherstov. Breaking the Minsky-Papert barrier for constant-depth circuits. In STOC, pages 223-232, 2014. Google Scholar
  47. A. A. Sherstov. The power of asymmetry in constant-depth circuits. In FOCS, pages 431-450, 2015. Google Scholar
  48. Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5):444-460, 2009. Google Scholar
  49. Justin Thaler, Jonathan Ullman, and Salil P. Vadhan. Faster algorithms for privately releasing marginals. In ICALP, Part I, pages 810-821, 2012. Google Scholar
  50. S. Toda. On the computational power of PP and +P. In FOCS, pages 514-519, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact