Document Open Access Logo

On Finer Separations Between Subclasses of Read-Once Oblivious ABPs

Authors C. Ramya , Anamay Tengse

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.53.pdf
  • Filesize: 0.86 MB
  • 23 pages

Document Identifiers

Author Details

C. Ramya
  • Chennai Mathematical Institute, India
Anamay Tengse
  • Department of Computer Science, University of Haifa, Israel

Funding

  • Ramya, C.: Research supported by INSPIRE Faculty Fellowship of DST and by a grant from the Infosys Foundation. Part of this work was done when at the Tata Institute of Fundamental Research, Mumbai, India (DAE project 12-R&D-TFR-5.01-0500).
  • Tengse, Anamay: Research supported by the Israel Science Foundation (grant No. 716/20). Part of this work was done when at the Tata Institute of Fundamental Research, Mumbai, India, as a student (DAE project no. 12-R&D-TFR-5.01-0500), and later as a visitor (Prof. Prahladh Harsha’s Swarnajaynti fellowship and Prof. Arkadev Chattopadhyay’s Microsoft Research funds).

Acknowledgements

We thank Ramprasad Saptharishi for numerous insightful discussions about the various structured models, which motivated this work. We also thank Mrinal Kumar for his helpful comments about our work which helped us in enchancing the presentation. We thank Manoj Gopalakrishan and the organisers of Thursday Theory Lunch at IIT Bombay for organising a talk by Debasattam Pal, where we first came across the work of {Möller} and Stetter (1995) that essentially led to the main results in this paper. We thank the anonymous reviewers for their valuable inputs on the earlier version of the paper.

Cite AsGet BibTex

C. Ramya and Anamay Tengse. On Finer Separations Between Subclasses of Read-Once Oblivious ABPs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.53

Abstract

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials). Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank. Our proof of the above result builds on the results of Marinari, Möller and Mora (1993), and Möller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic Complexity Theory
  • Algebraic Branching Programs
  • Commutative Matrices

Metrics

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

Related Versions

References

  1. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  2. Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A quadratic lower bound for algebraic branching programs. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 2:1-2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.2.
  3. David A. Cox, John B. Little, and Donal O'Shea. Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer, 2007. URL: https://doi.org/10.1007/978-0-387-35651-8.
  4. David S. Dummit and Richard M. Foote. Abstract Algebra. John Wiley and Sons, Inc., second edition, 1999. Google Scholar
  5. Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena. Demystifying the border of depth-3 algebraic circuits. In 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), 2021. URL: https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf.
  6. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 243-252, 2013. URL: https://doi.org/10.1109/FOCS.2013.34.
  7. Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the complexity of partial derivatives. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 37:1-37:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.37.
  8. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity testing for constant-width, and commutative, read-once oblivious abps. Theory of Computing, 13(1):1-21, 2017. URL: https://doi.org/10.4086/toc.2017.v013a002.
  9. Neeraj Kayal. Affine projections of polynomials. In 44th Annual ACM Symposium on Theory of Computing (STOC 2012), pages 643-662, 2012. URL: https://doi.org/10.1145/2213977.2214036.
  10. Mrinal Kumar and Ben Lee Volk. A lower bound on determinantal complexity. In 36th Annual Computational Complexity Conference (CCC 2021), volume 200 of LIPIcs, pages 4:1-4:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.4.
  11. Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. Electron. Colloquium Comput. Complex., page 81, 2021. URL: https://eccc.weizmann.ac.il/report/2021/081.
  12. M.G. Marinari, H.M. Möller, and T. Mora. Gröbner bases of ideals defined by functionals with an application to ideals of projective points. Applicable Algebra in Engineering, Communication and Computing, 4(2):103-145, 1993. URL: https://doi.org/10.1007/BF01386834.
  13. H. Michael Möller and Hans J. Stetter. Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems. Numerische Mathematik, 70, 1995. URL: https://doi.org/10.1007/s002110050122.
  14. Noam Nisan. Lower bounds for non-commutative computation. In 23rd Annual ACM Symposium on Theory of Computing (STOC 1991), pages 410-418, 1991. URL: https://doi.org/10.1145/103418.103462.
  15. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. URL: https://doi.org/10.1007/BF01294256.
  16. Kevin Pratt. Waring rank, parameterized and exact algorithms. In David Zuckerman, editor, 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 806-823. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00053.
  17. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6(1):135-177, 2010. URL: https://doi.org/10.4086/toc.2010.v006a007.
  18. Chandan Saha. Factoring Polynomials over Finite Fields using Balance Test. In 25th Symposium on Theoretical Aspects of Computer Science (STACS 2008), pages 609-620, 2008. Google Scholar
  19. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  20. Yaroslav Shitov. How hard is the tensor rank?, 2016. URL: http://arxiv.org/abs/1611.01559.
  21. Amir Shpilka and Avi Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10(1):1-27, 2001. URL: https://doi.org/10.1007/PL00001609.
  22. V. Strassen. Gaussian Elimination is not Optimal. Numerische Mathematik, 13(3):354-356, 1969. URL: https://doi.org/10.1007/BF02165411.
  23. Leslie G. Valiant. Completeness Classes in Algebra. In 11th Annual ACM Symposium on Theory of Computing (STOC 1979), pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
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