Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form

Adam Karczmarz, Piotr Sankowski

Algebraic techniques have had an important impact on graph algorithms so far. Porting them, e.g., the matrix inverse, into the dynamic regime improved best-known bounds for various…