Skip to main content

Discrete Optimization

Computer Science

Image of Vladimir Kolmogorov

Vladimir Kolmogorov

Professor


1 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
  • 2009 – 2010 Consultant, Microsoft Research, Cambridge, UK
  • 2006 – 2009 Visiting Researcher, Microsoft Research, Cambridge, UK
  • 2003 – 2005 Associate Researcher, Microsoft Research, Cambridge, UK
  • Summer 2000, Summer 2001 Intern, Siemens Corporate Research, Imaging Department, Princeton, NJ, USA
  • Spring 2001 Visiting Research Assistant, Weill Medical College, Department of Radiology, New York, NY, USA

1.1 Selected Distinctions

  • 2018 Best paper honorable mention award at IEEE/CVF Conference on Computer Vision and Pattern Recognition.
  • 2012 Koenderink Prize for fundamental contributions to computer vision at the European Conference on Computer Vision.
  • 2007 Honorable mention, outstanding student paper award (to M. Pawan Kumar) at Neural Information Processing Systems Conference.
  • 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.

1.2 Selected Grants

  • 2014 – 2020 ERC Consolidator Grant. Title: “Discrete Optimization in Computer Vision: Theory and Practice” (DOiCV). Amount: € 1,641,585.
  • 2020 – 2025 FWF DK Grant, “Vienna Graduate School on Computational Optimization”. Amount: € 152,000.

1.3 Tech Transfer (Patents, Spin-Offs)

N/A


1.4 Selected Publications

  1. P. Arkhipov and V. Kolmogorov, “Faster algorithms for packing forests in graphs and related problems,” in ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan. 2026.
  2. V. Kolmogorov, S. Naldi, and J. Zapata, “Certifying solutions of degenerate semidefinite programs,” SIAM Journal on Optimization (SIOPT), vol. 235(3), pp. 1630–1654, 2025.
  3. D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity for the algorithmic Lovasz local lemma,” Theory of Computing (ToC), vol. 21, pp. 1–34, 2025.
  4. V. Kolmogorov, “A simpler and parallelizable O(log⁡n)O\!\left(\sqrt{\log n}\right)-approximation algorithm for sparsest cut,” ACM Transactions on Algorithms (TALG), vol. 21(4), pp. 1–22, 2025.
  5. D. G. Harris and V. Kolmogorov, “Parameter estimation for gibbs distributions,” ACM Transactions on Algorithms (TALG), vol. 21(1), pp. 1–39, 2024.
  6. M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” Mathematical Programming (MP), vol. 209, pp. 279–322, Mar. 2024.
  7. V. Kolmogorov, “Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions,” in IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2023.
  8. V. Kolmogorov and T. Pock, “One-sided Frank-Wolfe algorithms for saddle problems,” in International Conference on Machine Learning (ICML), Jul. 2021.
  9. D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastic algorithms,” SIAM Journal on Computing (SICOMP), vol. 48(5), pp. 1583–1602, 2019.
  10. P. Swoboda and V. Kolmogorov, “MAP inference via block-coordinate Frank-Wolfe algorithm,” in IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2019.

2 Group Members

  • Pavel Arkrhipov, PhD Student since 2024
  • Asaf Lef-Ran, PhD Student since 2025
  • Jefferson Zapata, PhD Student since 2020
  • Mikhail Karapetyants, Postdoc since 2025

3 Research

My group works primarily on discrete and combinatorial optimization. It 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, namely the dichotomy conjecture (now theorem) for VCSPs. 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 such as Lovász Local Lemma, estimating parameters of Gibbs distributions, and certifying solutions of SDPs. In the past I worked on applications of discrete optimization in computer vision, such as stereo reconstruction and image segmentation.


3.1 Current Scientific Projects/Directions

  • Numerical algorithms for solving systems of polynomial equations. More specifically, we are investigating new “endgames” for tracking paths that converge to isolated singular solutions.
  • Exploring tighter relaxations for solving MAP-MRF problems.
  • Practical implementations of combinatorial optimization algorithms

3.2 Research in Focus

In [1] we proposed new algorithms for several problems related to tree packings in graphs. One of them is the well-studied “kk-forest problem”: find kk edge-disjoint forests of maximum cardinality in a given undirected graph. Previous approaches were specialized implementations of the matroid union algorithm; their complexity included a factor of Ok(n3/2+m)O_k\!\left(n^{3/2} + m\right) (for fixed kk) which seemed to be a barrier for this class of algorithms. We improved this to Ok(m1+o(1))O_k\!\left(m^{1+o(1)}\right) using a very different approach.

Another highlight is a new practical algorithm for the minimum-weight perfect matching problem. The previous state-of-the-art was my “Blossom V” algorithm, which has been uncontested since 2009. Our new “Blossom VI” implementation [P. Arkhipov, V. Kolmogorov, April 2026, arXiv] outperforms Blossom V by orders of magnitude on those families of problems for which Blossom V takes superlinear time.



theme sidebar-arrow-up
Back to Top