Lakshay Saggi

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$-...