# The complexity of the permanent of low rank matrices

I know that for an arbitrary $$n \times n$$ matrix, Ryser's algorithm can compute the permanent in $$\mathcal{O}(2^n n^2)$$ time. I'm interested in computing the permanent of $$n \times n$$ matrices of rank $$m$$. A few sources told me that this algorithm is exponential in $$m$$. The algorithm must also depend on $$n$$, so what is the $$\mathcal{O}$$-notation for this? $$\mathcal{O}(2^m n^2)$$? $$\mathcal{O}(n^m)$$?

• The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-$m$ matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$. – smapers Jan 30 '20 at 17:59

The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $$n^{\mathcal{O}(m)}$$ algorithm for computing the permanent of a rank-m matrix. I don't know whether this can be improved to $$\mathrm{poly}(n) 2^{\mathcal{O}(m)}$$.