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.
The work of Vladimir Kolmogorov’s group can be divided into three topics. The first is the development of efficient algorithms for inference in graphical models and combinatorial optimization problems. Some of their techniques are widely used in computer vision and other areas, for example the “Boykov-Kolmogorov” maximum flow algorithm and the “TRW-S” algorithm for MAP inference in pairwise graphical models. Kolmogorov‘s “Blossom V” algorithm is currently the fastest technique in practice for computing a minimum cost perfect matching in a graph. Their second focus is theoretical investigations of the complexity of discrete optimization, in particular using the framework of valued constraint satisfaction problems and their variants. Finally, the Kolmogorov group has worked on applications of discrete optimization in computer vision, such as image segmentation and stereo reconstruction.
Group Leader
Administrative Support
Team
Current Projects
Inference in graphical models | Combinatorial optimization problems | Theory of discrete optimization
Publications
Kolmogorov V. 2024. A simpler and parallelizable O(√log n)-approximation algorithm for sparsest cut. Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 403–414. View
Dvorak M, Kolmogorov V. 2024. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. View
Kolmogorov V. 2023. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2023, 11980–11989. View
Dvorak M, Blanchette J. 2023. Closure properties of general grammars – formally verified. 14th International Conference on Interactive Theorem Proving. ITP: International Conference on Interactive Theorem Proving, LIPIcs, vol. 268, 15. View
Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72. 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
