### Volume 2020

#### Article 2

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

#### On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials

V. Arvind
The Institute of Mathematical Sciences
HBNI
Chennai, India
arvind AT imsc DOT res DOT in

Abhranil Chatterjee
The Institute of Mathematical Sciences
HBNI
Chennai, India
abhranilc AT imsc DOT res DOT in

Rajit Datta
Chennai Mathematical Institute
Chennai, India
rajit AT cmi DOT res DOT in

and

Chennai Mathematical Institute
Chennai, India
partham AT cmi DOT res DOT in

August 5, 2020

#### 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.

Volume 2020, Article 1 Article 3
Volume 2020 Published articles