When does approximate counting have the same running time as decision?

It is obvious that if one can approximately count size-k independent sets (for example) up to multiplicative error, then one can decide whether any size-k independent set exists. In many settings, there are foundational results saying that the opposite is true, and that efficient decision algorithms for hard complexity classes would imply efficient approximate counting algorithms for those same classes; for example, a polynomial-time decision algorithm for SAT would imply an FPRAS for #SAT, and a sub-exponential time algorithm for 3-SAT would imply a sub-exponential time approximation algorithm for #3-SAT.

In fine-grained complexity, where we care about not broad categories like “polynomial” or “sub-exponential” but exact running times, the picture is more complicated. A wide class of problems in the area can be viewed as counting edges of a k-uniform hypergraph which is a “natural” function of the instance, using an existing decision algorithm to detect these edges – for example, this is true for counting size-k independent sets, weight-k solutions to CSPs, k-SUM and k-OV. For all problems in this class, it is known that any algorithm for a “colourful” version of the decision problem can be bootstrapped into an approximate counting algorithm with the same running time up to a factor of log^{O(k)}(n). In this talk, we will address two further questions. First: the dependence on k in log^{O(k)}(n) is potentially quite severe – can it be mitigated? And second: does the same result hold for algorithms for the usual version of the decision problem, without the need for a “colourful” version? We will answer both questions with “it depends”, presenting algorithms when the answer is “yes” and oracle lower bounds when the answer is “no”.