approximate-counting

Model Counting Competition Submission of Ganak + Approxmc 2025

Code for my B.Sc. thesis at RWTH Aachen: implementation and benchmarking of two FPRAS algorithms (Arenas et al., Meel et al.) that approximately count the words of length n accepted by an NFA, compared against exact baselines. Python, NumPy/SciPy, SQLite.

A Python implementation and statistical analysis of the Morris Counter, a probabilistic data structure for approximate counting. Includes multi-counter and generalized base variants.

Critical review of approximate counting and uniform sampling, with manuscript, citation evidence, worked reductions and reproducible data.

A small, dependency-free [Count-Min Sketch](https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch) in Rust —

N queens counting as a rare event and a quantile integral, turned into a Monte Carlo program for P versus NP: NP = RP is shown equivalent to sampling queens completions, promise RP = promise P, which implies P = RP, is restated as a hitting set problem, with exact computations on the queens.