ISTA Research Explorer

Vladimir Kolmogorov

Kolmogorov Group

94 Publications

[94]

2024 | Journal Article | IST-REx-ID: 10045 |

Dvorak M, Kolmogorov V. 2024. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming., 2109.10203.

[Preprint] View | Files available | DOI | arXiv

[93]

2023 | Conference Paper | IST-REx-ID: 14084 |

Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72.

[Published Version] View | Files available | DOI | arXiv

[92]

2023 | Conference Paper | IST-REx-ID: 14448 |

Kolmogorov V. 2023. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2023, 11980–11989.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[91]

2022 | Journal Article | IST-REx-ID: 10737 |

Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[90]

2021 | Conference Paper | IST-REx-ID: 10072 |

Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs, vol. 207, 31.

[Published Version] View | Files available | DOI | arXiv

[89]

2021 | Conference Paper | IST-REx-ID: 10552 |

Kolmogorov V, Pock T. 2021. One-sided Frank-Wolfe algorithms for saddle problems. 38th International Conference on Machine Learning. ICML: International Conference on Machine Learning.

[Preprint] View | Download Preprint (ext.) | arXiv

[88]

2019 | Conference Paper | IST-REx-ID: 6725 |

Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.

[Published Version] View | Files available | DOI | arXiv

[87]

2019 | Journal Article | IST-REx-ID: 7412 |

Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[86]

2019 | Conference Paper | IST-REx-ID: 7468 |

Swoboda P, Kolmogorov V. 2019. Map inference via block-coordinate Frank-Wolfe algorithm. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2019–June, 11138–11147.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[85]

2019 | Conference Paper | IST-REx-ID: 7639

Rannen-Triki A, Berman M, Kolmogorov V, Blaschko MB. 2019. Function norms for neural networks. Proceedings of the 2019 International Conference on Computer Vision Workshop. ICCVW: International Conference on Computer Vision Workshop, 748–752.

View | DOI | WoS

[84]

2018 | Conference Paper | IST-REx-ID: 273 |

Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[83]

2018 | Journal Article | IST-REx-ID: 5975 |

Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.

[82]

2018 | Journal Article | IST-REx-ID: 18 |

Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304.

[Preprint] View | Download Preprint (ext.) | WoS | arXiv

[81]

2018 | Journal Article | IST-REx-ID: 6032 |

Kazda A, Kolmogorov V, Rolinek M. 2018. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 15(2), 22.

[80]

2017 | Journal Article | IST-REx-ID: 644 |

Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued CSPs. SIAM Journal on Computing. 46(3), 1087–1110.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[79]

2017 | Conference Paper | IST-REx-ID: 1192 |

Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.

[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.) | WoS

[78]

2017 | Conference Paper | IST-REx-ID: 274 |

Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual Conference on Learning Theory vol. 75, 228–249.

[Published Version] View | Files available | arXiv

[77]

2016 | Conference Paper | IST-REx-ID: 1231 |

Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9666, 358–387.

[Submitted Version] View | DOI | Download Submitted Version (ext.)

[76]

2016 | Journal Article | IST-REx-ID: 1377 |

Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636.

[Preprint] View | DOI | Download Preprint (ext.)

[75]

2016 | Conference Paper | IST-REx-ID: 1193 |

Kolmogorov V. 2016. Commutativity in the algorithmic Lovasz local lemma. Proceedings - Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2016–December, 7782993.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[74]

2016 | Journal Article | IST-REx-ID: 1794 |

Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[73]

2015 | Conference Paper | IST-REx-ID: 1636 |

Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 9472, 566–577.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[72]

2015 | Journal Article | IST-REx-ID: 1841 |

Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37(5), 919–930.

[Preprint] View | DOI | Download Preprint (ext.)

[71]

2015 | Conference Paper | IST-REx-ID: 1859 |

Shah N, Kolmogorov V, Lampert C. 2015. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. CVPR: Computer Vision and Pattern Recognition, 2737–2745.

[Preprint] View | DOI | Download Preprint (ext.)

[70]

2015 | Journal Article | IST-REx-ID: 2271 |

Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[69]

2015 | Conference Paper | IST-REx-ID: 1637 |

Kolmogorov V, Krokhin A, Rolinek M. 2015. The complexity of general-valued CSPs. FOCS: Foundations of Computer Science, 56th Annual Symposium on Foundations of Computer Science, , 1246–1258.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[68]

2015 | Conference Paper | IST-REx-ID: 1675 |

Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 9216, 585–605.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[67]

2014 | Conference Paper | IST-REx-ID: 2275 |

Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.

[Submitted Version] View | Files available | DOI

[66]

2013 | Conference Paper | IST-REx-ID: 2270 |

Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence, 81–87.

