Published by the Department of Computer Science, The University of Chicago.

Abstract

We study the arithmetic circuit complexity of some well-known families of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABPs) for the determinant and the permanent polynomials of the rectangular symbolic matrix in both commutative and noncommutative settings. The main results are:

1. We show an explicit $O^{*}({n\choose {\downarrow k/2}})$-size ABP construction for the noncommutative permanent polynomial of a $k\times n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({n\choose {\downarrow k/2}})$ for $S_{n,k}^*$, the noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$.
2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $k\times n$ symbolic matrix.
3. In contrast, we show that evaluating the rectangular noncommutative determinant with rational matrix entries is $\#W[1]$-hard.

• The article: PDF (268 KB)
• Source material: ZIP (210 KB)
• BibTeX entry for this article (355 bytes)

Submitted Submitted November 20,2019, revised July 20, 2020, published August 5, 2020.

© 2020 V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhpadhyay
Licensed under a Creative Commons Attribution License

Volume 2020, Article 1

Article 3

Volume 2020

Published articles