Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization
Pavel Arkhipov, Nikita P. Kalinin
Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Nevertheless, an asymptotic gap remains…
cs.DS2026
Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov
We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling thi…
cs.DS2026
Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
Pavel Arkhipov, Vladimir Kolmogorov
Minimum weight perfect matching is a fundamental problem in combinatorial optimization. Since 2009, Blossom V has been the leading practical implementation. We present Blossom VI,…