Preprint
Sep 2026
Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications
A unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids is presented, yielding the first oracles supporting an arbitrary number of updates across all of these problems (all constructions randomized Monte-Carlo).
Keerti Choudhary, Amit Kumar, Lakshay Saggi
· 0 citations