# An ETH-hardness sparsity transition for the permanent

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

• 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? – Andreas Björklund Jul 9 '12 at 9:41