About me:

I received the M.S. degree in Applied Mathematics and Physics from the Moscow Institute of Physics and Technology, and the Ph.D. degree in Computer Science from Cornell University. After spending two years as an Associate Researcher at Microsoft Research in Cambridge, England, I joined University College London as a Lecturer. In 2006-2011 I held the Royal Academy of Engineering/EPSRC Research Fellowship. In September 2011 I moved to IST Austria.

My main research area is discrete optimization. Specific topics include the following:

• Complexity classifications, in particular in the framework of Valued Constraint Satisfaction Problems.
• Designing algorithms for combinatorial optimization problems (maximum flow, minimum cost perfect matching, etc).
• Designing algorithms for MAP inference in Markov Random Fields.
• Previously, I was also working on applications of discrete optimization algorithms (such as "graph cuts") in computer vision.

Links:

• Curriculum Vitae
  
• Software that I wrote
  
• Workshop on Optimization in Machine Learning, May 2020, IST Austria (cancelled due to coronavirus)
• ERC Consolidator grant (2014-2020).
• European Laboratory for Learning and Intelligent Systems (ELLIS)
• Personal
  

Current team members:

• Ivan Sergeev (postdoc)
• Martin Dvořák (PhD student)
• Jeferson Zapata (PhD student)
• Pavel Arkhipov (PhD student)

Former team members:

• Rustem Takhanov (postdoc)
• Alexandr Kazda (postdoc)
• K S Sesh Kumar (postdoc)
• Paul Swoboda (postdoc)
• Sharareh Alipour (postdoc)
• Yekini Shehu (postdoc)
• Nasim Samei (postdoc)
• Michal Rolínek (PhD student)

Publications:

• A faster algorithm for the k-forest problem: breaking the O_k(n^3/2) complexity barrier
  Pavel Arkhipov, Vladimir Kolmogorov.
  arXiv technical report, September 2024.
• Bounded indegree k-forests problem and a faster algorithm for directed graph augmentation
  Pavel Arkhipov, Vladimir Kolmogorov.
  arXiv technical report, September 2024.
• Duality theory in linear optimization and its extensions -- formally verified
  Martin Dvorak, Vladimir Kolmogorov.
  arXiv technical report, September 2024.
• Parameter estimation for Gibbs distributions
  David G. Harris and Vladimir Kolmogorov.
  Accepted to Transactions on Algorithms (TALG), 2024. Preliminary versions appeared in COLT 2018 (V. Kolmogorov, "A Faster Approximation Algorithm for the Gibbs Partition Function") and ICALP 2023 (D. Harris, V. Kolmogorov, "Parameter estimation for Gibbs distributions").
• Verifying feasibility of degenerate semidefinite programs
  Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata.
  arXiv technical report, May 2024.
• A simpler and parallelizable O( √ log n)-approximation algorithm for Sparsest Cut
  Vladimir Kolmogorov.
  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2024.
• Generalized minimum 0-extension problem and discrete convexity
  Martin Dvorak and Vladimir Kolmogorov.
  In Mathematical Programming (MP), March 2024.
• Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions
  Vladimir Kolmogorov.
  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2023.
• OrderedCuts: A new approach for computing Gomory-Hu tree
  Vladimir Kolmogorov.
  arXiv technical report, August 2022.
• A computational study of Gomory-Hu construction tree algorithms
  Vladimir Kolmogorov.
  arXiv technical report, August 2022.
• One-sided Frank-Wolfe algorithms for saddle problems
  Vladimir Kolmogorov and Thomas Pock.
  In International Conference on Machine Learning (ICML), July 2021.
• A new notion of commutativity for the algorithmic Lovasz Local Lemma
  David G. Harris, Fotis Iliopoulos and Vladimir Kolmogorov.
  In Approximation, Randomization, and Combinatorial Optimization (RANDOM), August 2021.
• A Local Lemma for Focused Stochastic Algorithms
  Dimitris Achlioptas, Fotis Iliopoulos and Vladimir Kolmogorov.
  In SIAM Journal on Computing (SICOMP), 48(5), 1583-1602, 2019.
• Function Norms for Neural Networks
  Amal Rannen-Triki, Maxim Berman, Vladimir Kolmogorov and Matthew B. Blaschko.
  In ICCV workshop: Statistical Deep Learning for Computer Vision, October 2019.
