Vladimir Kolmogorov

Timeline

1. 2002

   Best papers on graph cuts

   In May 2002 he and Ramin Zabih receive a best paper award at the European Conference on Computer Vision for What Energy Functions can be Minimized via Graph Cuts? and for Multi-camera Scene Reconstruction via Graph Cuts.

2. 2003

   A doctorate at Cornell

   He receives an M.S. in applied mathematics and physics from the Moscow Institute of Physics and Technology and a Ph.D. in computer science from Cornell University. In September 2003 the Cornell thesis is Graph Based Algorithms for Scene Reconstruction from Two or More Views, advised by Ramin Zabih.

3. 2003–2005

   Microsoft Research in Cambridge

   From October 2003 to October 2005 he is an associate researcher at Microsoft Research in Cambridge. In August 2004 he publishes GrabCut with Carsten Rother and Andrew Blake in ACM Transactions on Graphics. In September 2004 he and Yuri Boykov publish an experimental comparison of min-cut/max-flow algorithms for energy minimization in vision.

4. 2005–2011

   Lecturer at UCL

   From 2005 to 2011 he is a lecturer at University College London. From 2006 to 2011 he holds a Royal Academy of Engineering/EPSRC Research Fellowship. In 2006 he publishes the TRW-S algorithm for inference in graphical models, and in 2009 he publishes Blossom V for minimum-cost perfect matching.

5. 2011–2014

   Assistant professor at ISTA

   In September 2011 he moves to the Institute of Science and Technology Austria. He is an assistant professor there from 2011 to 2014.

6. 2012

   A Koenderink Prize

   In October 2012 he receives the Koenderink Prize at the European Conference on Computer Vision in Florence for What Energy Functions can be Minimized via Graph Cuts?, written with Ramin Zabih at Cornell University in 2002.

7. Since 2014

   Professor and VCSP complexity

   Since 2014 he is a professor at the Institute of Science and Technology Austria. In 2017 he, Andrei Krokhin, and Michal Rolínek publish The Complexity of General-Valued CSPs in SIAM Journal on Computing. The paper gives a complete complexity classification of general valued constraint satisfaction problems.

8. 2025–2026

   Sparsest cut and forests

   In 2025 he publishes a simpler parallelizable approximation algorithm for Sparsest Cut in ACM Transactions on Algorithms. In January 2026 he and Pavel Arkhipov publish faster algorithms for packing forests in graphs at the ACM-SIAM Symposium on Discrete Algorithms. He is a professor at the Institute of Science and Technology Austria, and discrete optimization is his main research area.