I am interested in problems concerning networks that are challenging either from a mathematical modelling or an algorithmic perspective, or both. My thesis is on the source idenitfication problem, which fortunately qualifies as “both”: the goal is to design efficient algorithms that find the first infected individual (also called patient zero) during an epidemic, based on sparse measurements about who got infected and when.
On the algorithmic side, I have worked on rigorously quantifying the role of adaptivity in source identification: the difference between the problem settings when the measurements are chosen adaptively vs non-adaptively. If the epidemic spreads very aggressively, the theoretical analysis ( and ) becomes equivalent to adaptive and non-adaptive versions of the metric dimension from the combinatorics literature. If the epidemic is less aggressive, then there is more stochasticity in the problem, making the analysis more challenging . Interestingly, in some cases adaptivity only plays a small role , whereas in others, its role is very substantial .
More on the modelling (but still rigorous) side, I have worked on relaxing the assumption in the source identification problem that the underlying contact network is fully known to the algorithm . Also in this direction, we studied the robustness of the metric dimension to single edge changes . Slightly deviating from the algorithmic source identification problem, I have worked on understanding how the location of (multiple) seeds affect the outcome of an epidemic .