101 citations · 355 across the 29 of their papers we have counts for
38 papers
Simple parallel estimation of the partition ratio for Gibbs distributions
David G. Harris, Vladimir Kolmogorov
We consider the problem of estimating the partition function of a Gibbs distribution with the Hamiltonian . As shown in [Ha…
A simpler and parallelizable -approximation algorithm for Sparsest Cut
Vladimir Kolmogorov
Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqr…
OrderedCuts: A new approach for computing Gomory-Hu tree
Vladimir Kolmogorov
The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum - cuts of an undirected weighted graph for all pairs of nodes . We propose a new app…
A computational study of Gomory-Hu construction tree algorithms
Vladimir Kolmogorov
This paper studies algorithms for computing a Gomory-Hu tree, which is a classical data structure that compactly stores all minimum - cuts of an undirected weighted graph. We…
Generalized minimum 0-extension problem and discrete convexity
Martin Dvorak, Vladimir Kolmogorov
Given a fixed finite metric space , the {\em minimum -extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimiz…
One-sided Frank-Wolfe algorithms for saddle problems
Vladimir Kolmogorov, Thomas Pock
We study a class of convex-concave saddle-point problems of the form where is a linear operator, is th…
A new notion of commutativity for the algorithmic Lovász Local Lemma
David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthr…
Parameter estimation for Gibbs distributions
David G. Harris, Vladimir Kolmogorov
We consider Gibbs distributions, which are families of probability distributions over a discrete space with probability mass function of the form f…
Extensions of the Algorithmic Lovasz Local Lemma
Vladimir Kolmogorov
We consider recent formulations of the algorithmic Lovasz Local Lemma by Achlioptas-Iliopoulos-Kolmogorov [2] and by Achlioptas-Iliopoulos-Sinclair [3]. These papers analyze a rand…
Parameter estimation for integer-valued Gibbs distributions
David G. Harris, Vladimir Kolmogorov
A central problem in computational statistics is to convert a procedure for sampling combinatorial from an objects into a procedure for counting those objects, and vice versa. Weco…
A Local Lemma for Focused Stochastic Algorithms
Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov
We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These are algorithms that search a state space by repeatedly selecting some constrai…
MAP inference via Block-Coordinate Frank-Wolfe Algorithm
Paul Swoboda, Vladimir Kolmogorov
We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the ori…
Testing the complexity of a valued CSP language
Vladimir Kolmogorov
A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite se…
A Faster Approximation Algorithm for the Gibbs Partition Function
Vladimir Kolmogorov
We consider the problem of estimating the partition function of a Gibbs distribution with a Hamilton , or more precisely the logarithm of the…
Efficient Optimization for Rank-based Loss Functions
Pritish Mohapatra, Michal Rolinek, C. V. Jawahar +2
The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG).…
Even Delta-Matroids and the Complexity of Planar Boolean CSPs
Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each vari…
Commutativity in the Algorithmic Lovasz Local Lemma
Vladimir Kolmogorov
We consider the recent formulation of the Algorithmic Lovász Local Lemma [10,2,3] for finding objects that avoid `bad features', or `flaws'. It extends the Moser-Tardos resampling…
Effectiveness of Structural Restrictions for Hybrid CSPs
Vladimir Kolmogorov, Michal Rolinek, Rustem Takhanov
Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism…
Total variation on a tree
Vladimir Kolmogorov, Thomas Pock, Michal Rolinek
We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programmin…
The Complexity of General-Valued CSPs
Vladimir Kolmogorov, Andrei Krokhin, Michal Rolinek
An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending o…
A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle
Neel Shah, Vladimir Kolmogorov, Christoph H. Lampert
Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation…
Superconcentrators of Density 25.3
Vladimir Kolmogorov, Michal Rolinek
An -superconcentrator is a directed, acyclic graph with input nodes and output nodes such that every subset of the inputs and every subset of the outputs of same cardina…
Proceedings of The 38th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM), 2014
Vladimir Kolmogorov, Christoph Lampert, Emilie Morvant +1
The 38th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM) will be held at IST Austria, on May 22-23, 2014. The workshop provides a platform for researcher…
Combining pattern-based CRFs and weighted context-free grammars
Rustem Takhanov, Vladimir Kolmogorov
We consider two models for the sequence labeling (tagging) problem. The first one is a {\em Pattern-Based Conditional Random Field }(\PB), in which the energy of a string (chain la…