Institute of Science and Technology (IST), Austria
For Postdocs:
I have postdoc openings in the area of discrete optimization.
You can also check the ISTfellow program.
For prospective PhD students:
Please visit the IST Austria Graduate School page for details on our graduate program.
For Interns:
I am not accepting intern applications at the moment.
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.
I work in the areas of combinatorial optimization and computer vision. My current research topics include the theory of Valued Constraint Satisfaction Problem, graphical models, and optimization algorithms for Markov Random Fields.
Parameter estimation for Gibbs distributions
David G. Harris and Vladimir Kolmogorov.
In 50th International Colloquium on Automata, Languages and Programming (ICALP), July 2023.
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.
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.
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 new look at reweighted message passing
Vladimir Kolmogorov.
In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), May 2015, 37(5):919-930.
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.
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.
Object cosegmentation
Sara Vicente, Carsten Rother 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.
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.
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).
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.
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.
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.