On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials

Authors V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.38.pdf
  • Filesize: 486 kB
  • 13 pages

Document Identifiers

Author Details

V. Arvind
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Abhranil Chatterjee
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Rajit Datta
  • Chennai Mathematical Institute, Chennai, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, Chennai, India

Cite AsGet BibTex

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.38

Abstract

We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polynomials of the rectangular symbolic matrix in both commutative and noncommutative settings. The main results are: - We show an explicit O^*(binom{n}{downarrow k/2})-size ABP construction for noncommutative permanent polynomial of k x n symbolic matrix. We obtain this via an explicit ABP construction of size O^*(binom{n}{downarrow k/2}) for S_{n,k}^*, noncommutative symmetrized version of the elementary symmetric polynomial S_{n,k}. - We obtain an explicit O^*(2^k)-size ABP construction for the commutative rectangular determinant polynomial of the k x n symbolic matrix. - In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is #W[1]-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation
Keywords
  • Determinant
  • Permanent
  • Parameterized Complexity
  • Branching Programs

Metrics

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

References

  1. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. CoRR, abs/1807.04496, 2018. URL: http://arxiv.org/abs/1807.04496.
  2. Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, pages 25-36, 2009. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2304.
  3. Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 677-686, 2010. URL: https://doi.org/10.1145/1806689.1806782.
  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Paths and Packings in Halves. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, pages 578-586, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  5. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Evaluation of permanents in rings and semirings. Inf. Process. Lett., 110(20):867-870, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.005.
  6. Markus Bläser. Noncommutativity Makes Determinants Hard. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 243, pages 172-183, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_15.
  7. Steve Chien, Prahladh Harsha, Alistair Sinclair, and Srikanth Srinivasan. Almost settling the hardness of noncommutative determinant. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 499-508, 2011. URL: https://doi.org/10.1145/1993636.1993703.
  8. Ioannis Koutis and Ryan Williams. LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algorithms, 12(3):31:1-31:18, 2016. URL: https://doi.org/10.1145/2885499.
  9. 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.
  10. Virginia Vassilevska Williams and Ryan Williams. Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput., 42(3):831-854, 2013. URL: https://doi.org/10.1137/09076619X.
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