View | Download None (ext.) | arXiv

[65]

2013 | Report | IST-REx-ID: 2273 |

Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p.

View | Download (ext.)

[64]

2013 | Conference Paper | IST-REx-ID: 2276 |

Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular functions. ICCV: International Conference on Computer Vision, 2320–2327.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[63]

2013 | Conference Paper | IST-REx-ID: 2518 |

Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965, 625–636.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[62]

2013 | Journal Article | IST-REx-ID: 2828 |

Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal of the ACM. 60(2), 10.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[61]

2013 | Conference Paper | IST-REx-ID: 2901 |

Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model. AISTATS: Conference on Uncertainty in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.

View | Download None (ext.)

[60]

2013 | Conference Paper | IST-REx-ID: 2272 |

Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs on sequence data. ICML’13 Proceedings of the 30th International Conference on International. ICML: International Conference on Machine Learning, JMLR, vol. 28, 145–153.

[Submitted Version] View | Files available | Download Submitted Version (ext.)

[59]

2013 | Report | IST-REx-ID: 2274 |

Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space, IST Austria,p.

[Published Version] View | Files available

[58]

2012 | Conference Paper | IST-REx-ID: 2930 |

Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.

[Preprint] View | DOI | Download Preprint (ext.)

[57]

2012 | Preprint | IST-REx-ID: 2928 |

Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, .

[Preprint] View | Download Preprint (ext.) | arXiv

[56]

2012 | Report | IST-REx-ID: 2929 |

Kolmogorov V. 2012. The power of linear programming for valued CSPs: a constructive characterization, Unknown,p.

View | Download (ext.)

[55]

2012 | Journal Article | IST-REx-ID: 2931

Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(2), 259–271.

View | DOI

[54]

2012 | Journal Article | IST-REx-ID: 3117 |

Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 160(15), 2246–2258.

[Preprint] View | DOI | Download Preprint (ext.)

[53]

2012 | Conference Paper | IST-REx-ID: 3284 |

Kolmogorov V, Živný S. 2012. The complexity of conservative valued CSPs. SODA: Symposium on Discrete Algorithms, 750–759.

View | Download (ext.)

[52]

2012 | Journal Article | IST-REx-ID: 3257 |

Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[51]

2012 | Conference Paper | IST-REx-ID: 3124 |

Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, .

[Submitted Version] View | Files available

[50]

2012 | Technical Report | IST-REx-ID: 5396 |

Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p.

[Published Version] View | Files available | DOI

[49]

2011 | Book Chapter | IST-REx-ID: 2922

Vicente S, Kolmogorov V, Rother C. 2011.Graph-cut Based Image Segmentation with Connectivity Priors. In: Markov Random Fields for Vision and Image Processing. .

View

[48]

2011 | Book Chapter | IST-REx-ID: 2923

Kumar MP, Kolmogorov V, Torr P. 2011.Analyzing Convex Relaxations for MAP Estimation. In: Markov Random Fields for Vision and Image Processing. .

View

[47]

2011 | Book Chapter | IST-REx-ID: 2924

Criminisi A, Cross G, Blake A, Kolmogorov V. 2011.Bilayer Segmentation of Video. In: Markov Random Fields for Vision and Image Processing. .

View

[46]

2011 | Book Chapter | IST-REx-ID: 2925

Rother C, Kolmogorov V, Boykov Y, Blake A. 2011.Interactive Foreground Extraction using graph cut. In: Markov Random Fields for Vision and Image Processing. .

View

[45]

2011 | Book Chapter | IST-REx-ID: 2935

Boykov Y, Kolmogorov V. 2011.Basic graph cut algorithms. In: Markov Random Fields for Vision and Image Processing. , 31–50.

View

[44]

2011 | Conference Paper | IST-REx-ID: 3204

Kolmogorov V. 2011. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907, 400–411.

View | DOI | Download (ext.)

[43]

2011 | Conference Paper | IST-REx-ID: 3206

Osokin A, Vetrov D, Kolmogorov V. 2011. Submodular decomposition framework for inference in associative Markov networks with global constraints. CVPR: Computer Vision and Pattern Recognition, 1889–1896.

View | DOI | Download (ext.)

[42]

2011 | Conference Paper | IST-REx-ID: 3205

Tarlow D, Batra D, Kohli P, Kolmogorov V. 2011. Dynamic tree block coordinate ascent. ICML: International Conference on Machine Learning, 113–120.

View | Download (ext.)

[41]

2011 | Conference Paper | IST-REx-ID: 3207

Vicente S, Rother C, Kolmogorov V. 2011. Object cosegmentation. CVPR: Computer Vision and Pattern Recognition, 2217–2224.

