Fast dynamic matching in bipartite lossless expanders

We consider bipartite graphs, and refer to the 2 parts as left and right nodes. Hall's theorem states that if every set $S$ of left nodes has at least $\# S$ neighbors, then the graph has a matching that saturates all the left nodes. We say that a graph has $e$-expansion up to $K$ elements, then if every left set $S$ of size at most $K$ has at least $e\# S$ neighbors. Thus Hall's theorem implies that if a graph has $1$-expansion up to $K$, then every left set of size $K$ has a saturating matching. We consider a dynamic variant of this problem and present a strategy that can be solved in time O(D polylog N) in graphs with N left nodes and left degree at most D. However, the algorithm only works in graphs with (2D/3)-expansion. Such graphs can be computed using with known constructions.
Application 1: 1-bit probes. Such probes are datastructures to store a set $S$ and in which a membership query is answered probabilistically by reading only a single bit from the memory. Our construction reduces the size of the smallest such probes. Moreover, our probes are dynamic: one can add and remove elements in $S$.
Application 2: connector graphs. Such graphs model the connection problem on old telephone networks in which input and output nodes need to be connected using node disjoint paths. Our algorithm gives an almost double exponential speed up of the path finding algorithm in constant depth connectors, and this solves an open question by Feldman, Friedman and Pippenger from 1988.