Approximate Counting in Local Lemma Regimes
December 12, 2025
Gabriel Waite and I have just uploaded to arXiv our paper "Approximate Counting in Local Lemma Regimes". In this paper we establish efficient approximate counting algorithms for several natural problems in local lemma regimes, including the probability of intersection of events and the dimension of intersection of subspaces.
The Lovász local lemma provides a powerful tool for establishing the existence of combinatorial objects. Informally, the lemma states that if a collection of events each occurs with sufficiently small probability and each event depends on only a bounded number of other events, then with positive probability none of the events occur. While efficient constructive algorithms exist for finding such objects, we focus on the problem of approximately counting solutions.
We consider a set of events $\{E_v\}_{v \in V(G)}$ indexed by the vertices of a finite graph $G$. The graph $G$ is called a strong dependency graph of the events if, for every pair of disjoint vertex subsets $S,T \subseteq V(G)$ such that $G[S \cup T]=G[S] \cup G[T]$, the sets of events $\{E_v\}_{v \in S}$ and $\{E_v\}_{v \in T}$ are independent. We are interested in the probability of intersection $\Pr\left[\bigcap_{v \in V(G)}E_v\right]$.
Our main result for the classical setting is as follows.
As a corollary, we obtain an efficient algorithm for approximating the number of satisfying assignments of CNF formulae in local lemma regimes.
For the quantum setting, we establish analogous results for the dimension of intersection of projector kernels. We consider a set of projectors $\{\Pi_v\}_{v \in V(G)}$ on a Hilbert space indexed by the vertices of a finite graph $G$. The graph $G$ is called the strong dependency graph of the projectors if there is an edge between vertices $u$ and $v$ if and only if the supports of the projectors $\Pi_u$ and $\Pi_v$ are not disjoint. We are interested in the dimension of intersection $\dim\left[\bigcap_{v \in V(G)}\ker\Pi_v\right]$.
For commuting projectors, our main result is as follows.
For general projectors, we provide two algorithms. The first is a fully polynomial-time approximation scheme under a global inclusion-exclusion stability condition. The second provides an affine approximation under a spectral gap assumption, avoiding the global stability requirement at the cost of a weaker approximation guarantee.
