The paper gives explicit optimal-size algebraic branching programs for the noncommutative rectangular permanent and for the commutative rectangular determinant, plus a #W[1]-hardness result for evaluating the noncommutative rectangular determinant over matrices.
Counting paths and packings in halves
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
The paper gives explicit optimal-size algebraic branching programs for the noncommutative rectangular permanent and for the commutative rectangular determinant, plus a #W[1]-hardness result for evaluating the noncommutative rectangular determinant over matrices.