2 papers
cs.DS2022
Local treewidth of random and noisy graphs with applications to stopping contagion in networks
Hermish Mehta, Daniel Reichman
We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all -vertex subgraphs of an -vertex graph. When is not too large, we give nearl…
cs.DS2018
A New Algorithm for the Robust Semi-random Independent Set Problem
Theo McKenzie, Hermish Mehta, Luca Trevisan
In this paper, we study a general semi-random version of the planted independent set problem in a model initially proposed by Feige and Kilian, which has a large proportion of adve…