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. Springer Nature. https://doi.org/10.1007/s10107-024-02064-5

[Preprint] View | Files available | DOI | arXiv

[93]

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

Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.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. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2023, pp. 11980–11989). Vancouver, Canada: IEEE. https://doi.org/10.1109/CVPR52729.2023.01153

[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. IOS Press. https://doi.org/10.3233/IDA-205623

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

[90]

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

Harris, D. G., Iliopoulos, F., & Kolmogorov, V. (2021). A new notion of commutativity for the algorithmic Lovász Local Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Vol. 207). Virtual: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.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. In 38th International Conference on Machine Learning. Virtual.

[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. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77

[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. SIAM. https://doi.org/10.1137/16m109332x

[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. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2019–June). Long Beach, CA, United States: IEEE. https://doi.org/10.1109/CVPR.2019.01140

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

[85]

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

Rannen-Triki, A., Berman, M., Kolmogorov, V., & Blaschko, M. B. (2019). Function norms for neural networks. In Proceedings of the 2019 International Conference on Computer Vision Workshop. Seoul, South Korea: IEEE. https://doi.org/10.1109/ICCVW.2019.00097

View | DOI | WoS

[84]

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

Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389

[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. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/16m1093306

[82]

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

Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3. Ars Combinatoria. Charles Babbage Research Centre.

[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. ACM. https://doi.org/10.1145/3230649

[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. SIAM. https://doi.org/10.1137/16M1091836

[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 (pp. 307–326). Presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20

[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. In Proceedings of the 31st Conference On Learning Theory (Vol. 75, pp. 228–249). ML Research Press.

[Published Version] View | Files available | arXiv

[77]

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

Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., & Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49896-5_13

[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. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/15M1010257

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

[75]

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

Kolmogorov, V. (2016). Commutativity in the algorithmic Lovasz local lemma. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science (Vol. 2016–December). New Brunswick, NJ, USA : IEEE. https://doi.org/10.1109/FOCS.2016.88

[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. Springer. https://doi.org/10.1007/s00453-015-0017-7

[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. In 26th International Symposium (Vol. 9472, pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48

[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. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465

[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 (pp. 2737–2745). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. https://doi.org/10.1109/CVPR.2015.7298890

[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. SIAM. https://doi.org/10.1137/130945648

[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 (pp. 1246–1258). Presented at the FOCS: Foundations of Computer Science, Berkeley, CA, United States: IEEE. https://doi.org/10.1109/FOCS.2015.80

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

[68]

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

Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2015). Proofs of space. In 35th Annual Cryptology Conference (Vol. 9216, pp. 585–605). Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-48000-7_29

[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 (pp. 2936–2943). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.365

[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 (pp. 81–87). Presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI Press.

View | Download None (ext.) | arXiv

[65]

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

Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria.

View | Download (ext.)

[64]

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

Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288

[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 (Vol. 7965, pp. 625–636). Presented at the ICALP: Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53

[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. ACM. https://doi.org/10.1145/2450142.2450146

[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 (Vol. 31, pp. 161–169). Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR.

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. In ICML’13 Proceedings of the 30th International Conference on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.

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

[59]

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

Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs of Space. IST Austria.

[Published Version] View | Files available

[58]

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

Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions (Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40

[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. 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.

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. IEEE. https://doi.org/10.1109/TPAMI.2012.105

View | DOI

[54]

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

Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025

[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 (pp. 750–759). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.

View | Download (ext.)

[52]

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

Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026

[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. Presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland: ICML.

[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. https://doi.org/10.15479/AT:IST-2012-0003

[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 A. Blake, P. Kohli, & C. Rother (Eds.), Markov Random Fields for Vision and Image Processing. Massachusetts Institute of Technology Press.

View

[48]

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

Kumar, M. P., Kolmogorov, V., & Torr, P. (2011). Analyzing Convex Relaxations for MAP Estimation. In A. Blake, P. Kohli, & C. Rother (Eds.), Markov Random Fields for Vision and Image Processing. Massachusetts Institute of Technology Press.

View

[47]

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

Criminisi, A., Cross, G., Blake, A., & Kolmogorov, V. (2011). Bilayer Segmentation of Video. In A. Blake, P. Kohli, & C. Rother (Eds.), Markov Random Fields for Vision and Image Processing. Massachusetts Institute of Technology Press.

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 A. Blake, P. Kohli, & C. Rother (Eds.), Markov Random Fields for Vision and Image Processing. Massachusetts Institute of Technology Press.

View

[45]

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

Boykov, Y., & Kolmogorov, V. (2011). Basic graph cut algorithms. In A. Blake, P. Kohli, & C. Rother (Eds.), Markov Random Fields for Vision and Image Processing (pp. 31–50). Massachusetts Institute of Technology Press.

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 (Vol. 6907, pp. 400–411). Presented at the MFCS: Mathematical Foundations of Computer Science, Springer. https://doi.org/10.1007/978-3-642-22993-0_37

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 (pp. 1889–1896). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2011.5995361

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 (pp. 113–120). Presented at the ICML: International Conference on Machine Learning, Omnipress.

View | Download (ext.)

[41]

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

Vicente, S., Rother, C., & Kolmogorov, V. (2011). Object cosegmentation (pp. 2217–2224). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2011.5995530

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. Springer. https://doi.org/10.1007/s00453-008-9177-z

View | DOI

[39]

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

Vicente, S., Kolmogorov, V., & Rother, C. (2010). Cosegmentation revisited: Models and optimization (Vol. 6312, pp. 465–479). Presented at the ECCV: European Conference on Computer Vision, Springer. https://doi.org/10.1007/978-3-642-15552-9_34

View | DOI | Download (ext.)

[38]

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

Kolmogorov, V. (2010). Generalized roof duality and bisubmodular functions. Presented at the Neural Information Processing Systems, 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. Springer. https://doi.org/10.1007/s12532-009-0002-8

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 (pp. 2319–2326). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2009.5459434

View | DOI

[35]

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

Kumar, M. P., Kolmogorov, V., & Torr, P. (2009). An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research. Microtome Publishing.

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 (pp. 755–762). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2009.5459287

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. Elsevier. https://doi.org/10.1016/j.disopt.2009.04.006

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 (pp. 480–487). Presented at the ICML: International Conference on Machine Learning, Omnipress. https://doi.org/10.1145/1390156.1390217

View | DOI | Download (ext.)

[31]

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

Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., … 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. IEEE. https://doi.org/10.1109/TPAMI.2007.70844

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 (Vol. 5303, pp. 596–609). Presented at the ECCV: European Conference on Computer Vision, Springer. https://doi.org/10.1007/978-3-540-88688-4_44

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. Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2008.4587440

View | DOI | Download (ext.)

[28]

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

Kumar, M. P., Kolmogorov, V., & Torr, P. (2007). An Analysis of Convex Relaxations for MAP Estimation. Presented at the Neural Information Processing Systems, 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. Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2007.383203

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. Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2007.4408910

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. IEEE. https://doi.org/10.1109/TPAMI.2007.1031

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. Springer. https://doi.org/10.1007/978-3-540-48113-3_27

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 (pp. 423–427). Springer. https://doi.org/10.1007/0-387-28831-7_26

View | DOI

[22]

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

Criminisi, A., Cross, G., Blake, A., & Kolmogorov, V. (2006). Bilayer segmentation of live video (Vol. 1, pp. 53–60). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2006.69

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. IEEE. https://doi.org/10.1109/TPAMI.2006.200

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 (pp. 993–1000). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2006.91

View | DOI

[19]

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

Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., … Rother, C. (2006). A comparative study of energy minimization methods for Markov random fields (Vol. 3952, pp. 16–29). Presented at the ECCV: European Conference on Computer Vision, Springer. https://doi.org/10.1007/11744047_2

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 (Vol. 3952 LNCS, pp. 1–15). Presented at the ECCV: European Conference on Computer Vision, Springer. https://doi.org/10.1007/11744047_1

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. IEEE. https://doi.org/10.1109/TPAMI.2006.193

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 (Vol. 3953, pp. 409–422). Presented at the ECCV: European Conference on Computer Vision, Springer. https://doi.org/10.1007/11744078_32

View | DOI

[15]

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

Rother, C., Kumar, S., Kolmogorov, V., & Blake, A. (2005). Digital tapestry (Vol. 1, pp. 589–596). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2005.130

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 (pp. 1186–1186). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2005.90

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 (Vol. 2, pp. 407–414). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2005.91

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 (Vol. 1, pp. 564–571). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2005.252

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 (pp. 316–323). Presented at the UAI: Uncertainty in Artificial Intelligence, AUAI Press.

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. IEEE. https://doi.org/10.1109/TPAMI.2004.60

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. IEEE. https://doi.org/10.1109/TPAMI.2004.1262177

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. Wiley-Blackwell. https://doi.org/10.1002/mrm.20162

View | DOI

[7]

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

Zabih, R., & Kolmogorov, V. (2004). Spatially coherent clustering using graph cuts (Vol. 2, pp. 437–444). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. https://doi.org/10.1109/CVPR.2004.1315196

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 (Vol. 23, pp. 309–314). Presented at the SIGGRAPH: Special Interest Group on Computer Graphics and Interactive Techniques, ACM. https://doi.org/10.1145/1015706.1015720

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 (Vol. 2683, pp. 501–516). Presented at the EMMCVPR: Energy Minimization Methods in Computer Vision and Pattern Recognition, Springer. https://doi.org/10.1007/978-3-540-45063-4_32

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 (Vol. 2, pp. 1033–1040). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2003.1238463

View | DOI

[3]

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

Boykov, Y., & Kolmogorov, V. (2003). Computing geodesics and minimal surfaces via graph cuts (Vol. 1, pp. 26–33). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2003.1238310

View | DOI

[2]

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

Kolmogorov, V., & Zabih, R. (2002). Multi-camera scene reconstruction via graph cuts. In Proceedings of the 7th European Conference on Computer Vision (pp. 65–81). Copenhagen, Denmark: Springer. https://doi.org/10.1007/3-540-47977-5_5

View | DOI

[1]

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

Kolmogorov, V., & Zabih, R. (2001). Computing visual correspondence with occlusions using graph cuts. In Proceedings of the 8th IEEE International Conference on Computer Vision (Vol. 2, pp. 508–515). Vancouver, Canada: IEEE. https://doi.org/10.1109/ICCV.2001.937668

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. Springer Nature. https://doi.org/10.1007/s10107-024-02064-5

[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. IOS Press. https://doi.org/10.3233/IDA-205623

[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. In 38th International Conference on Machine Learning. Virtual.

[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. SIAM. https://doi.org/10.1137/16m109332x

[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. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/16m1093306

[82]

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

Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3. Ars Combinatoria. Charles Babbage Research Centre.

[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. ACM. https://doi.org/10.1145/3230649

[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. SIAM. https://doi.org/10.1137/16M1091836

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

[79]

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

[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. In Proceedings of the 31st Conference On Learning Theory (Vol. 75, pp. 228–249). ML Research Press.

[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. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/15M1010257

[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. Springer. https://doi.org/10.1007/s00453-015-0017-7

[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. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465

[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. SIAM. https://doi.org/10.1137/130945648

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

[69]

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

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

[68]

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

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

[67]

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

[Submitted Version] View | Files available | DOI

[66]

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

View | Download None (ext.) | arXiv

[65]

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

Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria.

View | Download (ext.)

[64]

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

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

[63]

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

[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. ACM. https://doi.org/10.1145/2450142.2450146

[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, K. Z. (2013). Proofs of Space. IST Austria.

[Published Version] View | Files available

[58]

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

[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. 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.

View | Download (ext.)

[55]

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

View | DOI

[54]

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

Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025

[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 (pp. 750–759). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.

View | Download (ext.)

[52]

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

Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026

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

[51]

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

[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. https://doi.org/10.15479/AT:IST-2012-0003

[Published Version] View | Files available | DOI

[49]

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

View

[48]

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

View

[47]

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

View

[46]

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

View

[45]

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

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 (pp. 113–120). Presented at the ICML: International Conference on Machine Learning, Omnipress.

View | Download (ext.)

[41]

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

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. Springer. https://doi.org/10.1007/s00453-008-9177-z

View | DOI

[39]

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

View | DOI | Download (ext.)

[38]

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

Kolmogorov, V. (2010). Generalized roof duality and bisubmodular functions. Presented at the Neural Information Processing Systems, 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. Springer. https://doi.org/10.1007/s12532-009-0002-8

View | DOI

[36]

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

View | DOI

[35]

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

Kumar, M. P., Kolmogorov, V., & Torr, P. (2009). An analysis of convex relaxations for MAP estimation of discrete MRFs. Journal of Machine Learning Research. Microtome Publishing.

View | Download (ext.)

[34]

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

View | DOI | Download (ext.)

[33]

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

View | DOI

[32]

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

View | DOI | Download (ext.)

[31]

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

View | DOI

[30]

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

View | DOI | Download (ext.)

[29]

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

View | DOI | Download (ext.)

[28]

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

Kumar, M. P., Kolmogorov, V., & Torr, P. (2007). An Analysis of Convex Relaxations for MAP Estimation. Presented at the Neural Information Processing Systems, Neural Information Processing Systems.

View

[27]

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

View | DOI | Download (ext.)

[26]

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

View | DOI | Download (ext.)

[25]

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

View | DOI

[24]

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

View | DOI | Download (ext.)

[23]

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

View | DOI

[22]

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

View | DOI | Download (ext.)

[21]

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

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

View | DOI | Download (ext.)

[17]

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

View | DOI | Download (ext.)

[16]

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

View | DOI

[15]

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

View | DOI | Download (ext.)

[14]

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

View | DOI

[13]

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

View | DOI | Download (ext.)

[12]

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

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 (pp. 316–323). Presented at the UAI: Uncertainty in Artificial Intelligence, AUAI Press.

View | Download (ext.)

[10]

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

View | DOI

[9]

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

View | DOI

[8]

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

View | DOI

[7]

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

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

View | DOI

[3]

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

View | DOI

[2]

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

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