• Testing the complexity of a valued CSP language
  Vladimir Kolmogorov.
  In 46th International Colloquium on Automata, Languages and Programming (ICALP), July 2019.
• MAP inference via Block-Coordinate Frank-Wolfe Algorithm
  Paul Swoboda and Vladimir Kolmogorov.
  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
• Efficient Optimization for Rank-based Loss Functions
  Pritish Mohapatra, Michal Rolínek, C.V. Jawahar, Vladimir Kolmogorov and M. Pawan Kumar.
  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2018 (best paper honorable mention award).
• Even Delta-Matroids and the Complexity of Planar Boolean CSPs
  Alexandr Kazda, Vladimir Kolmogorov and Michal Rolínek.
  In Transactions on Algorithms (TALG), 15(2), December 2018. Preliminary version appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2017.
• Commutativity in the Algorithmic Lovasz Local Lemma
  Vladimir Kolmogorov.
  In SIAM Journal on Computing (SICOMP), 47(6):2029-2056, 2018. Preliminary version appeared in IEEE Symposium on Foundations of Computer Science (FOCS), October 2016.
• On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model
  Joël Alwen, Binyi Chen, Chetan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak and Stefano Tessaro.
  In EUROCRYPT, May 2016.
• Total Variation on a Tree
  Vladimir Kolmogorov, Thomas Pock and Michal Rolínek.
  In SIAM Journal on Imaging Sciences (SIIMS), 9(2):605-636, 2016.
• Inference algorithms for pattern-based CRFs on sequence data
  Vladimir Kolmogorov and Rustem Takhanov.
  In Algorithmica, September 2016, 76(1):17-46. Preliminary version (R. Takhanov, V. Kolmogorov "Inference algorithms for pattern-based CRFs on sequence data") appeared in International Conference on Machine Learning (ICML), June 2013.
• Effectiveness of Structural Restrictions for Hybrid CSPs
  Vladimir Kolmogorov, Michal Rolínek and Rustem Takhanov.
  In 26th International Symposium on Algorithms and Computation (ISAAC), December 2015.
• The Complexity of General-Valued CSPs
  Vladimir Kolmogorov, Andrei Krokhin and Michal Rolínek.
  In SIAM Journal on Computing (SICOMP), 46(3), 1087-1110, 2017. Preliminary version appeared in IEEE Symposium on Foundations of Computer Science (FOCS), October 2015.
• Proofs of Space
  Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov and Krzysztof Pietrzak.
  In Advances in Cryptology (CRYPTO), August 2015.
• A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle
  Neel Shah, Vladimir Kolmogorov and Christoph H. Lampert.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
• The power of linear programming for general-valued CSPs
  Vladimir Kolmogorov, Johan Thapper and Stanislav Zivny.
  In SIAM Journal on Computing (SICOMP), 44(1):1-36, 2015.
• A new look at reweighted message passing
  Vladimir Kolmogorov.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), May 2015, 37(5):919-930.
• Superconcentrators of Density 25.3
  Vladimir Kolmogorov and Michal Rolínek.
  arXiv technical report, May 2014. Accepted to Ars Combinatoria.
• Potts model, parametric maxflow and k-submodular functions
  Igor Gridchyn and Vladimir Kolmogorov.
  In International Conference on Computer Vision (ICCV), December 2013.
• Partial Enumeration and Curvature Regularization
  Carl Olsson, Johannes Ulen, Yuri Boykov and Vladimir Kolmogorov.
  In International Conference on Computer Vision (ICCV), December 2013.
• The power of linear programming for finite-valued CSPs: a constructive characterization
  Vladimir Kolmogorov.
  In International Colloquium on Automata, Languages and Programming (ICALP), July 2013.
• Optimal Coalition Structures in Cooperative Graph Games
  Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov and Morteza Zadimoghaddam.
  In AAAI Conference on Artificial Intelligence (AAAI), July 2013.
• Computing the M most probable modes of a graphical model
  Chao Chen, Vladimir Kolmogorov, Yan Zhu, Dimitris Metaxas and Christoph H. Lampert.
  In International Conference on Artificial Intelligence and Statistics (AISTATS), April-May 2013.
• A Dual Decomposition Approach to Feature Correspondence
  Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), February 2013, 35(2):259-271.
  Preliminary version ("Feature Correspondence via Graph Matching: Models and Global Optimization") appeared in European Conference on Computer Vision (ECCV), October 2008.
