License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.38
URN: urn:nbn:de:0030-drops-115340
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11534/
Go to the corresponding LIPIcs Volume Portal

Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials

pdf-format:
LIPIcs-ISAAC-2019-38.pdf (0.5 MB)

Abstract

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:
- We show an explicit O^*(binom{n}{downarrow k/2})-size ABP construction for noncommutative permanent polynomial of k x n symbolic matrix. We obtain this via an explicit ABP construction of size O^*(binom{n}{downarrow k/2}) for S_{n,k}^*, 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 x n symbolic matrix.
- In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is #W[1]-hard.

BibTeX - Entry

@InProceedings{arvind_et_al:LIPIcs:2019:11534,
  author =	{V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay},
  title =	{{On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11534},
  URN =		{urn:nbn:de:0030-drops-115340},
  doi =		{10.4230/LIPIcs.ISAAC.2019.38},
  annote =	{Keywords: Determinant, Permanent, Parameterized Complexity, Branching Programs}
}

Keywords: Determinant, Permanent, Parameterized Complexity, Branching Programs
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI