#

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

Partha Mukhopadhyay

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:

- 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}$.
- We obtain an explicit $O^{*}(2^k)$-size ABP construction for the
commutative rectangular determinant polynomial of the $k\times n$
symbolic matrix.
- 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