• Generalized sequential tree-reweighted message passing
  Thomas Schoenemann and Vladimir Kolmogorov.
  To appear in Advanced Structured Prediction, eds. Sebastian Nowozin, Peter V. Gehler, Jeremy Jancsary and Christoph Lampert, MIT Press.
• Approximating Marginals Using Discrete Energy Minimization
  Filip Korč, Vladimir Kolmogorov and Christoph Lampert.
  In ICML 2012 Workshop on Inferning: Interactions between Inference and Learning, June 2012.
• Towards Minimizing k-Submodular Functions
  Anna Huber and Vladimir Kolmogorov.
  In International Symposium on Combinatorial Optimization (ISCO), April 2012.
• Minimizing a sum of submodular functions
  Vladimir Kolmogorov.
  In Discrete Applied Mathematics, October 2012, 160(15):2246-2258.
• The complexity of conservative valued CSPs
  Vladimir Kolmogorov and Stanislav Zivny.
  In Journal of the ACM (JACM), April 2013, 60(2).
  Preliminary version appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2012.
• Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions
  Vladimir Kolmogorov.
  In 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 2011.
• Object cosegmentation
  Sara Vicente, Carsten Rother and Vladimir Kolmogorov.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2011.
• Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints
  Anton Osokin, Dmitry Vetrov and Vladimir Kolmogorov.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2011.
• Generalized roof duality and bisubmodular functions
  Vladimir Kolmogorov.
  In Discrete Applied Mathematics, March 2012, 160(4-5):416-426.
  Preliminary version appeared in Neural Information Processing Systems Conference (NIPS), December 2010.
• Cosegmentation revisited: Models and optimization
  Sara Vicente, Vladimir Kolmogorov and Carsten Rother.
  In European Conference on Computer Vision (ECCV), September 2010.
• A Global Perspective on MAP Inference for Low-Level Vision
  Oliver J. Woodford, Carsten Rother and Vladimir Kolmogorov.
  In IEEE International Conference on Computer Vision (ICCV), October 2009.
• Joint optimization of segmentation and appearance models
  Sara Vicente, Vladimir Kolmogorov and Carsten Rother.
  In IEEE International Conference on Computer Vision (ICCV), October 2009.
• New Algorithms for Convex Cost Tension Problem with Application to Computer Vision
  Vladimir Kolmogorov and Akiyoshi Shioura.
  In Discrete Optimization, November 2009, 6(4):378-393.
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
  Vladimir Kolmogorov.
  In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
• On Partial Optimality in Multi-label MRFs
  Pushmeet Kohli, Alexander Shekhovtsov, Carsten Rother, Vladimir Kolmogorov and Phil Torr.
  In International Conference on Machine Learning (ICML), July 2008.
• Graph cut based image segmentation with connectivity priors
  Sara Vicente, Vladimir Kolmogorov and Carsten Rother.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2008.
• A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors
  Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veskler, Vladimir Kolmogorov, Aseem Agarwala, Marshall Tappen and Carsten Rother.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 30(6):1068-1080, June 2008.
  Earlier version ``Comparative Study of Energy Minimization Methods for Markov Random Fields'' appeared in European Conference on Computer Vision (ECCV), May 2006.
• A faster algorithm for computing the principal sequence of partitions of a graph
  Vladimir Kolmogorov.
  In Algorithmica, April 2010, 56(4):394-412.
• An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs
  M. Pawan Kumar, Vladimir Kolmogorov and Philip H. S. Torr.
  In Journal of Machine Learning Research (JMLR), 10:71-106, January 2009.
  Preliminary version ("An Analysis of Convex Relaxations for MAP Estimation") appeared in Neural Information Processing Systems Conference (NIPS), December 2007 (honorable mention, outstanding student paper award).
• Applications of parametric maxflow in computer vision
  Vladimir Kolmogorov, Yuri Boykov and Carsten Rother.
  In IEEE International Conference on Computer Vision (ICCV), October 2007.
• A note on the primal-dual method for the semi-metric labeling problem
  Vladimir Kolmogorov.
  Technical report, June 2007.
• Optimizing binary MRFs via extended roof duality
  Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky and Martin Szummer.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2007.
• Minimizing non-submodular functions with graph cuts - a review
  Vladimir Kolmogorov and Cartsen Rother.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29(7):1274-1279, July 2007.
  
• Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs
  Carsten Rother, Vladimir Kolmogorov, Tom Minka and Andrew Blake.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2006.
• Bilayer Segmentation of Live Video
  Antonio Criminisi, Geoffrey Cross, Andrew Blake and Vladimir Kolmogorov.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2006.
• An integral solution to surface evolution PDEs via Geo-Cuts
  Yuri Boykov, Vladimir Kolmogorov, Daniel Cremers and Andrew Delong.
  In European Conference on Computer Vision (ECCV), May 2006.
• Comparison of energy minimization algorithms for highly connected graphs
  Vladimir Kolmogorov and Carsten Rother.
  In European Conference on Computer Vision (ECCV), May 2006.
• Convergent Tree-reweighted Message Passing for Energy Minimization
  Vladimir Kolmogorov.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 28(10):1568-1583, October 2006.
  Preliminary version appeared in Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS), January 2005.
• Probabilistic fusion of stereo with color and contrast for bi-layer segmentation
  Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross and Carsten Rother.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 28(9):1480-1492, September 2006.
  Preliminary version ("Bi-layer Segmentation of Binocular Stereo Video") appeared in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2005 (best paper honorable mention award).
• Digital Tapestry
  Carsten Rother, Sanjiv Kumar, Vladimir Kolmogorov and Andrew Blake.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2005.
• What Metrics Can Be Approximated by Geo-Cuts, or Global Optimization of Length/Area and Flux
  Vladimir Kolmogorov and Yuri Boykov.
  In IEEE International Conference on Computer Vision (ICCV), October 2005.
• On the Optimality of Tree-reweighted Max-product Message Passing
  Vladimir Kolmogorov and Martin Wainwright.
  In 21st Conference on Uncertainty in Artificial Intelligence (UAI), July 2005.
• Digital Tapestry
  Carsten Rother, Sanjiv Kumar, Vladimir Kolmogorov and Andrew Blake.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2005.
• Graph Cut Algorithms for Binocular Stereo with Occlusions
  Vladimir Kolmogorov and Ramin Zabih.
  In Mathematical Models in Computer Vision: The Handbook, Springer-Verlag, 2005.
• GrabCut - Interactive Foreground Extraction using Iterated Graph Cuts
  Carsten Rother, Vladimir Kolmogorov and Andrew Blake.
  In ACM Transactions on Graphics (SIGGRAPH), August 2004.
• An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision
  Yuri Boykov and Vladimir Kolmogorov.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 26(9):1124-1137, September 2004.
• What Energy Functions can be Minimized via Graph Cuts?
  Vladimir Kolmogorov and Ramin Zabih.
  In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 26(2):147-159, February 2004.
  Earlier version appeared in European Conference on Computer Vision (ECCV), May 2002 (best paper award).
• Spatially Coherent Clustering with Graph Cuts
  Ramin Zabih and Vladimir Kolmogorov.
  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2004.
• Computing Geodesics and Minimal Surfaces via Graph Cuts
  Yuri Boykov and Vladimir Kolmogorov.
  In IEEE International Conference on Computer Vision (ICCV), October 2003.
• Visual Correspondence Using Energy Minimization and Mutual Information
  Junhwan Kim, Vladimir Kolmogorov and Ramin Zabih.
  In IEEE International Conference on Computer Vision (ICCV), October 2003.
• Generalized Multi-camera Scene Reconstruction Using Graph Cuts
  Vladimir Kolmogorov, Ramin Zabih and Steven Gortler.
  In Fourth International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), July 2003.
• Multi-camera Scene Reconstruction via Graph Cuts
  Vladimir Kolmogorov and Ramin Zabih.
  In European Conference on Computer Vision (ECCV), May 2002 (best paper award).
• Computing Visual Correspondence with Occlusions using Graph Cuts
  Vladimir Kolmogorov and Ramin Zabih.
  In IEEE International Conference on Computer Vision (ICCV), July 2001.

PhD Thesis:

• Graph Based Algorithms for Scene Reconstruction from Two or More Views
  Vladimir Kolmogorov.
  PhD thesis, Cornell University, September 2003.

Contact information:

E-mail: 'vnk' followed by '@' and the IST domain name
Phone: +43 (0)2243 9000 4801
Fax: +43 (0)2243 9000 2000
Address:

Am Campus 1, IST Austria
3400 Klosterneuburg
Austria