On explicit branching programs for the rectangular determinant and permanent polynomials

DOI10.4086/CJTCS.2020.002MaRDI QIDQ4988301zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Publication date 14 May 2021

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.08347

zbMATH Keywords

rectangular determinantrectangular permanent

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Networks and circuits as models of computation; circuit complexity (68Q06) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On hard instances of non-commutative permanent
• Algebras with Polynomial Identities and Computing the Determinant
• On the hardness of the noncommutative determinant
• On hard instances of non-commutative permanent
• Almost settling the hardness of noncommutative determinant

Cites work

• Evaluation of permanents in rings and semirings
• Fast Parallel Computation of Polynomials Using Few Processors
• LIMITS and applications of group algebras for parameterized problems
• Noncommutativity makes determinants hard
• Quaternionic determinants

Cited in

(4)

• On hard instances of non-commutative permanent
• Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
• A subquadratic upper bound on Hurwitz's problem and related noncommutative polynomials
• On hard instances of non-commutative permanent

This page was built for publication: On explicit branching programs for the rectangular determinant and permanent polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4988301)