We present a deterministic (1+ ε)-approximate maximum matching algorithm in poly (1/ε)
passes in the semi-streaming model, solving the long-standing open problem of breaking …

We study fully dynamic algorithms for maximum matching. This is a well-studied problem,
known to admit several update-time/approximation trade-offs. For instance, it is known how …

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 …

Sublinear time algorithms for approximating maximum matching size have long been
studied. Much of the progress over the last two decades on this problem has been on the …

We study sublinear time algorithms for estimating the size of maximum matching. After a
long line of research, the problem was finally settled by Behnezhad ‍ [FOCS'22], in the …

We prove a lower bound on the space complexity of two-pass semi-streaming algorithms
that approximate the maximum matching problem. The lower bound is parameterized by the …

We provide Õ (∊–1)-pass semi-streaming algorithms for computing (1–∊)-approximate
maximum cardinality matchings in bipartite graphs. Our most efficient methods are …

Motivated by applications to process massive datasets, we study streaming algorithms for
pure exploration in Stochastic Multi-Armed Bandits (MABs). This problem was first …

Given a graph $ G $, an edge-coloring is an assignment of colors to edges of $ G $ such that
any two edges sharing an endpoint receive different colors. By Vizing's celebrated theorem …

We present deterministic algorithms for maintaining a $(3/2+\epsilon) $ and $(2+\epsilon) $-
approximate maximum matching in a fully dynamic graph with worst-case update times $\hat …