Marko Mitrovic

Ph.D. Student
Department of Computer Science
Yale University


Research Interests

  • Machine Learning
  • Graph Algorithms
  • Operations Research




Yale Institute for Network Science: August 2015 – Present

Under the supervision of Professor Amin Karbasi.
Funded by Yale University Fellowship.

  • Differentially Private Submodular Maximization (ICML 2017):
    [pdf][full version][poster]


    Submodularity and differential privacy are both burgeoning fields that have been attracting a lot of interest lately, particularly in a machine learning context. Submodular functions are essentially the class of all functions that exhibit diminishing returns. Differential privacy, on the other hand, aims to provably maintain privacy by guaranteeing that any one individual’s data does not significantly influence the outcome of an algorithm. We present a general framework for privately maximizing submodular functions under a variety of constraints.

  • Submodularity on Hypergraphs: From Sets to Sequences (paper under review):

    In many problems, it makes more sense to model solutions as sequences rather than sets. For example, if a recommender system suggests that I watch The Lord of the Rings, the order of movies it recommends is very important. Although there have been many nice results in the field of submodularity, they are generally limited to the context of sets. We aim to establish new algorithms and theoretical guarantees for submodular functions when the desired output is a sequence rather than a set.

  • Source Identification of Contagions in Networks

    Over the course of the last decade, one of the most studied problems in the field of network science has been the prediction and modeling of the spread of a contagion through a network. However, the inverse problem where the resulting spread is known, but the source is unknown, has received considerably less attention. Given a graph and a subset of “infected” vertices, we want to create an algorithm that accurately and efficiently identifies the most likely source of the infection.


Social Network Analysis of Human Genome Project: September 2014 – May 2015

Under the supervision of Professor Martin Ester.

Our goal was to determine both the short-term and long-term effects that the Human Genome Project has had on the co-authorship network of researchers in the field of genomics. One of our main challenges was to create methods that would isolate the effects of the Human Genome Project from the side-effects of other major events and changes from the same time period. For example, consider the rapid rise in the prevalence of the internet as a means of academic communication in the 1990’s. Even if we find an increase in the connectivity of the co-authorship network, how will we know that the cause was the Human Genome Project and not something else?


SFU Algorithms and Complexity Lab: April 2014 – May 2015

Under the supervision of Professor Binay Bhattacharya
Funded by the Natural Sciences and Engineering Research Council of Canada (NSERC) – Undergraduate Student Research Award (USRA)

  • Adaptive Binmedian: an algorithm for efficiently finding the kth smallest element in a large, read-only dataset, using as few passes through the data as possible.
  • Part Placement Problem in computational geometry. [very brief overview]


Hilbert Bases in Graphs and Matroids: April 2013 – August 2013

Under the supervision of Professor Luis Goddyn.
Funded by the Natural Sciences and Engineering Research Council of Canada (NSERC) – Undergraduate Student Research Award (USRA).

Poster Presentation at the 2013 SFU Symposium on Mathematics and Computation.