“We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs.”

Find the paper and full list of authors in the Proceedings of the 55th Annual ACM Symposium on Theory of Computing.