MATHEMATIK UND INFORMATIK

Kolmogorov Group

Diskrete Optimierung

Wenn wir auf die Straße gehen, beurteilen wir automatisch den Abstand und die Geschwindigkeit der herannahenden Autos. Computer müssen komplexe Berechnungen durchführen, um die Tiefe von Objekten in einem Bild zu schätzen. Ein beliebter Ansatz zur Lösung dieses Problems ist die Verwendung diskreter Optimierungsalgorithmen – dem Forschungsschwerpunkt der Kolmogorov Gruppe.

Die Arbeit von Vladimir Kolmogorovs Gruppe lässt sich in drei Themengebiete unterteilen. Das erste Gebiet ist die Entwicklung effizienter Algorithmen für die Inferenz in graphischen Modellen und kombinatorischen Optimierungsproblemen. Manche der Techniken werden häufig für “Computer Vision” und andere Gebiet eingesetzt, wie entweder der “Boykov-Kolmogorov” Maximum Flow Algorithmus und der “TRW-S” Algorithmus für MAP Inferenz in paarweisen graphischen Modellen. Kolmogorovs “Blossom V” Algorithmus ist die derzeit schnellste Technik für die Berechnung des „minimum cost perfect matching“ in einem Graphen. Der zweite Schwerpunkt der Gruppe liegt auf theoretischen Studien zur Komplexität diskreter Optimierung, insbesondere im Rahmen der “valued constraint satisfaction” Probleme und ihrer Varianten. Zusätzlich arbeitet die Kolmogorov-Gruppe an Anwendungen der diskreten Optimierung für “Computer Vision”, wie etwa in der Bildunterteilung und der Stereorekonstruktion.

Group Leader


On this site:


Team


Laufende Projekte

Inferenz in graphischen Modellen | Kombinatorische Optimierungsprobleme | Theorie der diskreten Optimierung


Publikationen

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

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

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

Shekhovtsov A, Swoboda P, Savchynskyy B. 2018. Maximum persistency via iterative relaxed inference with graphical models. IEEE Transactions on Pattern Analysis and Machine Intelligence. 40(7), 1668–1682. View

Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security 51–65. View

Zu Allen Publikationen

Karriere

seit 2014 Professor, IST Austria
2011 – 2014 Assistant Professor, IST Austria
2005 – 2011 Lecturer, University College London, UK
2003 – 2005 Assistant Researcher, Microsoft Research, Cambridge, UK
2003 PhD, Cornell University, Ithaca, U


Ausgewählte Auszeichnungen

2018 Best paper award honorable mention at IEEE/CVF Conference on Computer Vision and Pattern Recognition
2013 ERC Consolidator Grant
2012 Koenderink Prize at the European Conference on Computer Vision for fundamental contributions to computer vision
2007 Honorable mention, outstanding student paper award (to M. Pawan Kumar) at Neural Information Processing Systems Conference
2006 – 2011 Royal Academy of Engineering/EPSRC Research Fellowship
2005 Best paper honorable mention award at IEEE Conference on Computer Vision and Pattern Recognition
2002 Best paper award at the European Conference on Computer Vision


Ausgewählte Auszeichnungen

Open Kolmogorov’s homepage



Nach Oben