Vladimir Kolmogorov

According to our database, Vladimir Kolmogorov authored at least 102 papers between 2001 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

A Simpler and Parallelizable \(\boldsymbol{O(\sqrt{\log n})}\)-Approximation Algorithm for Sparsest Cut.

Vladimir Kolmogorov

ACM Trans. Algorithms, October, 2025

Composition Direction of Seymour's Theorem for Regular Matroids - Formally Verified.

Martin Dvorak, Tristan Figueroa-Reid, Rida Hamadani, Byung-Hak Hwang, Evgenia Karunus, Vladimir Kolmogorov, Alexander Meiburg, Alexander Nelson, Peter Nelson, Mark Sandey, Ivan Sergeev

CoRR, September, 2025

Simple parallel estimation of the partition ratio for Gibbs distributions.

David G. Harris, Vladimir Kolmogorov

CoRR, May, 2025

Generalized minimum 0-extension problem and discrete convexity.

Martin Dvorak, Vladimir Kolmogorov

Math. Program., January, 2025

A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.

David G. Harris, Fotios Iliopoulos, Vladimir Kolmogorov

Theory Comput., 2025

Certifying Solutions of Degenerate Semidefinite Programs.

Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata

SIAM J. Optim., 2025

2024

A faster algorithm for the <i>k</i>-forest problem: breaking the O_k(n^3/2) complexity barrier.

Pavel A. Arkhipov, Vladimir Kolmogorov

CoRR, 2024

Duality theory in linear optimization and its extensions - formally verified.

Martin Dvorak, Vladimir Kolmogorov

CoRR, 2024

Verifying feasibility of degenerate semidefinite programs.

Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata

CoRR, 2024

A Simpler and Parallelizable O(√log n)-approximation Algorithm for Sparsest Cut.

Vladimir Kolmogorov

Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

2023

Parameter Estimation for Gibbs Distributions.

David G. Harris, Vladimir Kolmogorov

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions.

Vladimir Kolmogorov

Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023

2022

Combining pattern-based CRFs and weighted context-free grammars.

Rustem Takhanov, Vladimir Kolmogorov

Intell. Data Anal., 2022

OrderedCuts: A new approach for computing Gomory-Hu tree.

Vladimir Kolmogorov

CoRR, 2022

A computational study of Gomory-Hu tree algorithms.

Vladimir Kolmogorov

CoRR, 2022

2021

One-sided Frank-Wolfe algorithms for saddle problems.

Vladimir Kolmogorov, Thomas Pock

Proceedings of the 38th International Conference on Machine Learning, 2021

A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.

David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov

Proceedings of the Approximation, 2021

2020

Practical Frank-Wolfe algorithms.

Vladimir Kolmogorov

CoRR, 2020

2019

A Local Lemma for Focused Stochastic Algorithms.

Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov

SIAM J. Comput., 2019

Function Norms for Neural Networks.

Amal Rannen-Triki, Maxim Berman, Vladimir Kolmogorov, Matthew B. Blaschko

Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision Workshops, 2019

Testing the Complexity of a Valued CSP Language.

Vladimir Kolmogorov

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

MAP Inference via Block-Coordinate Frank-Wolfe Algorithm.

Paul Swoboda, Vladimir Kolmogorov

Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019

2018

Superconcentrators of Density 25.3.

Vladimir Kolmogorov, Michal Rolínek

Ars Comb., 2018

Efficient Optimization for Rank-Based Loss Functions.

Pritish Mohapatra, Michal Rolínek, C. V. Jawahar, Vladimir Kolmogorov, M. Pawan Kumar

Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition, 2018

A Faster Approximation Algorithm for the Gibbs Partition Function.

Vladimir Kolmogorov

Proceedings of the Conference On Learning Theory, 2018

2017

Even Delta-Matroids and the Complexity of Planar Boolean CSPs.

Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Total Variation on a Tree.

Vladimir Kolmogorov, Thomas Pock, Michal Rolínek