View | DOI

[40]

2010 | Journal Article | IST-REx-ID: 3202

Kolmogorov V. 2010. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica. 56(4), 394–412.

View | DOI

[39]

2010 | Conference Paper | IST-REx-ID: 3201

Vicente S, Kolmogorov V, Rother C. 2010. Cosegmentation revisited: Models and optimization. ECCV: European Conference on Computer Vision, LNCS, vol. 6312, 465–479.

View | DOI | Download (ext.)

[38]

2010 | Conference Paper | IST-REx-ID: 2934

Kolmogorov V. 2010. Generalized roof duality and bisubmodular functions. Neural Information Processing Systems.

View | Files available

[37]

2009 | Journal Article | IST-REx-ID: 2932

Kolmogorov V. 2009. Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation. 1(1), 43–67.

View | DOI

[36]

2009 | Conference Paper | IST-REx-ID: 3203

Woodford O, Rother C, Kolmogorov V. 2009. A global perspective on MAP inference for low level vision. ICCV: International Conference on Computer Vision, 2319–2326.

View | DOI

[35]

2009 | Journal Article | IST-REx-ID: 3197 |

Kumar MP, Kolmogorov V, Torr P. 2009. An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research. 10, 71–106.

View | Download (ext.)

[34]

2009 | Conference Paper | IST-REx-ID: 3199

Vicente S, Kolmogorov V, Rother C. 2009. Joint optimization of segmentation and appearance models. ICCV: International Conference on Computer Vision, 755–762.

View | DOI | Download (ext.)

[33]

2009 | Journal Article | IST-REx-ID: 3200

Kolmogorov V, Shioura A. 2009. New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization. 6(4), 378–393.

View | DOI

[32]

2008 | Conference Paper | IST-REx-ID: 3194

Kohli P, Shekhovtsov A, Rother C, Kolmogorov V, Torr P. 2008. On partial optimality in multi label MRFs. ICML: International Conference on Machine Learning, 480–487.

View | DOI | Download (ext.)

[31]

2008 | Journal Article | IST-REx-ID: 3196

Szeliski R, Zabih R, Scharstein D, Veksler O, Kolmogorov V, Agarwala A, Tappen M, Rother C. 2008. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Transactions on Pattern Analysis and Machine Intelligence. 30(6), 1068–1080.

View | DOI

[30]

2008 | Conference Paper | IST-REx-ID: 3198

Torresani L, Kolmogorov V, Rother C. 2008. Feature correspondence via graph matching: Models and global optimization. ECCV: European Conference on Computer Vision, LNCS, vol. 5303, 596–609.

View | DOI | Download (ext.)

[29]

2008 | Conference Paper | IST-REx-ID: 3195

Vicente S, Kolmogorov V, Rother C. 2008. Graph cut based image segmentation with connectivity priors. CVPR: Computer Vision and Pattern Recognition.

View | DOI | Download (ext.)

[28]

2007 | Conference Paper | IST-REx-ID: 2933

Kumar MP, Kolmogorov V, Torr P. 2007. An Analysis of Convex Relaxations for MAP Estimation. Neural Information Processing Systems.

View

[27]

2007 | Conference Paper | IST-REx-ID: 3192

Rother C, Kolmogorov V, Lempitsky V, Szummer M. 2007. Optimizing binary MRFs via extended roof duality. CVPR: Computer Vision and Pattern Recognition.

View | DOI | Download (ext.)

[26]

2007 | Conference Paper | IST-REx-ID: 3191

Kolmogorov V, Boykov Y, Rother C. 2007. Applications of parametric maxflow in computer vision. ICCV: International Conference on Computer Vision.

View | DOI | Download (ext.)

[25]

2007 | Journal Article | IST-REx-ID: 3193

Kolmogorov V, Rother C. 2007. Minimizing nonsubmodular functions with graph cuts - A review. IEEE Transactions on Pattern Analysis and Machine Intelligence. 29(7), 1274–1279.

View | DOI

[24]

2007 | Journal Article | IST-REx-ID: 3187

Blake A, Criminisi A, Cross G, Kolmogorov V, Rother C. 2007. Fusion of stereo colour and contrast. Springer Tracts in Advanced Robotics. 28, 295–304.

View | DOI | Download (ext.)

[23]

2006 | Book Chapter | IST-REx-ID: 2921

Kolmogorov V, Zabih R. 2006.Graph cut algorithms for binocular stereo with occlusions. In: Handbook of Mathematical Models in Computer Vision. , 423–427.

View | DOI

[22]

2006 | Conference Paper | IST-REx-ID: 3189

