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

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

CC BY-SA 4.0
2020-01-31T11:57:25.010Z
2020-01-31T11:57:25.010Z
smapers
<p>I know that for an arbitrary <span class="math-container">$n \times n$</span> matrix, Ryser's algorithm can compute the permanent in <span class="math-container">$\mathcal{O}(2^n n^2)$</span> time. I'm interested in computing the permanent of <span class="math-container">$n \times n$</span> matrices of rank <span class="math-container">$m$</span>. A few sources told me that this algorithm is exponential in <span class="math-container">$m$</span>. The algorithm must also depend on <span class="math-container">$n$</span>, so what is the <span class="math-container">$\mathcal{O}$</span>-notation for this? <span class="math-container">$\mathcal{O}(2^m n^2)$</span>? <span class="math-container">$\mathcal{O}(n^m)$</span>? </p>

CC BY-SA 4.0
2020-01-30T17:59:52.540Z
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
<cc.complexity-theory><linear-algebra><matrices>
The complexity of the permanent of low rank matrices
Teferi
# The complexity of the permanent of low rank matrices

(Asked by: username_0 on 2020-01-30)

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)$?

**Tags:** cc.complexity-theory, linear-algebra, matrices

> **Comments:**
> **username_1**: 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)}$.  

---

## 1 answers

### Answer by username_1 on 2020-01-31. Score: 10 | Accepted answer

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.)*


---