SIAM J. Imaging Sci., 2016

Commutativity in the Algorithmic Lovász Local Lemma.

Vladimir Kolmogorov

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model.

Joël Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak, Stefano Tessaro

Proceedings of the Advances in Cryptology - EUROCRYPT 2016, 2016

2015

The Power of Linear Programming for General-Valued CSPs.

Vladimir Kolmogorov, Johan Thapper, Stanislav Zivný

SIAM J. Comput., 2015

A New Look at Reweighted Message Passing.

Vladimir Kolmogorov

IEEE Trans. Pattern Anal. Mach. Intell., 2015

Commutativity in the Random Walk formulation of the Lovasz Local Lemma.

Vladimir Kolmogorov

CoRR, 2015

Effectiveness of Structural Restrictions for Hybrid CSPs.

Vladimir Kolmogorov, Michal Rolínek, Rustem Takhanov

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

The Complexity of General-Valued CSPs.

Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

A multi-plane block-coordinate frank-wolfe algorithm for training structural SVMs with a costly max-oracle.

Neel Shah, Vladimir Kolmogorov, Christoph H. Lampert

Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015

Proofs of Space.

Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, Krzysztof Pietrzak

Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

2014

Kolmogorov and Zabih's Graph Cuts Stereo Matching Algorithm.

Vladimir Kolmogorov, Pascal Monasse, Pauline Tan

Image Process. Line, 2014

A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Structural SVMs with a Costly max-Oracle.

Neel Shah, Vladimir Kolmogorov, Christoph H. Lampert

CoRR, 2014

Proceedings of The 38th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM), 2014.

Vladimir Kolmogorov, Christoph H. Lampert, Emilie Morvant, Rustem Takhanov

CoRR, 2014

Tree-Reweighted Message Passing.

Vladimir Kolmogorov

Proceedings of the Tractability: Practical Approaches to Hard Problems, 2014

2013

A Dual Decomposition Approach to Feature Correspondence.

Lorenzo Torresani, Vladimir Kolmogorov, Carsten Rother

IEEE Trans. Pattern Anal. Mach. Intell., 2013

Reweighted message passing revisited.

Vladimir Kolmogorov

CoRR, 2013

Inference algorithms for pattern-based CRFs on sequence data.

Rustem Takhanov, Vladimir Kolmogorov

Proceedings of the 30th International Conference on Machine Learning, 2013

Partial Enumeration and Curvature Regularization.

Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov

Proceedings of the IEEE International Conference on Computer Vision, 2013

Potts Model, Parametric Maxflow and K-Submodular Functions.

Igor Gridchyn, Vladimir Kolmogorov

Proceedings of the IEEE International Conference on Computer Vision, 2013

The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization.

Vladimir Kolmogorov

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Computing the M Most Probable Modes of a Graphical Model.

Chao Chen, Vladimir Kolmogorov, Yan Zhu, Dimitris N. Metaxas, Christoph H. Lampert

Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, 2013

Optimal Coalition Structure Generation in Cooperative Graph Games.

Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, Morteza Zadimoghaddam

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012

Minimizing a sum of submodular functions.

Vladimir Kolmogorov

Discret. Appl. Math., 2012

The power of linear programming for valued CSPs: a constructive characterization

Vladimir Kolmogorov

CoRR, 2012

Generalized sequential tree-reweighted message passing

Vladimir Kolmogorov, Thomas Schoenemann

CoRR, 2012

The complexity of conservative valued CSPs.

Vladimir Kolmogorov, Stanislav Zivný

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Towards Minimizing k-Submodular Functions.

Anna Huber, Vladimir Kolmogorov

Proceedings of the Combinatorial Optimization - Second International Symposium, 2012

2011

Optimal Coalition Structures in Graph Games

Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, Morteza Zadimoghaddam

CoRR, 2011

Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions.

Vladimir Kolmogorov

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Dynamic Tree Block Coordinate Ascent.

Daniel Tarlow, Dhruv Batra, Pushmeet Kohli, Vladimir Kolmogorov

