Slobodan Mitrović


I am Postdoctoral Fellow at Theory of Computation group, CSAIL, at MIT and I am fortunate to have Ronitt Rubinfeld as my host.

I received my PhD and Master's degree from the Computer Science department at EPFL. After finishing my PhD and prior to coming to MIT, I visited Mohsen Ghaffari at ETH.


Broadly speaking, I am interested in algorithmic graph theory and combinatorial approach to optimization. My research focuses on designing efficient algorithms in the context of memory-constrained computation. In particular, my work is mainly concerned with problems stemming from parallel and streaming setting.


e-mail: slobo at mit.edu

Publications

  • Weighted Matchings via Unweighted Augmentations

Buddhima Gamlath, Sagar Kale, Slobodan Mitrović, Ola Svensson

ACM Symposium on Principles of Distributed Computing, PODC 2019. arXiv

  • Adversarially Robust Submodular Maximization under Knapsack Constraints

Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev, Samson Zhou

25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2019. arXiv

  • Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams

Ashkan Norouzi-Fard, Jakub M Tarnawski, Slobodan Mitrović, Amir Zandieh, Aida Mousavifar, Ola Svensson

35th International Conference on Machine Learning, ICML 2018. link

  • Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, Ronitt Rubinfeld

ACM Symposium on Principles of Distributed Computing, PODC 2018. arXiv

  • Round Compression for Parallel Matching Algorithms

Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski

50th ACM Symposium on Theory of Computing, STOC 2018. Invited to the special issue. arXiv video

  • A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians

Aleksander Mądry, Slobodan Mitrović, Ludwig Schmidt

The 21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018. arXiv

  • Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub M Tarnawski, Volkan Cevher

31th Conference on Neural Information Processing Systems, NIPS 2017. arXiv

  • Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Ilija Bogunovic, Slobodan Mitrović, Jonathan Scarlett, Volkan Cevher

34th International Conference on Machine Learning, ICML 2017. arXiv

  • On the Resiliency of Randomized Routing Against Multiple Edge Failures

Marco Chiesa, Andrei Gurtov, Aleksander Mądry, Slobodan Mitrović, Ilya Nikolaevskiy, Michael Schapira, Scott Shenker

43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. link

  • The Quest for Resilient (Static) Forwarding Tables

Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrović, Aurojit Panda, Andrei Gurtov, Aleksander Mądry, Michael Schapira, Scott Shenker

35th IEEE International Conference on Computer Communications, INFOCOM 2016. link

  • On the Resiliency of Static Forwarding Tables

Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrović, Andrei Gurtov, Aleksander Mądry, Michael Schapira, Scott Shenker

IEEE/ACM Transactions on Networking (Volume: 25, Issue: 2), ToN 2016. link

  • Homometric sets in diameter-two and outerplanar graphs

Slobodan Mitrović

17th IEEE Mediterranean Electrotechnical Conference, MELECON 2014. link

IEEE R8 Best Student Paper Award

  • Homometric sets in trees

Radoslav Fulek, Slobodan Mitrović

European Journal of Combinatorics, 2014. arXiv


Manuscripts

  • Identifying Maximal Non-Redundant Integer Cone Generators

Slobodan Mitrović, Ruzica Piskac, Viktor Kuncak pdf


Theses

  • When Stuck, Flip a Coin: New Algorithms for Large-Scale Tasks

PhD Thesis, EPFL, 2018. pdf

  • Metric problems on graphs

Master's Thesis, EPFL, 2013. pdf