Four works on fine-grained reductions of approximate counting and uniform generation to decision

by Anup Bhattacharya, Arijit Bishnu, Holger Dell, Arijit Ghosh, John Lapinskas, Kitty Meeks, and Gopinath Mishra.

Oded's comments

I missed these works when they were published and am lumping them together now in order to make up for that. The issue at hand is fine-grained reductions from approximate counting (of solutions) problems to the corresponding decision problems and the relation of approximate counting to uniform generation of solutions. This is indeed the fine-grained analogous of the celebrated results (from the 1980s) that refer to NP-search problems, and the focus in the current works is on reductions that make a polylogaithmic number of queries.

I started thinking about these problems (in the context of $t$-cliques) a few days ago, not realizing that much work has been done about it already. In particular, the sequence of works listed below contains all the ideas that I came-up with. Nevertheless, since I drafted a memo while thinking about these problems and since my perspectives are somewhat different, I am posting it HERE.

What is described in my (5-page) memo is a crude approximation for the number of $t$-cliques in an $n$-vertex graph. This (almost linear-time randomized) approximation algorithm uses $O(\log n)^t$ calls to a decision procedure (for the existence of $t$-cliques in graphs), and yields an approximation up to a factor of $O(\log n)^t$. In addition, the memo contains a sketch of the fine-grained equivalence between approximate counting and uniform generation of $t$-cliques in graphs.

The four works

The results in the works listed below are better than those described in my memo. In particular, they obtain a fine approximation (actually, a FPTAS) rather than a crude one. Furthermore, these works go beyond $t$-cliques, which is (or may be) viewed as a special case.

Back to list of Oded's choices.