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…