en
Please note that IST Research Explorer no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
52 Publications
2019 | Journal Article | IST-REx-ID: 6596 
Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces
Y. Shehu, Results in Mathematics 74 (2019) 138.
View
| Files available
| DOI
Y. Shehu, Results in Mathematics 74 (2019) 138.
2019 | Conference Paper | IST-REx-ID: 6725
Testing the complexity of a valued CSP language
V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.
View
| Files available
| DOI
| arXiv
V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.
2019 | Journal Article | IST-REx-ID: 6593
An efficient projection-type method for monotone variational inequalities in Hilbert spaces
Y. Shehu, X.-H. Li, Q.-L. Dong, Numerical Algorithms (2019) 1–24.
View
| Files available
| DOI
Y. Shehu, X.-H. Li, Q.-L. Dong, Numerical Algorithms (2019) 1–24.
2019 | Journal Article | IST-REx-ID: 6032
Even delta-matroids and the complexity of planar boolean CSPs
A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2019).
View
| DOI
| Download (ext.)
| arXiv
A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2019).
2019 | Journal Article | IST-REx-ID: 7000
Convergence analysis of projection method for variational inequalities
Y. Shehu, O.S. Iyiola, X.-H. Li, Q.-L. Dong, Computational and Applied Mathematics 38 (2019) 161.
View
| DOI
Y. Shehu, O.S. Iyiola, X.-H. Li, Q.-L. Dong, Computational and Applied Mathematics 38 (2019) 161.
2018 | Conference Paper | IST-REx-ID: 193
On the memory hardness of data independent password hashing functions
J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.
View
| DOI
| Download (ext.)
J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.
2018 | Conference Paper | IST-REx-ID: 5978
Exact MAP-inference by confining combinatorial search with LP relaxation
S. Haller, P. Swoboda, B. Savchynskyy, in:, Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI, 2018, pp. 6581–6588.
View
S. Haller, P. Swoboda, B. Savchynskyy, in:, Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI, 2018, pp. 6581–6588.
2018 | Journal Article | IST-REx-ID: 18
Superconcentrators of density 25.3
V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304.
View
| Download (ext.)
| arXiv
V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304.
2018 | Journal Article | IST-REx-ID: 5975
Commutativity in the algorithmic Lovász local lemma
V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.
View
| Files available
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.
2018 | Journal Article | IST-REx-ID: 703
Maximum persistency via iterative relaxed inference with graphical models
A. Shekhovtsov, P. Swoboda, B. Savchynskyy, IEEE Transactions on Pattern Analysis and Machine Intelligence 40 (2018) 1668–1682.
View
| DOI
| Download (ext.)
| arXiv
A. Shekhovtsov, P. Swoboda, B. Savchynskyy, IEEE Transactions on Pattern Analysis and Machine Intelligence 40 (2018) 1668–1682.
2018 | Conference Paper | IST-REx-ID: 273
Efficient optimization for rank-based loss functions
P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.
View
| DOI
| Download (ext.)
| arXiv
P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.
2018 | Research Data | IST-REx-ID: 5573
Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow
H. Alhaija, A. Sellent, D. Kondermann, C. Rother, Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow, IST Austria, 2018.
View
| Files available
| DOI
H. Alhaija, A. Sellent, D. Kondermann, C. Rother, Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow, IST Austria, 2018.
2017 | Conference Paper | IST-REx-ID: 1192
Even delta-matroids and the complexity of planar Boolean CSPs
A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
View
| DOI
| Download (ext.)
A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
2017 | Conference Paper | IST-REx-ID: 915
A message passing algorithm for the minimum cost multicut problem
P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.
View
| Files available
| DOI
P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.
2017 | Journal Article | IST-REx-ID: 644
The complexity of general-valued CSPs
V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017) 1087–1110.
View
| Files available
| DOI
| Download (ext.)
V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017) 1087–1110.
2017 | Conference Paper | IST-REx-ID: 916
A study of lagrangean decompositions and dual ascent solvers for graph matching
P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.
View
| Files available
| DOI
P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.
2017 | Thesis | IST-REx-ID: 992
Complexity of constraint satisfaction
M. Rolinek, Complexity of Constraint Satisfaction, IST Austria, 2017.
View
| Files available
| DOI
M. Rolinek, Complexity of Constraint Satisfaction, IST Austria, 2017.
2017 | Conference Paper | IST-REx-ID: 917
A dual ascent framework for Lagrangean decomposition of combinatorial problems
P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.
View
| Files available
| DOI
P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.
2017 | Conference Paper | IST-REx-ID: 641
Graphical model parameter learning by inverse linear programming
V. Trajkovska, P. Swoboda, F. Åström, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 323–334.
View
| DOI
V. Trajkovska, P. Swoboda, F. Åström, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 323–334.
2017 | Conference Paper | IST-REx-ID: 646
A novel convex relaxation for non binary discrete tomography
J. Kuske, P. Swoboda, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 235–246.
View
| DOI
| Download (ext.)
J. Kuske, P. Swoboda, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 235–246.
2017 | Conference Paper | IST-REx-ID: 274
A faster approximation algorithm for the Gibbs partition function
V. Kolmogorov, in:, Unknown, 2017, pp. 1–17.
View
| Download (ext.)
V. Kolmogorov, in:, Unknown, 2017, pp. 1–17.
2017 | Research Data | IST-REx-ID: 5561
Graph matching problems for annotating C. Elegans
D. Kainmueller, F. Jug, C. Rother, G. Meyers, Graph Matching Problems for Annotating C. Elegans, IST Austria, 2017.
View
| Files available
| DOI
D. Kainmueller, F. Jug, C. Rother, G. Meyers, Graph Matching Problems for Annotating C. Elegans, IST Austria, 2017.
2016 | Conference Paper | IST-REx-ID: 1231
On the complexity of scrypt and proofs of space in the parallel random oracle model
J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.
View
| DOI
| Download (ext.)
J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.
2016 | Journal Article | IST-REx-ID: 1612
CSP for binary conservative relational structures
A. Kazda, Algebra Universalis 75 (2016) 75–84.
View
| DOI
| Download (ext.)
A. Kazda, Algebra Universalis 75 (2016) 75–84.
2016 | Journal Article | IST-REx-ID: 1794
Inference algorithms for pattern-based CRFs on sequence data
V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.
View
| Files available
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.
2016 | Conference Paper | IST-REx-ID: 1193
Commutativity in the algorithmic Lovasz local lemma
V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016.
View
| Files available
| DOI
| Download (ext.)
V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016.
2016 | Journal Article | IST-REx-ID: 1377
Total variation on a tree
V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.
View
| DOI
| Download (ext.)
V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.
2016 | Journal Article | IST-REx-ID: 1353
Deciding absorption
L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016) 1033–1060.
View
| DOI
| Download (ext.)
L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016) 1033–1060.
2016 | Research Data | IST-REx-ID: 5557
Synthetic discrete tomography problems
P. Swoboda, Synthetic Discrete Tomography Problems, IST Austria, 2016.
View
| Files available
| DOI
P. Swoboda, Synthetic Discrete Tomography Problems, IST Austria, 2016.
2015 | Conference Paper | IST-REx-ID: 1636
Effectiveness of structural restrictions for hybrid CSPs
V. Kolmogorov, M. Rolinek, R. Takhanov, 9472 (2015) 566–577.
View
| DOI
| Download (ext.)
V. Kolmogorov, M. Rolinek, R. Takhanov, 9472 (2015) 566–577.
2015 | Journal Article | IST-REx-ID: 1841
A new look at reweighted message passing
V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930.
View
| DOI
| Download (ext.)
V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930.
2015 | Conference Paper | IST-REx-ID: 1675
Proofs of space
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.
View
| Files available
| DOI
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.
2015 | Conference Paper | IST-REx-ID: 1637
The complexity of general-valued CSPs
V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 2015, pp. 1246–1258.
View
| Files available
| DOI
| Download (ext.)
V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 2015, pp. 1246–1258.
2015 | Conference Paper | IST-REx-ID: 1859
A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle
N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.
View
| DOI
| Download (ext.)
N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.
2015 | Journal Article | IST-REx-ID: 2271
The power of linear programming for general-valued CSPs
V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.
View
| Files available
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.
2014 | Working Paper | IST-REx-ID: 7038
Playful Math - An introduction to mathematical games
K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.
View
| Files available
K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.
2014 | Conference Paper | IST-REx-ID: 2275
Partial enumeration and curvature regularization
C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943.
View
| Files available
| DOI
C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943.
2013 | Conference Paper | IST-REx-ID: 2272
Inference algorithms for pattern-based CRFs on sequence data
R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, International Machine Learning Society, 2013, pp. 145–153.
View
| Files available
| Download (ext.)
R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, International Machine Learning Society, 2013, pp. 145–153.
2013 | Conference Paper | IST-REx-ID: 2518
The power of linear programming for finite-valued CSPs: A constructive characterization
V. Kolmogorov, in:, Springer, 2013, pp. 625–636.
View
| Files available
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, in:, Springer, 2013, pp. 625–636.
2013 | Journal Article | IST-REx-ID: 2828
The complexity of conservative valued CSPs
V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).
View
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).
2013 | Report | IST-REx-ID: 2273
Reweighted message passing revisited
V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013.
View
| Download (ext.)
V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013.
2013 | Conference Paper | IST-REx-ID: 2901
Computing the M most probable modes of a graphical model
C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169.
View
| Download (ext.)
C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169.
2013 | Report | IST-REx-ID: 2274
Proofs of Space
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space, IST Austria, 2013.
View
| Files available
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space, IST Austria, 2013.
2013 | Conference Paper | IST-REx-ID: 2270
Optimal Coalition Structures in Cooperative Graph Games
Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press, 2013, pp. 81–87.
View
| Download (ext.)
| arXiv
Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press, 2013, pp. 81–87.
2013 | Conference Paper | IST-REx-ID: 2276
Potts model, parametric maxflow and k-submodular functions
I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.
View
| DOI
| Download (ext.)
| arXiv
I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.
2012 | Journal Article | IST-REx-ID: 2931
A dual decomposition approach to feature correspondence
L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271.
View
| DOI
L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271.
2012 | Journal Article | IST-REx-ID: 3117
Minimizing a sum of submodular functions
V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.
View
| DOI
| Download (ext.)
V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.
2012 | Conference Paper | IST-REx-ID: 3124
Approximating marginals using discrete energy minimization
F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
View
| Files available
F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.
2012 | Technical Report | IST-REx-ID: 5396
Approximating marginals using discrete energy minimization
F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012.
View
| Files available
| DOI
F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012.
2012 | Journal Article | IST-REx-ID: 3257
Generalized roof duality and bisubmodular functions
V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
View
| Files available
| DOI
| Download (ext.)
| arXiv
V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.