Kolmogorov Group
Discrete Optimization
When we step out into the street, we automatically judge the distance and speed of cars. For computers, estimating the depth of objects in an image requires complex computations. A popular approach for tackling this problem is to use discrete optimization algorithms – the research focus of the Kolmogorov group.
Vladimir Kolmogorov’s group works primarily on discrete and combinatorial optimization. They developed several efficient algorithms well known in the community, such as the “Boykov-Kolmogorov” maximum flow algorithm, the “Blossom V” algorithm for computing a minimum cost perfect matching in a graph, and the “TRW-S” algorithm for MAP-MRF inference in graphical models. The group has investigated complexity classifications of Valued Constraint Satisfaction Problems (VCSPs) and their variants, and contributed to resolving a major open problem in the area. More recent work addressed the Sparsest Cut problem, packing trees in graphs, practical algorithms for computing the Gomory-Hu tree, and some topics outside discrete optimization. These include the Lovász Local Lemma, estimating parameters of Gibbs distributions, and certifying solutions of SDPs. In the past, the Kolmogorov group worked on applications of discrete optimization in computer vision, such as stereo reconstruction and image segmentation.
Group Leader
Administrative Support
Team
Current Projects
Inference in graphical models | Combinatorial optimization problems | Theory of discrete optimization
Publications
Kolmogorov V. 2025. A simpler and parallelizable O(√log n)-approximation algorithm for SPARSEST CUT. ACM Transactions on Algorithms. 21(4), 1–22. View
Harris DG, Iliopoulos F, Kolmogorov V. 2025. A new notion of commutativity for the algorithmic Lovász Local Lemma. Theory of Computing. 21(5), 1–34. View
Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate semidefinite programs. SIAM Journal on Optimization. 35(3), 1630–1654. View
Dvorak M, Kolmogorov V. 2025. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. 209, 279–322. View
Harris DG, Kolmogorov V. 2025. Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. 21(1), 3. View
ReX-Link: Vladimir Kolmogorov
Career
Since 2014 Professor, Institute of Science and Technology Austria (ISTA)
2011 – 2014 Assistant Professor, Institute of Science and Technology Austria (ISTA)
2005 – 2011 Lecturer, University College London, UK
2003 – 2005 Assistant Researcher, Microsoft Research, Cambridge, UK
2003 PhD, Cornell University, Ithaca, USA
Selected Distinctions
2018 Best paper award honorable mention at IEEE/CVF Conference on Computer Vision and Pattern Recognition
2013 ERC Consolidator Grant
2012 Koenderink Prize at the European Conference on Computer Vision for fundamental contributions to computer vision
2007 Honorable mention, outstanding student paper award (to M. Pawan Kumar) at Neural Information Processing Systems Conference
2006 – 2011 Royal Academy of Engineering/EPSRC Research Fellowship
2005 Best paper honorable mention award at IEEE Conference on Computer Vision and Pattern Recognition
2002 Best paper award at the European Conference on Computer Vision
