Lower Bounds for Multilinear Order-Restricted ABPs

Authors C. Ramya, B. V. Raghavendra Rao



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.52.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

C. Ramya
  • Chennai Mathematical Institute, Chennai, India
B. V. Raghavendra Rao
  • IIT Madras, Chennai, India

Cite AsGet BibTex

C. Ramya and B. V. Raghavendra Rao. Lower Bounds for Multilinear Order-Restricted ABPs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.52

Abstract

Proving super-polynomial lower bounds on the size of syntactic multilinear Algebraic Branching Programs (smABPs) computing an explicit polynomial is a challenging problem in Algebraic Complexity Theory. The order in which variables in {x_1,...,x_n} appear along any source to sink path in an smABP can be viewed as a permutation in S_n. In this article, we consider the following special classes of smABPs where the order of occurrence of variables along a source to sink path is restricted: 1) Strict circular-interval ABPs: For every sub-program the index set of variables occurring in it is contained in some circular interval of {1,..., n}. 2) L-ordered ABPs: There is a set of L permutations (orders) of variables such that every source to sink path in the smABP reads variables in one of these L orders, where L <=2^{n^{1/2 -epsilon}} for some epsilon>0. We prove exponential (i.e., 2^{Omega(n^delta)}, delta>0) lower bounds on the size of above models computing an explicit multilinear 2n-variate polynomial in VP. As a main ingredient in our lower bounds, we show that any polynomial that can be computed by an smABP of size S, can be written as a sum of O(S) many multilinear polynomials where each summand is a product of two polynomials in at most 2n/3 variables, computable by smABPs. As a corollary, we show that any size S syntactic multilinear ABP can be transformed into a size S^{O(sqrt{n})} depth four syntactic multilinear Sigma Pi Sigma Pi circuit where the bottom Sigma gates compute polynomials on at most O(sqrt{n}) variables. Finally, we compare the above models with other standard models for computing multilinear polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Circuit complexity
Keywords
  • Computational complexity
  • Algebraic complexity theory
  • Polynomials

Metrics

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

References

  1. Manindra Agrawal and V. Vinay. Arithmetic Circuits: A Chasm at Depth Four. In FOCS, pages 67-75, 2008. https://doi.org/10.1109/FOCS.
  2. Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 11:1-11:16, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.11.
  3. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. TOCT, 10(1):3:1-3:30, 2018. URL: https://doi.org/10.1145/3170709.
  4. Vikraman Arvind and S. Raja. Some Lower Bound Results for Set-Multilinear Arithmetic Computations. Chicago J. Theor. Comput. Sci., 2016, 2016. URL: http://cjtcs.cs.uchicago.edu/articles/2016/6/contents.html.
  5. Walter Baur and Volker Strassen. The Complexity of Partial Derivatives. Theor. Comput. Sci., 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  6. Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. Electronic Colloquium on Computational Complexity (ECCC), 25:62, 2018. URL: https://eccc.weizmann.ac.il/report/2018/062.
  7. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 21:1-21:15, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.21.
  8. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 615-624, 2012. URL: https://doi.org/10.1145/2213977.2214034.
  9. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 867-875, 2014. URL: https://doi.org/10.1145/2591796.2591816.
  10. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs. Theory of Computing, 13(1):1-21, 2017. URL: https://doi.org/10.4086/toc.2017.v013a002.
  11. Maurice J. Jansen. Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, pages 407-418, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_33.
  12. Maurice J. Jansen, Youming Qiao, and Jayalal Sarma. Deterministic Black-Box Identity Testing π-Ordered Algebraic Branching Programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, pages 296-307, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.296.
  13. Mrinal Kumar. A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.19.
  14. Mrinal Kumar, Rafael Mendes de Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. Electronic Colloquium on Computational Complexity (ECCC), 26:19, 2019. URL: https://eccc.weizmann.ac.il/report/2019/019.
  15. Noam Nisan. Lower Bounds for Non-Commutative Computation (Extended Abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418, 1991. URL: https://doi.org/10.1145/103418.103462.
  16. C. Ramya and B. V. Raghavendra Rao. Lower Bounds for Special Cases of Syntactic Multilinear ABPs. In Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings, pages 701-712, 2018. URL: https://doi.org/10.1007/978-3-319-94776-1_58.
  17. C. Ramya and B. V. Raghavendra Rao. Lower bounds for multilinear bounded order ABPs. CoRR, abs/1901.04377, 2019. URL: http://arxiv.org/abs/1901.04377.
  18. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009. URL: https://doi.org/10.1145/1502793.1502797.
  19. Ran Raz and Amir Yehudayoff. Balancing Syntactically Multilinear Arithmetic Circuits. Computational Complexity, 17(4):515-535, 2008. URL: https://doi.org/10.1007/s00037-008-0254-0.
  20. Ran Raz and Amir Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171-207, 2009. URL: https://doi.org/10.1007/s00037-009-0270-8.
  21. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity, 2017. URL: https://github.com/dasarpmar/lowerbounds-survey/releases.
  22. Sébastien Tavenas. Improved Bounds for Reduction to Depth 4 and Depth 3. In MFCS, pages 813-824, 2013. URL: https://doi.org/10.1007/978-3-642-40313-2_71.
  23. Leslie G. Valiant. Completeness Classes in Algebra. In STOC, pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
  24. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput., 12(4):641-644, 1983. https://doi.org/10.1137/0212043.
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