LIPIcs.ISAAC.2019.38.pdf
- Filesize: 486 kB
- 13 pages
Document
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
Authors
-
Part of:
Volume:
30th International Symposium on Algorithms and Computation (ISAAC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-28
Cite As Get 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)
0PDF Downloads
References
- 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.
- 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.
- 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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.