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)}$.

(I originally posted this as a comment. I post it as an answer by lack of any other answers.)