期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2020
卷号：2020
页码：1-18
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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 ↓k/2 )-size ABP construction for the noncommutative permanent polynomial of a k ×n symbolic matrix. We obtain this via an explicit ABP construction of size O ∗ ( n ↓k/2 ) for S ∗ n,k , the noncommutative symmetrized version of the elementary symmetric polynomial Sn,k. • We obtain an explicit O ∗ (2 k )-size ABP construction for the commutative rectangular determinant polynomial of the k ×n symbolic matrix. • In contrast, we show that evaluating the rectangular noncommutative determinant with rational matrix entries is #W[1]-hard.
