Professor Vladimir Kolmogorov

Professor, Group Leader of Kolmogorov Group

Research areas in the program

• Combinatorial Optimization
• Global Optimization

Keywords

• combinatorial optimization
• complexity classifications
• linear programming relaxations
• valued constraint satisfaction problems

Research Interests

The PI works on several aspects of discrete optimization problems, such as development of efficient optimization algorithms, understanding complexity of different classes of problems, and applications in computer vision.

Know-how and infrastructure of the research group

The PI’s research focuses on discrete optimization. Some of the main achievements are listed below.

Efficient optimization algorithms, with practical implementations
The “Boykov-Kolmogorov” maxflow algorithm has been a standard method in computer vision for many years. The ”QPBO” software developed by the PI (and based on maxflow) is another standard library; in particular, the implementation of the PROBE technique is faster than the previous one by more than 2 orders of magnitude (on random 2D grids). The “TRW-S” algorithm [Kolmogorov PAMI’06] is still among state-of-the-art techniques for inference in graphical models with unary and pairwise terms. The “Blossom V” method [Kolmogorov MPC’09] is currently the fastest available algorithm in practice for solving the min cost perfect matching problem; it significantly outperforms previous techniques. These libraries are widely used in computer vision and beyond (e.g. “Blossom V” is used in physics). More recent examples of efficient algorithms are [Gridchyn,Kolmogorov ICCV’13] and [Kolmogorov,Takhanov Algorithmica’16].

Theoretical work
The PI has obtained important results for “Valued Constraint Satisfaction Problems” (VCSPs): a dichotomy result for conservative VCSPs [Kolmogorov,Zivny ACM’13]; a characterization of the power of Linear Programming for VCSPs [Kolmogorov,Thapper,Zivny SICOMP’15]; the work [Kolmogorov,Krokhin,Rolinek SICOMP’17] has led to a complete complexity classification of general VCSPs. In addition, the work [Kazda,Kolmogorov,Rolinek TALG’18] gave the largest known tractable subclass of “Delta-matroids”, and has settled a complexity classification for Planar Boolean CSPs.

Computer vision
The PI has also developed several optimization algorithms for computer vision problems such as stereo matching and image segmentation.

Collaborations within the VGSCO

With Monika Henzinger, Nysret Musliu and Günther Raidl on Combinatorial Optimization and with Immanuel Bomze and Arnold Neumaier on Global Optimization.

Scientific CV

Positions

Microsoft Research, Cambridge, UK: Associat e Researcher (Oct 2003-Oct 2005); Visiting Researcher (Feb-Dec 2006, Jul 2007-Jun 2008, Dec 2008-Jun 2009); Consultant (Dec 2009-Jun 2010)

University College London, UK:  Lecturer  (Oct 2005 - Aug 2011) 

Institute of Science and Technology (IST), Austria: Assistant Professor (Sep 2011-Sep 2014); Professor (Oct 2014-current)

Selected awards

Best paper honorable mention award at CVPR’18.

ERC Consolidator Grant, 2014-2019.

Koenderink Prize for fundamental contributions to computer vision ECCV’12.

Honorable mention, outstanding student paper award (to M. Pawan Kumar) at NIPS’07.

The Royal Academy of Engineering/EPSRC Research Fellowship, 2006-2011.

Best paper honorable mention award at CVPR’05.

Best paper award at the ECCV’02.

Publications

click here for list of publications