<p>Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|&lt;B$ where $B$ is part of input.</p>

<p>Is there a way to compute $Per(M)$ faster than $O(n2^n)$ in this case? Note if $B=2^{o(n)}$ there is a faster way. So I am interested in $B=2^{\Omega(n)}$ case.</p>

<p>Given any $\alpha\in(0,1)$ is there an efficient algorithm to compute $Per(M)$ approximately to any non-trivial (say $2^{o(n^\alpha)}$) factor when $B=2^{\omega(n^\alpha)}$ holds that runs in $2^{o(n^\alpha)}$ time?</p>

CC BY-SA 3.0
2017-02-16T00:24:07.463Z
Your original question doesn't quite match the motivation you state afterwards. For computing perm mod $2^k$ for any $k$ is in P, so if you want only care about inputs with the promise that $|Per(M)| < B$, then simply choose $2^k > B$ and apply the poly-time algorithm. But if you want to know perm mod 3 under the promise that the perm is bounded in absolute value, then that's obviously a different story. Maybe this answers your question, or maybe you want to refine/change your question a little?
Joshua Grochow
CC BY-SA 3.0
2017-02-16T00:29:38.813Z
oops sorry I confused things. I am aware of $2^k$ case.
Turbo
CC BY-SA 3.0
2017-02-16T01:38:58.523Z
Okay, then it seems like the 2^k algorithm solves your problem. Do you mean for B to be part of the input, or to be fixed independent of the input?
Joshua Grochow
CC BY-SA 3.0
2017-02-16T01:39:31.513Z
@JoshuaGrochow part of input.
Turbo
CC BY-SA 3.0
2017-02-16T01:53:54.903Z
Okay, that wasn't clear from the question. As you can tell from my first comment, based on how the question is currently phrased, I thought you wanted to do it where B was a promise, not part of the input. Please clarify up front in the question.
Joshua Grochow
CC BY-SA 3.0
2017-02-16T01:54:55.100Z
@JoshuaGrochow isnt that the natural non-trivial case?
Turbo
CC BY-SA 3.0
2017-02-16T02:21:47.057Z
Yes, if you know about the 2^k algorithm, but the reader (including me, prior to our discussion) has no way of knowing that the questioner is aware of the 2^k algorithm. And the way it's worded, "in this case", suggests the promise problem, not the setting where B is part of the input.
Joshua Grochow
CC BY-SA 3.0
2017-02-18T09:25:34.403Z
@JoshuaGrochow Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?
Turbo
<cc.complexity-theory><ds.algorithms><approximation-algorithms><matrices><permanent>
On permanent of $\{\pm1,0\}$ matrices
Turbo
# On permanent of $\{\pm1,0\}$ matrices

(Asked by: username_0 on 2017-02-15)

Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|

Is there a way to compute $Per(M)$ faster than $O(n2^n)$ in this case? Note if $B=2^{o(n)}$ there is a faster way. So I am interested in $B=2^{\Omega(n)}$ case.

Given any $\alpha\in(0,1)$ is there an efficient algorithm to compute $Per(M)$ approximately to any non-trivial (say $2^{o(n^\alpha)}$) factor when $B=2^{\omega(n^\alpha)}$ holds that runs in $2^{o(n^\alpha)}$ time?

**Tags:** cc.complexity-theory, ds.algorithms, approximation-algorithms, matrices, permanent
> **Comments:**
> **username_1**: Your original question doesn't quite match the motivation you state afterwards. For computing perm mod $2^k$ for any $k$ is in P, so if you want only care about inputs with the promise that $|Per(M)| < B$, then simply choose $2^k > B$ and apply the poly-time algorithm. But if you want to know perm mod 3 under the promise that the perm is bounded in absolute value, then that's obviously a different story. Maybe this answers your question, or maybe you want to refine/change your question a little?  
> **username_0**: oops sorry I confused things. I am aware of $2^k$ case.  
> **username_1**: Okay, then it seems like the 2^k algorithm solves your problem. Do you mean for B to be part of the input, or to be fixed independent of the input?  
> **username_0**: @JoshuaGrochow part of input.  
> **username_1**: Okay, that wasn't clear from the question. As you can tell from my first comment, based on how the question is currently phrased, I thought you wanted to do it where B was a promise, not part of the input. Please clarify up front in the question.  
> **username_0**: @JoshuaGrochow isnt that the natural non-trivial case?  
> **username_1**: Yes, if you know about the 2^k algorithm, but the reader (including me, prior to our discussion) has no way of knowing that the questioner is aware of the 2^k algorithm. And the way it's worded, "in this case", suggests the promise problem, not the setting where B is part of the input.  
> **username_0**: @JoshuaGrochow Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?  

---

## 0 answers

