Let $A$ be an $n \times n$ matrix with $0$ or $1$ as entries. Under ETH, the permanent of $A$ cannot be calculated in $exp(o(n))$ time.

Consider $A$ has $O(n^{r})$ entries as $0$ where $r \in [0,2]$. It is reasonable to assume ETH breaks down at $r=0$. Fix a $r_{o} \in (0,2)$. Is there an $s \in (0,1)$ such that $\forall r \le r_{o}$, $Perm(A)$ can be computed in $O(2^{n^{s}})$ time? If so, is there a formula for $s$ in terms of $n$ and $r_{o}$?

  • 6
    $\begingroup$ I guess you are referring to arxiv.org/abs/1206.1775 which shows there are no such algorithms for matrices with a linear in $n$ number of ones unless rETH is false? $\endgroup$ – Andreas Björklund Jul 9 '12 at 9:41

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.