Email Gateway (Mar 25 2024 at 15:42): Email Gateway (Mar 25 2024 at 15:42):From: Dmitriy Traytel <traytel@di.ku.dk>
Dear all,
You will love this entry iff<https://xkcd.com/1033/> you love probabilities and logic:
Approximate Model Counting
by Yong Kiam Tan and Jiong Yang
Approximate model counting is the task of approximating the number of solutions to an input formula. This entry formalizes ApproxMC, an algorithm due to Chakraborty et al. with a probably approximately correct (PAC) guarantee, i.e., ApproxMC returns a multiplicative (1+ε)-factor approximation of the model count with probability at least 1-δ, where ε > 0 and 0 < δ ≤ 1. The algorithmic specification is further refined to a verified certificate checker that can be used to validate the results of untrusted ApproxMC implementations (assuming access to trusted randomness).
https://www.isa-afp.org/entries/Approximate_Model_Counting.html
Enjoy!
Last updated: Jan 04 2025 at 20:18 UTC