Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Barriers for Rank Methods in Arithmetic Complexity

Authors Klim Efremenko, Ankit Garg, Rafael Oliveira, Avi Wigderson

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.1.pdf
  • Filesize: 0.63 MB
  • 19 pages

Document Identifiers

Author Details

Klim Efremenko
Ankit Garg
Rafael Oliveira
Avi Wigderson

Cite AsGet BibTex

Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.1

Abstract

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive. At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study. In this paper we address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (under the name of flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular, 1. Rank methods cannot prove better than (2^d)*n^(d/2) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.) 2. Rank methods cannot prove (d+1)n^(d/2) on the Waring rank of any n-variate polynomial of degree d. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.) The proofs of these bounds use simple linear-algebraic arguments, leveraging connections between the symbolic rank of matrix polynomials and the usual rank of their evaluations. These techniques can perhaps be extended to barriers for other arithmetic models on which progress has halted. To see how these barrier results directly inform the state-of-art in arithmetic complexity we note the following. First, the bounds above nearly match the best explicit bounds we know for these models, hence offer an explanations why the rank methods got stuck there. Second, the bounds above are a far cry (quadratically away) from the true complexity (e.g. of random polynomials) in these models, which if achieved (by any methods), are known to imply super-polynomial formula lower bounds. We also explain the relation of our barrier results to other attempts, and in particular how they significantly differ from the recent attempts to find analogues of "natural proofs" for arithmetic complexity. Finally, we discuss the few arithmetic lower bound approaches which fall outside rank methods, and some natural directions our barriers suggest.
Keywords
  • Lower Bounds
  • Barriers
  • Partial Derivatives
  • Flattenings
  • Algebraic Complexity

Metrics

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