Criminisi A, Cross G, Blake A, Kolmogorov V. 2006. Bilayer segmentation of live video. CVPR: Computer Vision and Pattern Recognition vol. 1, 53–60.

View | DOI | Download (ext.)

[21]

2006 | Journal Article | IST-REx-ID: 3190

Kolmogorov V. 2006. Convergent tree reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence. 28(10), 1568–1583.

View | DOI | Download (ext.)

[20]

2006 | Conference Paper | IST-REx-ID: 3188

Rother C, Kolmogorov V, Minka T, Blake A. 2006. Cosegmentation of image pairs by histogram matching - Incorporating a global constraint into MRFs. CVPR: Computer Vision and Pattern Recognition, 993–1000.

View | DOI

[19]

2006 | Conference Paper | IST-REx-ID: 3180

Szeliski R, Zabih R, Scharstein D, Veksler O, Kolmogorov V, Agarwala A, Tappen M, Rother C. 2006. A comparative study of energy minimization methods for Markov random fields. ECCV: European Conference on Computer Vision vol. 3952, 16–29.

View | DOI | Download (ext.)

[18]

2006 | Conference Paper | IST-REx-ID: 3184

Kolmogorov V, Rother C. 2006. Comparison of energy minimization algorithms for highly connected graphs. ECCV: European Conference on Computer Vision, LNCS, vol. 3952 LNCS, 1–15.

View | DOI | Download (ext.)

[17]

2006 | Journal Article | IST-REx-ID: 3185

Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2006. Probabilistic fusion of stereo with color and contrast for bilayer segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 28(9), 1480–1492.

View | DOI | Download (ext.)

[16]

2006 | Conference Paper | IST-REx-ID: 3186

Boykov Y, Kolmogorov V, Cremers D, Delong A. 2006. An integral solution to surface evolution PDEs via geo cuts. ECCV: European Conference on Computer Vision, LNCS, vol. 3953, 409–422.

View | DOI

[15]

2005 | Conference Paper | IST-REx-ID: 3175

Rother C, Kumar S, Kolmogorov V, Blake A. 2005. Digital tapestry. CVPR: Computer Vision and Pattern Recognition vol. 1, 589–596.

View | DOI | Download (ext.)

[14]

2005 | Conference Paper | IST-REx-ID: 3176

Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation of binocular stereo video. CVPR: Computer Vision and Pattern Recognition, 1186–1186.

View | DOI

[13]

2005 | Conference Paper | IST-REx-ID: 3183

Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation of binocular stereo video. CVPR: Computer Vision and Pattern Recognition vol. 2, 407–414.

View | DOI | Download (ext.)

[12]

2005 | Conference Paper | IST-REx-ID: 3182

Kolmogorov V, Boykov Y. 2005. What metrics can be approximated by geo cuts or global optimization of length area and flux. ICCV: International Conference on Computer Vision vol. 1, 564–571.

View | DOI

[11]

2005 | Conference Paper | IST-REx-ID: 3181

Kolmogorov V, Wainwright M. 2005. On the optimality of tree reweighted max product message passing. UAI: Uncertainty in Artificial Intelligence, 316–323.

View | Download (ext.)

[10]

2004 | Journal Article | IST-REx-ID: 3178

Boykov Y, Kolmogorov V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence. 26(9), 1124–1137.

View | DOI

[9]

2004 | Journal Article | IST-REx-ID: 3173

Kolmogorov V, Zabih R. 2004. What energy functions can be minimized via graph cuts? . IEEE Transactions on Pattern Analysis and Machine Intelligence. 26(2), 147–159.

View | DOI

[8]

2004 | Journal Article | IST-REx-ID: 3172

Kolmogorov V, Nguyen T, Nuval A, Spincemaille P, Prince M, Zabih R, Wang Y. 2004. Multiprocessor scheduling implementation of the simultaneous multiple volume SMV navigator method. Magnetic Resonance in Medicine. 52(2), 362–367.

View | DOI

[7]

2004 | Conference Paper | IST-REx-ID: 3177

Zabih R, Kolmogorov V. 2004. Spatially coherent clustering using graph cuts. CVPR: Computer Vision and Pattern Recognition vol. 2, 437–444.

View | DOI

[6]

2004 | Conference Paper | IST-REx-ID: 3179

Rother C, Kolmogorov V, Blake A. 2004. "GrabCut" - Interactive foreground extraction using iterated graph cuts . SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques vol. 23, 309–314.

View | DOI | Download (ext.)

[5]

2003 | Conference Paper | IST-REx-ID: 3171

Kolmogorov V, Zabih R, Gortler S. 2003. Generalized multi camera scene reconstruction using graph cuts. EMMCVPR: Energy Minimization Methods in Computer Vision and Pattern Recognition, LNCS, vol. 2683, 501–516.