Proceedings of the 28th International Conference on Machine Learning, 2011

Object cosegmentation.

Sara Vicente, Carsten Rother, Vladimir Kolmogorov

Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, 2011

Submodular decomposition framework for inference in associative Markov networks with global constraints.

Anton Osokin, Dmitry P. Vetrov, Vladimir Kolmogorov

Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, 2011

Team coverage games.

Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov

Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), 2011

2010

A dichotomy theorem for conservative general-valued CSPs

Vladimir Kolmogorov

CoRR, 2010

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms

Vladimir Kolmogorov, Stanislav Zivný

CoRR, 2010

The complexity of conservative finite-valued CSPs

Vladimir Kolmogorov, Stanislav Zivný

CoRR, 2010

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph.

Vladimir Kolmogorov

Algorithmica, 2010

Generalized roof duality and bisubmodular functions.

Vladimir Kolmogorov

Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

Cosegmentation Revisited: Models and Optimization.

Sara Vicente, Vladimir Kolmogorov, Carsten Rother

Proceedings of the Computer Vision, 2010

2009

Blossom V: a new implementation of a minimum cost perfect matching algorithm.

Vladimir Kolmogorov

Math. Program. Comput., 2009

An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs.

M. Pawan Kumar, Vladimir Kolmogorov, Philip H. S. Torr

J. Mach. Learn. Res., 2009

New algorithms for convex cost tension problem with application to computer vision.

Vladimir Kolmogorov, Akiyoshi Shioura

Discret. Optim., 2009

A global perspective on MAP inference for low-level vision.

Oliver J. Woodford, Carsten Rother, Vladimir Kolmogorov

Proceedings of the IEEE 12th International Conference on Computer Vision, ICCV 2009, Kyoto, Japan, September 27, 2009

Joint optimization of segmentation and appearance models.

Sara Vicente, Vladimir Kolmogorov, Carsten Rother

Proceedings of the IEEE 12th International Conference on Computer Vision, ICCV 2009, Kyoto, Japan, September 27, 2009

2008

A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors.

Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall F. Tappen, Carsten Rother

IEEE Trans. Pattern Anal. Mach. Intell., 2008

Probabilistic Fusion of Stereo with Color and Contrast for Bi-Layer Segmentation.

Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother

Int. J. Comput. Vis., 2008

On partial optimality in multi-label MRFs.

Pushmeet Kohli, Alexander Shekhovtsov, Carsten Rother, Vladimir Kolmogorov, Philip H. S. Torr

Proceedings of the Machine Learning, 2008

Feature Correspondence Via Graph Matching: Models and Global Optimization.

Lorenzo Torresani, Vladimir Kolmogorov, Carsten Rother

Proceedings of the Computer Vision, 2008

Graph cut based image segmentation with connectivity priors.

Sara Vicente, Vladimir Kolmogorov, Carsten Rother

Proceedings of the 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2008), 2008

2007

Minimizing Nonsubmodular Functions with Graph Cuts-A Review.

Vladimir Kolmogorov, Carsten Rother

IEEE Trans. Pattern Anal. Mach. Intell., 2007

An Analysis of Convex Relaxations for MAP Estimation.

Pawan Kumar Mudigonda, Vladimir Kolmogorov, Philip H. S. Torr

Proceedings of the Advances in Neural Information Processing Systems 20, 2007

Applications of parametric maxflow in computer vision.

Vladimir Kolmogorov, Yuri Boykov, Carsten Rother

Proceedings of the IEEE 11th International Conference on Computer Vision, 2007

Optimizing Binary MRFs via Extended Roof Duality.

Carsten Rother, Vladimir Kolmogorov, Victor S. Lempitsky, Martin Szummer

Proceedings of the 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007), 2007

2006

Probabilistic Fusion of Stereo with Color and Contrast for Bilayer Segmentation.

Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother

IEEE Trans. Pattern Anal. Mach. Intell., 2006

