On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
share
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: 1. We show an explicit O^*(n↓ k/2)-size ABP construction for noncommutative permanent polynomial of k× n symbolic matrix. We obtain this via an explicit ABP construction of size O^*(n↓ k/2) for S_n,k^*, 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× n symbolic matrix. 3. In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is W[1]-hard.
READ FULL TEXT