Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time

Expander graphs are known to be robust to edge deletions in the following sense: for any online sequence of edge deletions \(e_1, e_2, \ldots, e_k\) to an \(m\)-edge graph \(G\) that is initially a \(\phi\)-expander, the algorithm can grow a set \(P \subseteq V\) such that at any time \(t\), \(G[V \setminus P]\) is an expander of the same quality as the initial graph \(G\) up to a constant factor and the set \(P\) has volume at most \(O(t / \phi)\). However, currently, there is no algorithm to grow \(P\) with low worst-case recourse that achieves any non-trivial guarantee.