Deterministic $(1+varepsilon)$-Approximate Maximum Matching with $mathsf{poly}(1/varepsilon)$ Passes in the Semi-Streaming Model

We present a deterministic $(1+varepsilon)$-approximate maximum matching algorithm in $mathsf{poly}(1/varepsilon)$ passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on $1/varepsilon$. Our algorithm exponentially improves on the well-known randomized $(1/varepsilon)^{O(1/varepsilon)}$-pass algorithm from the seminal work by McGregor [APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity [FSTTCS18], as well as the deterministic $log n cdot mathsf{poly}(1/varepsilon)$-pass algorithm by Ahn and Guha [ICALP11].