The Taub Faculty of Computer Science Events and Talks

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. This answers in the affirmative the value version of a major open question, repeatedly asked in the dynamic graph algorithms literature. Based on an upcoming SODA 2023 best paper, joint with Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak.