Fast online matching in lossless expanders and applications

We show that in bipartite graphs a large expansion factor implies very fast dynamic matching. Coupled with known constructions of lossless expanders, this gives a solution to the main open problem in a classical paper of Feldman, Friedman, and Pippenger (SIAM J. Discret. Math., 1(2):158-173, 1988). Application 1: storing sets. We construct 1-query bitprobes that store a dynamic subset $S$ of an $N$ element set. A membership query reads a single bit, whose location is computed in time poly$(\log N, \log (1/\varepsilon))$ time and is correct with probability $1-\epsilon$. Elements can be inserted and removed efficiently in time quasipoly$(\log N)$. Previous constructions were static: membership queries have the same parameters, but each update requires the recomputation of the whole data structure, which takes time poly$(\# S \log N)$. Moreover, the size of our scheme is smaller than the best known constructions for static sets. Application 2: switching networks. We construct explicit constant depth $N$-connectors of essentially minimum size in which the path-finding algorithm runs in time quasipoly$(\log N)$. In the non-explicit construction in Feldman, Friedman and Pippenger (SIAM J. Discret. Math., 1(2):158-173, 1988). and in the explicit construction of Wigderson and Zuckerman (Combinatorica, 19(1):125-138, 1999) the runtime is exponential in $N$.