89 citations · 98 across the 2 of their papers we have counts for
2 papers
cs.CC2012★ 89 cited
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Holger Dell, Thore Husfeldt, Dániel Marx +2
We show conditional lower bounds for well-studied #P-hard problems: (a) The number of satisfying assignments of a 2-CNF formula with n variables cannot be counted in time exp(o(n))…
cs.CC2010★ 9 cited
The Exponential Time Complexity of Computing the Probability That a Graph is Connected
Thore Husfeldt, Nina Taslaman
We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in Omega(m/ log^2 m) fo…