References

  1. Scott Aaronson and Andrew Drucker. Arithmetic natural proofs theory is sought. Blog post, 2008. Google Scholar
  2. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory (TOCT), 1(1):2, 2009. Google Scholar
  3. James Alexander and André Hirschowitz. Polynomial interpolation in several variables. Journal of Algebraic Geometry, 4(2):201-222, 1995. Google Scholar
  4. Boris Alexeev, Michael A Forbes, and Jacob Tsimerman. Tensor rank: Some lower and upper bounds. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 283-291. IEEE, 2011. Google Scholar
  5. Anima Anandkumar, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Yi-Kai Liu. A spectral algorithm for latent dirichlet allocation. In Advances in Neural Information Processing Systems, pages 917-925, 2012. Google Scholar
  6. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the p=?np question. SIAM Journal on computing, 4(4):431-442, 1975. Google Scholar
  7. Peter Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7. Springer Science &Business Media, 2013. Google Scholar
  8. Peter Bürgisser, Michael Clausen, and Amin Shokrollahi. Algebraic complexity theory, volume 315. Springer Science &Business Media, 2013. Google Scholar
  9. Peter Bürgisser and Christian Ikenmeyer. Geometric complexity theory and tensor rank. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 509-518. ACM, 2011. Google Scholar
  10. Enrico Carlini, Maria Virginia Catalisano, and Anthony V Geramita. The solution to the waring problem for monomials and the sum of coprime monomials. Journal of algebra, 370:5-14, 2012. Google Scholar
  11. Joseph T Chang. Full reconstruction of markov models on evolutionary trees: identifiability and consistency. Mathematical biosciences, 137(1):51-73, 1996. Google Scholar
  12. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Now Publishers Inc, 2011. Google Scholar
  13. Richard DeMillo and Richard Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  14. Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for rank methods in arithmetic complexity. arXiv preprint arXiv:1710.09502, 2017. Google Scholar
  15. Michael A Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 867-875. ACM, 2014. Google Scholar
  16. Michael A Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. arXiv preprint arXiv:1701.05328, 2017. Google Scholar
  17. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM Journal on Computing, 44(5):1173-1201, 2015. Google Scholar
  18. Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions. arXiv preprint arXiv:1706.05598, 2017. Google Scholar
  19. Fulvio Gesmundo and JM Landsberg. Explicit polynomial sequences with maximal spaces of partial derivatives and a question of k. mulmuley. arXiv preprint arXiv:1705.03866, 2017. Google Scholar
  20. Joshua A Grochow. Unifying known lower bounds via geometric complexity theory. computational complexity, 24(2):393-475, 2015. Google Scholar
  21. Joshua A Grochow, Mrinal Kumar, Michael Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv preprint arXiv:1701.01717, 2017. Google Scholar
  22. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the chasm at depth four. J. ACM, 61(6):33:1-33:16, 2014. URL: http://dx.doi.org/10.1145/2629541.
  23. Johan Håstad. Tensor rank is np-complete. Journal of Algorithms, 11(4):644-654, 1990. Google Scholar
  24. Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871-898, 2011. Google Scholar
  25. Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 11-20. ACM, 2013. Google Scholar
  26. Laurent Hyafil. On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2):120-123, 1979. Google Scholar
  27. N. Kayal, N. Limaye, C. Saha, and S. Srinivasan. Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, pages 119-127, 2014. Google Scholar
  28. Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19:81, 2012. URL: http://eccc.hpi-web.de/report/2012/081.
  29. Mrinal Kumar and Ramprasad Saptharishi. An exponential lower bound for homogeneous depth-5 circuits over finite fields. arXiv preprint arXiv:1507.00177, 2015. Google Scholar
  30. Mrinal Kumar and Shubhangi Saraf. Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. In International Colloquium on Automata, Languages, and Programming, pages 751-762. Springer, 2014. Google Scholar
  31. JM Landsberg. Nontriviality of equations and explicit tensors in cm cm cm of border rank at least 2m- 2. Journal of Pure and Applied Algebra, 219(8):3677-3684, 2015. Google Scholar
  32. Joseph M Landsberg. Tensors: geometry and applications, volume 128. American Mathematical Society Providence, RI, 2012. Google Scholar
  33. Joseph M Landsberg. Geometry and Complexity Theory. Cambridge, 2017. Google Scholar
  34. Joseph M Landsberg and Giorgio Ottaviani. New lower bounds for the border rank of matrix multiplication. Theory of Computing, 11(11):285-298, 2015. Google Scholar
  35. Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov models. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 366-375. ACM, 2005. Google Scholar
  36. N. Nisan and A. Wigderson. Lower bound on arithmetic circuits via partial derivatives. Computational Complexity, 6:217-234, 1996. Google Scholar
  37. Noam Nisan. Lower bounds for non-commutative computation. STOC, pages 410-418, 1991. Google Scholar
  38. Aaron Potechin. A note on amortized space complexity. arXiv preprint arXiv:1611.06632, 2016. Google Scholar
  39. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. Journal of the ACM (JACM), 56(2):8, 2009. Google Scholar
  40. Ran Raz. Tensor-rank and lower bounds for arithmetic formulas. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 659-666. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806780.
  41. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
  42. Alexander Razborov. On submodular complexity measures. URL: http://people.cs.uchicago.edu/~razborov/files/sub.pdf.
  43. Alexander A Razborov. On the method of approximations. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 167-176. ACM, 1989. Google Scholar
  44. Alexander A Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81-93, 1990. Google Scholar
  45. Alexander A Razborov and Steven Rudich. Natural proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 204-213. ACM, 1994. Google Scholar
  46. Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A Cook. Exponential lower bounds for monotone span programs. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 406-415. IEEE, 2016. Google Scholar
  47. Jack Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701-717, 1980. Google Scholar
  48. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trendsregistered in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  49. Roman Smolensky. On representations by low-degree polynomials. In Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on, pages 130-138. IEEE, 1993. Google Scholar
  50. James Joseph Sylvester. Lx. on a remarkable discovery in the theory of canonical forms and of hyperdeterminants. Philosophical Magazine Series 4, 2(12):391-410, 1851. Google Scholar
  51. Leslie G Valiant. Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 249-261. ACM, 1979. Google Scholar
  52. Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013. Google Scholar
  53. E. Waring. Meditationes algebraicæ. In Archdeacon, Cambridge, 1770. Google Scholar
  54. Richard Zippel. Probabilistic algorithms for sparse polynomials. EUROSAM, pages 216-226, 1979. 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 Imprint Privacy Contact