View | DOI

[4]

2003 | Conference Paper | IST-REx-ID: 3174

Kim J, Kolmogorov V, Zabih R. 2003. Visual correspondence using energy minimization and mutual information. ICCV: International Conference on Computer Vision vol. 2, 1033–1040.

View | DOI

[3]

2003 | Conference Paper | IST-REx-ID: 3170

Boykov Y, Kolmogorov V. 2003. Computing geodesics and minimal surfaces via graph cuts. ICCV: International Conference on Computer Vision vol. 1, 26–33.

View | DOI

[2]

2002 | Conference Paper | IST-REx-ID: 2927

Kolmogorov V, Zabih R. 2002. Multi-camera scene reconstruction via graph cuts. Proceedings of the 7th European Conference on Computer Vision. ECCV: European Conference on Computer Vision, 65–81.

View | DOI

[1]

2001 | Conference Paper | IST-REx-ID: 3169

Kolmogorov V, Zabih R. 2001. Computing visual correspondence with occlusions using graph cuts. Proceedings of the 8th IEEE International Conference on Computer Vision. ICCV: International Conference on Computer Vision vol. 2, 508–515.

View | DOI

94 Publications

Mark all

[94]

2024 | Journal Article | IST-REx-ID: 10045 |

Dvorak M, Kolmogorov V. 2024. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming., 2109.10203.

[Preprint] View | Files available | DOI | arXiv

[93]

2023 | Conference Paper | IST-REx-ID: 14084 |

[Published Version] View | Files available | DOI | arXiv

[92]

2023 | Conference Paper | IST-REx-ID: 14448 |

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[91]

2022 | Journal Article | IST-REx-ID: 10737 |

Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[90]

2021 | Conference Paper | IST-REx-ID: 10072 |

[Published Version] View | Files available | DOI | arXiv

[89]

2021 | Conference Paper | IST-REx-ID: 10552 |

Kolmogorov V, Pock T. 2021. One-sided Frank-Wolfe algorithms for saddle problems. 38th International Conference on Machine Learning. ICML: International Conference on Machine Learning.

[Preprint] View | Download Preprint (ext.) | arXiv

[88]

2019 | Conference Paper | IST-REx-ID: 6725 |

[Published Version] View | Files available | DOI | arXiv

[87]

2019 | Journal Article | IST-REx-ID: 7412 |

Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[86]

2019 | Conference Paper | IST-REx-ID: 7468 |

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[85]

2019 | Conference Paper | IST-REx-ID: 7639

View | DOI | WoS

[84]

2018 | Conference Paper | IST-REx-ID: 273 |

[Preprint] View | DOI | Download Preprint (ext.) | WoS | arXiv

[83]

2018 | Journal Article | IST-REx-ID: 5975 |

Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.

[82]

2018 | Journal Article | IST-REx-ID: 18 |

Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304.

[Preprint] View | Download Preprint (ext.) | WoS | arXiv

[81]

2018 | Journal Article | IST-REx-ID: 6032 |

Kazda A, Kolmogorov V, Rolinek M. 2018. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 15(2), 22.

[80]

2017 | Journal Article | IST-REx-ID: 644 |

Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued CSPs. SIAM Journal on Computing. 46(3), 1087–1110.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[79]

2017 | Conference Paper | IST-REx-ID: 1192 |

Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.

[Submitted Version] View | Files available | DOI | Download Submitted Version (ext.) | WoS

[78]

2017 | Conference Paper | IST-REx-ID: 274 |

[Published Version] View | Files available | arXiv

[77]

2016 | Conference Paper | IST-REx-ID: 1231 |

[Submitted Version] View | DOI | Download Submitted Version (ext.)

[76]

2016 | Journal Article | IST-REx-ID: 1377 |

Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636.

[Preprint] View | DOI | Download Preprint (ext.)

[75]

2016 | Conference Paper | IST-REx-ID: 1193 |

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[74]

2016 | Journal Article | IST-REx-ID: 1794 |

Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[73]

2015 | Conference Paper | IST-REx-ID: 1636 |

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[72]

2015 | Journal Article | IST-REx-ID: 1841 |

Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37(5), 919–930.

[Preprint] View | DOI | Download Preprint (ext.)

[71]

2015 | Conference Paper | IST-REx-ID: 1859 |

[Preprint] View | DOI | Download Preprint (ext.)

[70]

2015 | Journal Article | IST-REx-ID: 2271 |

Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[69]

2015 | Conference Paper | IST-REx-ID: 1637 |

