On Explicit Branching Programs for the Rectangular Determinant and\n Permanent Polynomials

2019/08/22 by V. Arvind, Abhranil Chatterjee, Arvind, V. +5
Computer Science · #Advanced Graph Theory Research #Cellular Automata and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1908.08347

openalex publication_date 2019/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the arithmetic circuit complexity of some well-known family of\npolynomials through the lens of parameterized complexity. Our main focus is on\nthe construction of explicit algebraic branching programs (ABP) for determinant\nand permanent polynomials of the \rectangular symbolic matrix in both\ncommutative and noncommutative settings. The main results are:\n 1. We show an explicit O^*(n choose downarrow k/2)-size ABP\nconstruction for noncommutative permanent polynomial of k\× n symbolic\nmatrix. We obtain this via an explicit ABP construction of size\nO^*(n choose downarrow k/2) for S_n,k^*, noncommutative\nsymmetrized version of the elementary symmetric polynomial S_n,k.\n 2. We obtain an explicit O^*(2^k)-size ABP construction for the\ncommutative rectangular determinant polynomial of the k\× n symbolic\nmatrix.\n 3. In contrast, we show that evaluating the rectangular noncommutative\ndeterminant over rational matrices is W[1]-hard.\n

Related

• Determinants vs. Algebraic Branching Programs
• On the hardness of the noncommutative determinant
• Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion
• On Finer Separations between Subclasses of Read-once Oblivious ABPs
• Schur Polynomials do not have small formulas if the Determinant doesn't!