7 papers
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…
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…
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,…
Matroid Base Packings: Improved Dynamic Matroid Density and Combinatorics of Tree Packings
Pavel Arkhipov, Vladimir Kolmogorov
Greedy minimum-weight spanning tree packings are an important tool in graph connectivity algorithms. We study the corresponding process of greedy base packing in matroids, followin…
Faster algorithms for packing forests in graphs and related problems
Pavel Arkhipov, Vladimir Kolmogorov
We consider several problems related to packing forests in graphs. The first one is to find edge-disjoint forests in a directed graph of maximal size such that the indegree…
Bounded indegree -forests problem and a faster algorithm for directed graph augmentation
Pavel Arkhipov, Vladimir Kolmogorov
We consider two problems for a directed graph , which we show to be closely related. The first one is to find edge-disjoint forests in of maximal size such that the inde…
Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results
Pavel Arkhipov
This paper focuses on Majority Dynamics in sparse graphs, in particular, as a tool to study internal cuts. It is known that, in Majority Dynamics on a finite graph, each vertex eve…