Kolmogorov V, Krokhin A, Rolinek M. 2015. The complexity of general-valued CSPs. FOCS: Foundations of Computer Science, 56th Annual Symposium on Foundations of Computer Science, , 1246–1258.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[68]

2015 | Conference Paper | IST-REx-ID: 1675 |

Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 9216, 585–605.

[Preprint] View | Files available | DOI | Download Preprint (ext.)

[67]

2014 | Conference Paper | IST-REx-ID: 2275 |

Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.

[Submitted Version] View | Files available | DOI

[66]

2013 | Conference Paper | IST-REx-ID: 2270 |

Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence, 81–87.

View | Download None (ext.) | arXiv

[65]

2013 | Report | IST-REx-ID: 2273 |

Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p.

View | Download (ext.)

[64]

2013 | Conference Paper | IST-REx-ID: 2276 |

Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular functions. ICCV: International Conference on Computer Vision, 2320–2327.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[63]

2013 | Conference Paper | IST-REx-ID: 2518 |

Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965, 625–636.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[62]

2013 | Journal Article | IST-REx-ID: 2828 |

Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal of the ACM. 60(2), 10.

[Preprint] View | DOI | Download Preprint (ext.) | arXiv

[61]

2013 | Conference Paper | IST-REx-ID: 2901 |

View | Download None (ext.)

[60]

2013 | Conference Paper | IST-REx-ID: 2272 |

[Submitted Version] View | Files available | Download Submitted Version (ext.)

[59]

2013 | Report | IST-REx-ID: 2274 |

Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space, IST Austria,p.

[Published Version] View | Files available

[58]

2012 | Conference Paper | IST-REx-ID: 2930 |

Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.

[Preprint] View | DOI | Download Preprint (ext.)

[57]

2012 | Preprint | IST-REx-ID: 2928 |

Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, .

[Preprint] View | Download Preprint (ext.) | arXiv

[56]

2012 | Report | IST-REx-ID: 2929 |

Kolmogorov V. 2012. The power of linear programming for valued CSPs: a constructive characterization, Unknown,p.

View | Download (ext.)

[55]

2012 | Journal Article | IST-REx-ID: 2931

Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(2), 259–271.

View | DOI

[54]

2012 | Journal Article | IST-REx-ID: 3117 |

Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 160(15), 2246–2258.

[Preprint] View | DOI | Download Preprint (ext.)

[53]

2012 | Conference Paper | IST-REx-ID: 3284 |

Kolmogorov V, Živný S. 2012. The complexity of conservative valued CSPs. SODA: Symposium on Discrete Algorithms, 750–759.

View | Download (ext.)

[52]

2012 | Journal Article | IST-REx-ID: 3257 |

Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.