A Comparative Study of Energy Minimization Methods for Markov Random Fields.

Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall F. Tappen, Carsten Rother

Proceedings of the Computer Vision, 2006

Comparison of Energy Minimization Algorithms for Highly Connected Graphs.

Vladimir Kolmogorov, Carsten Rother

Proceedings of the Computer Vision, 2006

An Integral Solution to Surface Evolution PDEs Via Geo-cuts.

Yuri Boykov, Vladimir Kolmogorov, Daniel Cremers, Andrew Delong

Proceedings of the Computer Vision, 2006

Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs.

Carsten Rother, Thomas P. Minka, Andrew Blake, Vladimir Kolmogorov

Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), 2006

Bilayer Segmentation of Live Video.

Antonio Criminisi, Geoffrey Cross, Andrew Blake, Vladimir Kolmogorov

Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), 2006

Graph Cut Algorithms for Binocular Stereo with Occlusions.

Vladimir Kolmogorov, Ramin Zabih

Proceedings of the Handbook of Mathematical Models in Computer Vision, 2006

2005

On the Optimality of Tree-reweighted Max-product Message-passing.

Vladimir Kolmogorov, Martin J. Wainwright

Proceedings of the UAI '05, 2005

Fusion of Stereo, Colour and Contrast.

Andrew Blake, Antonio Criminisi, Geoffrey Cross, Vladimir Kolmogorov, Carsten Rother

Proceedings of the Robotics Research: Results of the 12th International Symposium, 2005

What Metrics Can Be Approximated by Geo-Cuts, Or Global Optimization of Length/Area and Flux.

Vladimir Kolmogorov, Yuri Boykov

Proceedings of the 10th IEEE International Conference on Computer Vision (ICCV 2005), 2005

Digital Tapestry.

Carsten Rother, Sanjiv Kumar, Vladimir Kolmogorov, Andrew Blake

Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 2005

Bi-Layer Segmentation of Binocular Stereo Video.

Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother

Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), 2005

Convergent tree-reweighted message passing for energy minimization.

Vladimir Kolmogorov

Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, 2005

2004

Graph Based Algorithms for Scene Reconstruction from Two or More Views.

Vladimir Kolmogorov

PhD thesis, 2004

"GrabCut": interactive foreground extraction using iterated graph cuts.

Carsten Rother, Vladimir Kolmogorov, Andrew Blake

ACM Trans. Graph., 2004

Spatially Coherent Clustering Using Graph Cuts.

Ramin Zabih, Vladimir Kolmogorov

Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2004), with CD-ROM, 27 June, 2004

2003

Visual Correspondence Using Energy Minimization and Mutual Information.

Junhwan Kim, Vladimir Kolmogorov, Ramin Zabih

Proceedings of the 9th IEEE International Conference on Computer Vision (ICCV 2003), 2003

Computing Geodesics and Minimal Surfaces via Graph Cuts.

Yuri Boykov, Vladimir Kolmogorov

Proceedings of the 9th IEEE International Conference on Computer Vision (ICCV 2003), 2003

Generalized Multi-camera Scene Reconstruction Using Graph Cuts.

Vladimir Kolmogorov, Ramin Zabih, Steven J. Gortler

Proceedings of the Energy Minimization Methods in Computer Vision and Pattern Recognition, 2003

2002

Multi-camera Scene Reconstruction via Graph Cuts.

Vladimir Kolmogorov, Ramin Zabih

Proceedings of the Computer Vision, 2002

What Energy Functions Can Be Minimized via Graph Cuts?

Vladimir Kolmogorov, Ramin Zabih

Proceedings of the Computer Vision, 2002

2001

Computing Visual Correspondence with Occlusions via Graph Cuts.

Vladimir Kolmogorov, Ramin Zabih

Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), Vancouver, British Columbia, Canada, July 7-14, 2001, 2001

An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision.

Yuri Boykov, Vladimir Kolmogorov

Proceedings of the Energy Minimization Methods in Computer Vision and Pattern Recognition, 2001