Showing 2026Show all
2 papers · 1 filter
cs.DS2026
A Counting and Sampling Lovász Local Lemma
Hongyang Liu, Chunyang Wang, Yitong Yin +2
We establish counting and sampling analogues of the Lovász Local Lemma: we give efficient algorithms for approximately counting and exactly sampling satisfying assignments of gener…
cs.DS2026
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…