[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv

[51]

2012 | Conference Paper | IST-REx-ID: 3124 |

Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, .

[Submitted Version] View | Files available

[50]

2012 | Technical Report | IST-REx-ID: 5396 |

Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p.

[Published Version] View | Files available | DOI

[49]

2011 | Book Chapter | IST-REx-ID: 2922

Vicente S, Kolmogorov V, Rother C. 2011.Graph-cut Based Image Segmentation with Connectivity Priors. In: Markov Random Fields for Vision and Image Processing. .

View

[48]

2011 | Book Chapter | IST-REx-ID: 2923

Kumar MP, Kolmogorov V, Torr P. 2011.Analyzing Convex Relaxations for MAP Estimation. In: Markov Random Fields for Vision and Image Processing. .

View

[47]

2011 | Book Chapter | IST-REx-ID: 2924

Criminisi A, Cross G, Blake A, Kolmogorov V. 2011.Bilayer Segmentation of Video. In: Markov Random Fields for Vision and Image Processing. .

View

[46]

2011 | Book Chapter | IST-REx-ID: 2925

Rother C, Kolmogorov V, Boykov Y, Blake A. 2011.Interactive Foreground Extraction using graph cut. In: Markov Random Fields for Vision and Image Processing. .

View

[45]

2011 | Book Chapter | IST-REx-ID: 2935

Boykov Y, Kolmogorov V. 2011.Basic graph cut algorithms. In: Markov Random Fields for Vision and Image Processing. , 31–50.

View

[44]

2011 | Conference Paper | IST-REx-ID: 3204

View | DOI | Download (ext.)

[43]

2011 | Conference Paper | IST-REx-ID: 3206

View | DOI | Download (ext.)

[42]

2011 | Conference Paper | IST-REx-ID: 3205

Tarlow D, Batra D, Kohli P, Kolmogorov V. 2011. Dynamic tree block coordinate ascent. ICML: International Conference on Machine Learning, 113–120.

View | Download (ext.)

[41]

2011 | Conference Paper | IST-REx-ID: 3207

Vicente S, Rother C, Kolmogorov V. 2011. Object cosegmentation. CVPR: Computer Vision and Pattern Recognition, 2217–2224.

View | DOI

[40]

2010 | Journal Article | IST-REx-ID: 3202

Kolmogorov V. 2010. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica. 56(4), 394–412.

View | DOI

[39]

2010 | Conference Paper | IST-REx-ID: 3201

Vicente S, Kolmogorov V, Rother C. 2010. Cosegmentation revisited: Models and optimization. ECCV: European Conference on Computer Vision, LNCS, vol. 6312, 465–479.

View | DOI | Download (ext.)

[38]

2010 | Conference Paper | IST-REx-ID: 2934

Kolmogorov V. 2010. Generalized roof duality and bisubmodular functions. Neural Information Processing Systems.

View | Files available

[37]

2009 | Journal Article | IST-REx-ID: 2932

Kolmogorov V. 2009. Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation. 1(1), 43–67.

View | DOI

[36]

2009 | Conference Paper | IST-REx-ID: 3203

Woodford O, Rother C, Kolmogorov V. 2009. A global perspective on MAP inference for low level vision. ICCV: International Conference on Computer Vision, 2319–2326.

View | DOI

[35]

2009 | Journal Article | IST-REx-ID: 3197 |

Kumar MP, Kolmogorov V, Torr P. 2009. An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research. 10, 71–106.

View | Download (ext.)

[34]

2009 | Conference Paper | IST-REx-ID: 3199

Vicente S, Kolmogorov V, Rother C. 2009. Joint optimization of segmentation and appearance models. ICCV: International Conference on Computer Vision, 755–762.

View | DOI | Download (ext.)

[33]

2009 | Journal Article | IST-REx-ID: 3200

Kolmogorov V, Shioura A. 2009. New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization. 6(4), 378–393.

View | DOI

[32]

2008 | Conference Paper | IST-REx-ID: 3194

Kohli P, Shekhovtsov A, Rother C, Kolmogorov V, Torr P. 2008. On partial optimality in multi label MRFs. ICML: International Conference on Machine Learning, 480–487.

View | DOI | Download (ext.)

[31]

2008 | Journal Article | IST-REx-ID: 3196

View | DOI

[30]

2008 | Conference Paper | IST-REx-ID: 3198

Torresani L, Kolmogorov V, Rother C. 2008. Feature correspondence via graph matching: Models and global optimization. ECCV: European Conference on Computer Vision, LNCS, vol. 5303, 596–609.

View | DOI | Download (ext.)

[29]

2008 | Conference Paper | IST-REx-ID: 3195

Vicente S, Kolmogorov V, Rother C. 2008. Graph cut based image segmentation with connectivity priors. CVPR: Computer Vision and Pattern Recognition.

View | DOI | Download (ext.)

[28]

2007 | Conference Paper | IST-REx-ID: 2933

Kumar MP, Kolmogorov V, Torr P. 2007. An Analysis of Convex Relaxations for MAP Estimation. Neural Information Processing Systems.

View

[27]

2007 | Conference Paper | IST-REx-ID: 3192

Rother C, Kolmogorov V, Lempitsky V, Szummer M. 2007. Optimizing binary MRFs via extended roof duality. CVPR: Computer Vision and Pattern Recognition.

View | DOI | Download (ext.)

[26]

2007 | Conference Paper | IST-REx-ID: 3191

Kolmogorov V, Boykov Y, Rother C. 2007. Applications of parametric maxflow in computer vision. ICCV: International Conference on Computer Vision.

View | DOI | Download (ext.)

[25]

2007 | Journal Article | IST-REx-ID: 3193

Kolmogorov V, Rother C. 2007. Minimizing nonsubmodular functions with graph cuts - A review. IEEE Transactions on Pattern Analysis and Machine Intelligence. 29(7), 1274–1279.

View | DOI

[24]

2007 | Journal Article | IST-REx-ID: 3187

Blake A, Criminisi A, Cross G, Kolmogorov V, Rother C. 2007. Fusion of stereo colour and contrast. Springer Tracts in Advanced Robotics. 28, 295–304.

View | DOI | Download (ext.)

[23]

2006 | Book Chapter | IST-REx-ID: 2921

Kolmogorov V, Zabih R. 2006.Graph cut algorithms for binocular stereo with occlusions. In: Handbook of Mathematical Models in Computer Vision. , 423–427.

View | DOI

[22]

2006 | Conference Paper | IST-REx-ID: 3189

Criminisi A, Cross G, Blake A, Kolmogorov V. 2006. Bilayer segmentation of live video. CVPR: Computer Vision and Pattern Recognition vol. 1, 53–60.

View | DOI | Download (ext.)

[21]

2006 | Journal Article | IST-REx-ID: 3190

Kolmogorov V. 2006. Convergent tree reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence. 28(10), 1568–1583.

View | DOI | Download (ext.)

[20]

2006 | Conference Paper | IST-REx-ID: 3188

View | DOI

[19]

2006 | Conference Paper | IST-REx-ID: 3180

View | DOI | Download (ext.)

[18]

2006 | Conference Paper | IST-REx-ID: 3184

Kolmogorov V, Rother C. 2006. Comparison of energy minimization algorithms for highly connected graphs. ECCV: European Conference on Computer Vision, LNCS, vol. 3952 LNCS, 1–15.

View | DOI | Download (ext.)

[17]

2006 | Journal Article | IST-REx-ID: 3185

View | DOI | Download (ext.)

[16]

2006 | Conference Paper | IST-REx-ID: 3186

Boykov Y, Kolmogorov V, Cremers D, Delong A. 2006. An integral solution to surface evolution PDEs via geo cuts. ECCV: European Conference on Computer Vision, LNCS, vol. 3953, 409–422.

View | DOI

[15]

2005 | Conference Paper | IST-REx-ID: 3175

Rother C, Kumar S, Kolmogorov V, Blake A. 2005. Digital tapestry. CVPR: Computer Vision and Pattern Recognition vol. 1, 589–596.

View | DOI | Download (ext.)

[14]

2005 | Conference Paper | IST-REx-ID: 3176

Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation of binocular stereo video. CVPR: Computer Vision and Pattern Recognition, 1186–1186.

View | DOI

[13]

2005 | Conference Paper | IST-REx-ID: 3183

Kolmogorov V, Criminisi A, Blake A, Cross G, Rother C. 2005. Bi-layer segmentation of binocular stereo video. CVPR: Computer Vision and Pattern Recognition vol. 2, 407–414.

View | DOI | Download (ext.)

[12]

2005 | Conference Paper | IST-REx-ID: 3182

Kolmogorov V, Boykov Y. 2005. What metrics can be approximated by geo cuts or global optimization of length area and flux. ICCV: International Conference on Computer Vision vol. 1, 564–571.

View | DOI

[11]

2005 | Conference Paper | IST-REx-ID: 3181

Kolmogorov V, Wainwright M. 2005. On the optimality of tree reweighted max product message passing. UAI: Uncertainty in Artificial Intelligence, 316–323.

View | Download (ext.)

[10]

2004 | Journal Article | IST-REx-ID: 3178

View | DOI

[9]

2004 | Journal Article | IST-REx-ID: 3173

Kolmogorov V, Zabih R. 2004. What energy functions can be minimized via graph cuts? . IEEE Transactions on Pattern Analysis and Machine Intelligence. 26(2), 147–159.

View | DOI

[8]

2004 | Journal Article | IST-REx-ID: 3172

View | DOI

[7]

2004 | Conference Paper | IST-REx-ID: 3177

Zabih R, Kolmogorov V. 2004. Spatially coherent clustering using graph cuts. CVPR: Computer Vision and Pattern Recognition vol. 2, 437–444.

View | DOI

[6]

2004 | Conference Paper | IST-REx-ID: 3179

View | DOI | Download (ext.)

[5]

2003 | Conference Paper | IST-REx-ID: 3171

View | DOI

[4]

2003 | Conference Paper | IST-REx-ID: 3174

Kim J, Kolmogorov V, Zabih R. 2003. Visual correspondence using energy minimization and mutual information. ICCV: International Conference on Computer Vision vol. 2, 1033–1040.

View | DOI

[3]

2003 | Conference Paper | IST-REx-ID: 3170

Boykov Y, Kolmogorov V. 2003. Computing geodesics and minimal surfaces via graph cuts. ICCV: International Conference on Computer Vision vol. 1, 26–33.

View | DOI

[2]

2002 | Conference Paper | IST-REx-ID: 2927

Kolmogorov V, Zabih R. 2002. Multi-camera scene reconstruction via graph cuts. Proceedings of the 7th European Conference on Computer Vision. ECCV: European Conference on Computer Vision, 65–81.

View | DOI

[1]

2001 | Conference Paper | IST-REx-ID: 3169

View | DOI

Vladimir Kolmogorov

94 Publications

Search

Filter Publications

Display / Sort

Export / Embed

94 Publications

Search

Filter Publications

Display / Sort

Export / Embed

Vladimir Kolmogorov

94 Publications

Search

Filter Publications

Display / Sort

Export / Embed

Export Options

94 Publications

Search

Filter Publications

Display / Sort

Export / Embed

Export Options