The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting setting, which makes #ETH robust.

Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an $n\times n$ matrix with $m$ nonzero entries requires time $\exp(\Omega(m))$. Restricted to 01-matrices, the bound is $\exp(\Omega(m/\log m))$. Computing the Tutte polynomial of a multigraph with $n$ vertices and $m$ edges requires time $\exp(\Omega(n))$ at points $(x,y)$ with $(x-1)(y-1)\neq 1$ and $y\notin\{0,\pm 1\}$. At points $(x,0)$ with $x \not \in \{0,\pm 1\}$ it requires time $\exp(\Omega(n))$, and if $x=-2,-3,\ldots$, it requires time $\exp(\Omega(m))$. For simple graphs, the bound is $\exp(\Omega(m/\log^3 m))$.