The Complexity of Approximate Counting (Preliminary Version)

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill +1 more

Heng Guo, Pinyan Lu

In this article we survey recent developments on the complexity of Holant problems. We discuss three different aspects of Holant problems: the decision version, exact counting, and approximate counting.

Eleni Bakali

We consider the class of counting problems,i.e. functions in $\#$P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value of the function $f(x)$ is zero. For example, $\#$independent-sets of all sizes, is such a problem, and one of the hardest of this class, since it is equivalent to $\#$SAT under multiplicative approximation preserving reductions. Using these two powerful properties, self reducibility and easy decision, we prove that all problems/ functions $f$ in this class can be approximated in probabilistic polynomial time within an absolute exponential error $ε\cdot 2^{n'}, \forallε>0$, which for many of those problems (when $n'=n+$constant) implies additive approximation to the fraction $f(x)/2^n$. (Where $n'$ is the amount of non-determinism of some associated NPTM). Moreover we show that for all these problems we can have multiplicative error to the value $f(x)$, of any desired accuracy (i.e. a RAS), in time of order $2^{2n'/3}poly(n)$, which is strictly smaller than exhaustive search. We also show that $f(x)

Philippe Flajolet

Junzhao Yang

For $κ>1$, a directed graph is $κ$-conditioned if it is $κ$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$. We present a deterministic algorithm that approximates the stationary distribution of a $κ$-conditioned graph to inverse polynomial relative error in $O((\log n + \log^2 κ) \log \log n)$ space. In the regime $κ= \exp(Θ(\log^αn))$ for any $α\in (0, 2/3)$, our result improves the best-known $O(\log n \sqrt{\log κ} / \sqrt{\log \log n})$ space bound for approximating $κ$-step random walks in general directed graphs by [Hoza, RANDOM 2021]. We release this preliminary version due to recent rumors of LLM-based progress on related problems and uncertainty about when those results may appear. Further implementation details will be provided in a subsequent version.

Peter Kirschenhofer, Helmut Prodinger

Approximate counting : an alternative approach