5
$\begingroup$

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)|<B$ where $B$ is part of input.

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Feb 16 '17 at 0:24
  • $\begingroup$ oops sorry I confused things. I am aware of $2^k$ case. $\endgroup$ – T.... Feb 16 '17 at 0:29
  • $\begingroup$ 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? $\endgroup$ – Joshua Grochow Feb 16 '17 at 1:38
  • $\begingroup$ @JoshuaGrochow part of input. $\endgroup$ – T.... Feb 16 '17 at 1:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Feb 16 '17 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.