Vladimir Kolmogorov

141 papers A* 29A 4B 3C 2Journal 77Unranked 23

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph. CoRR Vladimir Kolmogorov, Jack Spalding-Jamieson
2026	A*	`conf`	Faster algorithms for packing forests in graphs and related problems. SODA Pavel A. Arkhipov, Vladimir Kolmogorov
2025	J	`jnl`	A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. Theory Comput. David G. Harris, Fotios Iliopoulos, Vladimir Kolmogorov
2025	J	`jnl`	A Simpler and Parallelizable $\boldsymbol{O(\sqrt{\log n})}$-Approximation Algorithm for Sparsest Cut. ACM Trans. Algorithms Vladimir Kolmogorov
2025	J	`jnl`	Certifying Solutions of Degenerate Semidefinite Programs. SIAM J. Optim. Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata
2025	J	`jnl`	Composition Direction of Seymour's Theorem for Regular Matroids - Formally Verified. CoRR Martin Dvorak, Tristan Figueroa-Reid, Rida Hamadani, Byung-Hak Hwang, Evgenia Karunus, Vladimir Kolmogorov, Alexander Meiburg, Alexander Nelson, Peter Nelson, Mark Sandey, Ivan Sergeev
2025	J	`jnl`	Generalized minimum 0-extension problem and discrete convexity. Math. Program. Martin Dvorak, Vladimir Kolmogorov
2025	J	`jnl`	Greedy matroid base packings with applications to dynamic graph density and orientations. CoRR Pavel A. Arkhipov, Vladimir Kolmogorov
2025	J	`jnl`	Parameter Estimation for Gibbs Distributions. ACM Trans. Algorithms David G. Harris, Vladimir Kolmogorov
2024	B	`conf`	A Simpler and Parallelizable O(√log n)-approximation Algorithm for Sparsest Cut. SPAA Vladimir Kolmogorov
2024	J	`jnl`	A faster algorithm for the CoRR Pavel A. Arkhipov, Vladimir Kolmogorov
2024	J	`jnl`	Duality theory in linear optimization and its extensions - formally verified. CoRR Martin Dvorak, Vladimir Kolmogorov
2024	J	`jnl`	Verifying feasibility of degenerate semidefinite programs. CoRR Vladimir Kolmogorov, Simone Naldi, Jeferson Zapata
2023	J	`jnl`	A simpler and parallelizable O(√log n)-approximation algorithm for Sparsest Cut. CoRR Vladimir Kolmogorov
2023	A*	`conf`	Parameter Estimation for Gibbs Distributions. ICALP David G. Harris, Vladimir Kolmogorov
2023	A*	`conf`	Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions. CVPR Vladimir Kolmogorov
2022	J	`jnl`	Combining pattern-based CRFs and weighted context-free grammars. Intell. Data Anal. Rustem Takhanov, Vladimir Kolmogorov
2022	J	`jnl`	OrderedCuts: A new approach for computing Gomory-Hu tree. CoRR Vladimir Kolmogorov
2021	—	`conf`	A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. APPROX-RANDOM David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
2021	J	`jnl`	Generalized minimum 0-extension problem and discrete convexity. CoRR Martin Dvorak, Vladimir Kolmogorov
2021	A*	`conf`	One-sided Frank-Wolfe algorithms for saddle problems. ICML Vladimir Kolmogorov, Thomas Pock
2020	J	`jnl`	A new notion of commutativity for the algorithmic Lovász Local Lemma. CoRR David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
2020	J	`jnl`	Parameter estimation for Gibbs distributions. CoRR David G. Harris, Vladimir Kolmogorov
2020	J	`jnl`	Practical Frank-Wolfe algorithms. CoRR Vladimir Kolmogorov
2019	J	`jnl`	A Local Lemma for Focused Stochastic Algorithms. SIAM J. Comput. Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov
2019	J	`jnl`	Even Delta-Matroids and the Complexity of Planar Boolean CSPs. ACM Trans. Algorithms Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
2019	—	`conf`	Function Norms for Neural Networks. ICCV Workshops Amal Rannen-Triki, Maxim Berman, Vladimir Kolmogorov, Matthew B. Blaschko
2019	A*	`conf`	MAP Inference via Block-Coordinate Frank-Wolfe Algorithm. CVPR Paul Swoboda, Vladimir Kolmogorov
2019	A*	`conf`	Testing the Complexity of a Valued CSP Language. ICALP Vladimir Kolmogorov
2018	A*	`conf`	A Faster Approximation Algorithm for the Gibbs Partition Function. COLT Vladimir Kolmogorov
2018	J	`jnl`	A Local Lemma for Focused Stochastic Algorithms. CoRR Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov
2018	J	`jnl`	Commutativity in the Algorithmic Lovász Local Lemma. SIAM J. Comput. Vladimir Kolmogorov
2018	A*	`conf`	Efficient Optimization for Rank-Based Loss Functions. CVPR Pritish Mohapatra, Michal Rolínek, C. V. Jawahar, Vladimir Kolmogorov, M. Pawan Kumar
2018	J	`jnl`	MAP inference via Block-Coordinate Frank-Wolfe Algorithm. CoRR Paul Swoboda, Vladimir Kolmogorov
2018	J	`jnl`	Superconcentrators of Density 25.3. Ars Comb. Vladimir Kolmogorov, Michal Rolínek
2018	J	`jnl`	Testing the complexity of a valued CSP language. CoRR Vladimir Kolmogorov
2017	A*	`conf`	Even Delta-Matroids and the Complexity of Planar Boolean CSPs. SODA Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
2017	J	`jnl`	The Complexity of General-Valued CSPs. SIAM J. Comput. Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2016	J	`jnl`	A Faster Approximation Algorithm for the Gibbs Partition Function. CoRR Vladimir Kolmogorov
2016	A*	`conf`	Commutativity in the Algorithmic Lovász Local Lemma. FOCS Vladimir Kolmogorov
2016	J	`jnl`	Efficient Optimization for Rank-based Loss Functions. CoRR Pritish Mohapatra, Michal Rolínek, C. V. Jawahar, Vladimir Kolmogorov, M. Pawan Kumar
2016	J	`jnl`	Even Delta-Matroids and the Complexity of Planar Boolean CSPs. CoRR Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
2016	J	`jnl`	Inference Algorithms for Pattern-Based CRFs on Sequence Data. Algorithmica Vladimir Kolmogorov, Rustem Takhanov
2016	—	`conf`	On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model. EUROCRYPT (2) Joël Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak, Stefano Tessaro
2016	J	`jnl`	On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model. IACR Cryptol. ePrint Arch. Joël Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak, Stefano Tessaro
2016	J	`jnl`	Total Variation on a Tree. SIAM J. Imaging Sci. Vladimir Kolmogorov, Thomas Pock, Michal Rolínek
2015	J	`jnl`	A New Look at Reweighted Message Passing. IEEE Trans. Pattern Anal. Mach. Intell. Vladimir Kolmogorov
2015	A*	`conf`	A multi-plane block-coordinate frank-wolfe algorithm for training structural SVMs with a costly max-oracle. CVPR Neel Shah, Vladimir Kolmogorov, Christoph H. Lampert
2015	J	`jnl`	Commutativity in the Random Walk formulation of the Lovasz Local Lemma. CoRR Vladimir Kolmogorov
2015	B	`conf`	Effectiveness of Structural Restrictions for Hybrid CSPs. ISAAC Vladimir Kolmogorov, Michal Rolínek, Rustem Takhanov
2015	J	`jnl`	Effectiveness of Structural Restrictions for Hybrid CSPs. CoRR Vladimir Kolmogorov, Michal Rolínek, Rustem Takhanov
2015	—	`conf`	Proofs of Space. CRYPTO (2) Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, Krzysztof Pietrzak
2015	A*	`conf`	The Complexity of General-Valued CSPs. FOCS Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2015	J	`jnl`	The Complexity of General-Valued CSPs. CoRR Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2015	J	`jnl`	The Power of Linear Programming for General-Valued CSPs. SIAM J. Comput. Vladimir Kolmogorov, Johan Thapper, Stanislav Zivný
2015	J	`jnl`	Total variation on a tree. CoRR Vladimir Kolmogorov, Thomas Pock, Michal Rolínek
2014	J	`jnl`	A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Structural SVMs with a Costly max-Oracle. CoRR Neel Shah, Vladimir Kolmogorov, Christoph H. Lampert
2014	J	`jnl`	Combining pattern-based CRFs and weighted context-free grammars. CoRR Rustem Takhanov, Vladimir Kolmogorov
2014	J	`jnl`	Kolmogorov and Zabih's Graph Cuts Stereo Matching Algorithm. Image Process. Line Vladimir Kolmogorov, Pascal Monasse, Pauline Tan
2014	J	`jnl`	Proceedings of The 38th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM), 2014. CoRR Vladimir Kolmogorov, Christoph H. Lampert, Emilie Morvant, Rustem Takhanov
2014	J	`jnl`	Superconcentrators of Density 25.3. CoRR Vladimir Kolmogorov, Michal Rolínek
2014	—	`ch.`	Tree-Reweighted Message Passing. Tractability Vladimir Kolmogorov
2013	J	`jnl`	A Dual Decomposition Approach to Feature Correspondence. IEEE Trans. Pattern Anal. Mach. Intell. Lorenzo Torresani, Vladimir Kolmogorov, Carsten Rother
2013	A	`conf`	Computing the M Most Probable Modes of a Graphical Model. AISTATS Chao Chen, Vladimir Kolmogorov, Yan Zhu, Dimitris N. Metaxas, Christoph H. Lampert
2013	—	`conf`	Inference algorithms for pattern-based CRFs on sequence data. ICML (3) Rustem Takhanov, Vladimir Kolmogorov
2013	A*	`conf`	Optimal Coalition Structure Generation in Cooperative Graph Games. AAAI Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, Morteza Zadimoghaddam
2013	A*	`conf`	Partial Enumeration and Curvature Regularization. ICCV Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
2013	A*	`conf`	Potts Model, Parametric Maxflow and K-Submodular Functions. ICCV Igor Gridchyn, Vladimir Kolmogorov
2013	J	`jnl`	Potts model, parametric maxflow and k-submodular functions. CoRR Igor Gridchyn, Vladimir Kolmogorov
2013	J	`jnl`	Proofs of Space. IACR Cryptol. ePrint Arch. Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, Krzysztof Pietrzak
2013	J	`jnl`	Reweighted message passing revisited. CoRR Vladimir Kolmogorov
2013	—	`conf`	The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. ICALP (1) Vladimir Kolmogorov
2013	J	`jnl`	The complexity of conservative valued CSPs. J. ACM Vladimir Kolmogorov, Stanislav Zivný
2013	J	`jnl`	The power of linear programming for general-valued CSPs. CoRR Vladimir Kolmogorov, Johan Thapper, Stanislav Zivný
2013	J	`jnl`	Towards Minimizing k-Submodular Functions. CoRR Anna Huber, Vladimir Kolmogorov
2012	J	`jnl`	Generalized roof duality and bisubmodular functions. Discret. Appl. Math. Vladimir Kolmogorov
2012	J	`jnl`	Generalized sequential tree-reweighted message passing CoRR Vladimir Kolmogorov, Thomas Schoenemann
2012	J	`jnl`	Inference algorithms for pattern-based CRFs on sequence data CoRR Rustem Takhanov, Vladimir Kolmogorov
2012	J	`jnl`	Minimizing a sum of submodular functions. Discret. Appl. Math. Vladimir Kolmogorov
2012	J	`jnl`	On the optimality of tree-reweighted max-product message-passing CoRR Vladimir Kolmogorov, Martin J. Wainwright
2012	A*	`conf`	The complexity of conservative valued CSPs. SODA Vladimir Kolmogorov, Stanislav Zivný
2012	J	`jnl`	The power of linear programming for valued CSPs: a constructive characterization CoRR Vladimir Kolmogorov
2012	C	`conf`	Towards Minimizing k-Submodular Functions. ISCO Anna Huber, Vladimir Kolmogorov
2011	A*	`conf`	Dynamic Tree Block Coordinate Ascent. ICML Daniel Tarlow, Dhruv Batra, Pushmeet Kohli, Vladimir Kolmogorov
2011	A*	`conf`	Object cosegmentation. CVPR Sara Vicente, Carsten Rother, Vladimir Kolmogorov
2011	J	`jnl`	Optimal Coalition Structures in Graph Games CoRR Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, Morteza Zadimoghaddam
2011	J	`jnl`	Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints CoRR Anton Osokin, Dmitry P. Vetrov, Vladimir Kolmogorov
2011	A*	`conf`	Submodular decomposition framework for inference in associative Markov networks with global constraints. CVPR Anton Osokin, Dmitry P. Vetrov, Vladimir Kolmogorov
2011	B	`conf`	Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions. MFCS Vladimir Kolmogorov
2011	A	`conf`	Team coverage games. AAMAS Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov
2011	J	`jnl`	The complexity of conservative valued CSPs CoRR Vladimir Kolmogorov, Stanislav Zivný
2010	J	`jnl`	A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph. Algorithmica Vladimir Kolmogorov
2010	J	`jnl`	A dichotomy theorem for conservative general-valued CSPs CoRR Vladimir Kolmogorov
2010	—	`conf`	Cosegmentation Revisited: Models and Optimization. ECCV (2) Sara Vicente, Vladimir Kolmogorov, Carsten Rother
2010	J	`jnl`	Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms CoRR Vladimir Kolmogorov, Stanislav Zivný
2010	J	`jnl`	Generalized roof duality and bisubmodular functions CoRR Vladimir Kolmogorov
2010	—	`conf`	Generalized roof duality and bisubmodular functions. NIPS Vladimir Kolmogorov
2010	J	`jnl`	Minimizing a sum of submodular functions CoRR Vladimir Kolmogorov
2010	J	`jnl`	Submodularity on a tree: Unifying $L^\natural$-convex and bisubmodular functions CoRR Vladimir Kolmogorov
2010	J	`jnl`	The complexity of conservative finite-valued CSPs CoRR Vladimir Kolmogorov, Stanislav Zivný
2009	A*	`conf`	A global perspective on MAP inference for low-level vision. ICCV Oliver J. Woodford, Carsten Rother, Vladimir Kolmogorov
2009	J	`jnl`	An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs. J. Mach. Learn. Res. M. Pawan Kumar, Vladimir Kolmogorov, Philip H. S. Torr
2009	J	`jnl`	Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. Vladimir Kolmogorov
2009	A*	`conf`	Joint optimization of segmentation and appearance models. ICCV Sara Vicente, Vladimir Kolmogorov, Carsten Rother
2009	J	`jnl`	New algorithms for convex cost tension problem with application to computer vision. Discret. Optim. Vladimir Kolmogorov, Akiyoshi Shioura
2008	J	`jnl`	A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors. IEEE Trans. Pattern Anal. Mach. Intell. Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall F. Tappen, Carsten Rother
2008	—	`conf`	Feature Correspondence Via Graph Matching: Models and Global Optimization. ECCV (2) Lorenzo Torresani, Vladimir Kolmogorov, Carsten Rother
2008	A*	`conf`	Graph cut based image segmentation with connectivity priors. CVPR Sara Vicente, Vladimir Kolmogorov, Carsten Rother
2008	A*	`conf`	On partial optimality in multi-label MRFs. ICML Pushmeet Kohli, Alexander Shekhovtsov, Carsten Rother, Vladimir Kolmogorov, Philip H. S. Torr
2008	J	`jnl`	Probabilistic Fusion of Stereo with Color and Contrast for Bi-Layer Segmentation. Int. J. Comput. Vis. Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother
2007	—	`conf`	An Analysis of Convex Relaxations for MAP Estimation. NIPS Pawan Kumar Mudigonda, Vladimir Kolmogorov, Philip H. S. Torr
2007	A*	`conf`	Applications of parametric maxflow in computer vision. ICCV Vladimir Kolmogorov, Yuri Boykov, Carsten Rother
2007	J	`jnl`	Minimizing Nonsubmodular Functions with Graph Cuts-A Review. IEEE Trans. Pattern Anal. Mach. Intell. Vladimir Kolmogorov, Carsten Rother
2007	A*	`conf`	Optimizing Binary MRFs via Extended Roof Duality. CVPR Carsten Rother, Vladimir Kolmogorov, Victor S. Lempitsky, Martin Szummer
2006	—	`conf`	A Comparative Study of Energy Minimization Methods for Markov Random Fields. ECCV (2) Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall F. Tappen, Carsten Rother
2006	—	`conf`	An Integral Solution to Surface Evolution PDEs Via Geo-cuts. ECCV (3) Yuri Boykov, Vladimir Kolmogorov, Daniel Cremers, Andrew Delong
2006	—	`conf`	Bilayer Segmentation of Live Video. CVPR (1) Antonio Criminisi, Geoffrey Cross, Andrew Blake, Vladimir Kolmogorov
2006	—	`conf`	Comparison of Energy Minimization Algorithms for Highly Connected Graphs. ECCV (2) Vladimir Kolmogorov, Carsten Rother
2006	J	`jnl`	Convergent Tree-Reweighted Message Passing for Energy Minimization. IEEE Trans. Pattern Anal. Mach. Intell. Vladimir Kolmogorov
2006	—	`conf`	Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs. CVPR (1) Carsten Rother, Thomas P. Minka, Andrew Blake, Vladimir Kolmogorov
2006	—	`ch.`	Graph Cut Algorithms for Binocular Stereo with Occlusions. Handbook of Mathematical Models in Computer Vision Vladimir Kolmogorov, Ramin Zabih
2006	J	`jnl`	Probabilistic Fusion of Stereo with Color and Contrast for Bilayer Segmentation. IEEE Trans. Pattern Anal. Mach. Intell. Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother
2005	—	`conf`	Bi-Layer Segmentation of Binocular Stereo Video. CVPR (2) Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother
2005	—	`conf`	Bi-Layer Segmentation of Binocular Stereo Video. CVPR (2) Vladimir Kolmogorov, Antonio Criminisi, Andrew Blake, Geoffrey Cross, Carsten Rother
2005	A	`conf`	Convergent tree-reweighted message passing for energy minimization. AISTATS Vladimir Kolmogorov
2005	—	`conf`	Digital Tapestry. CVPR (1) Carsten Rother, Sanjiv Kumar, Vladimir Kolmogorov, Andrew Blake
2005	C	`conf`	Fusion of Stereo, Colour and Contrast. ISRR Andrew Blake, Antonio Criminisi, Geoffrey Cross, Vladimir Kolmogorov, Carsten Rother
2005	A	`conf`	On the Optimality of Tree-reweighted Max-product Message-passing. UAI Vladimir Kolmogorov, Martin J. Wainwright
2005	A*	`conf`	What Metrics Can Be Approximated by Geo-Cuts, Or Global Optimization of Length/Area and Flux. ICCV Vladimir Kolmogorov, Yuri Boykov
2004	J	`jnl`	"GrabCut": interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. Carsten Rother, Vladimir Kolmogorov, Andrew Blake
2004	J	`jnl`	An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Trans. Pattern Anal. Mach. Intell. Yuri Boykov, Vladimir Kolmogorov
2004	—	`—`	Graph Based Algorithms for Scene Reconstruction from Two or More Views. Vladimir Kolmogorov
2004	—	`conf`	Spatially Coherent Clustering Using Graph Cuts. CVPR (2) Ramin Zabih, Vladimir Kolmogorov
2004	J	`jnl`	What Energy Functions Can Be Minimized via Graph Cuts? IEEE Trans. Pattern Anal. Mach. Intell. Vladimir Kolmogorov, Ramin Zabih
2003	A*	`conf`	Computing Geodesics and Minimal Surfaces via Graph Cuts. ICCV Yuri Boykov, Vladimir Kolmogorov
2003	—	`conf`	Generalized Multi-camera Scene Reconstruction Using Graph Cuts. EMMCVPR Vladimir Kolmogorov, Ramin Zabih, Steven J. Gortler
2003	A*	`conf`	Visual Correspondence Using Energy Minimization and Mutual Information. ICCV Junhwan Kim, Vladimir Kolmogorov, Ramin Zabih
2002	—	`conf`	Multi-camera Scene Reconstruction via Graph Cuts. ECCV (3) Vladimir Kolmogorov, Ramin Zabih
2002	—	`conf`	What Energy Functions Can Be Minimized via Graph Cuts? ECCV (3) Vladimir Kolmogorov, Ramin Zabih
2001	—	`conf`	An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision. EMMCVPR Yuri Boykov, Vladimir Kolmogorov
2001	A*	`conf`	Computing Visual Correspondence with Occlusions via Graph Cuts. ICCV Vladimir Kolmogorov, Ramin Zabih