Talk on 13 November

Skip to first unread message

Nikolay Vereshchagin

Nov 8, 2023, 3:41:00 AM11/8/23
to Kolmogorov seminar on complexity
Dear all,

The next meeting of the Kolmogorov seminar is scheduled on Monday Nov. 13, 18:30 Moscow time (16:30 CET). 

Speaker: Ivan Baburin

Title: Algebraic Matching Algorithms

Abstract: In this presentation we will explore algebraic algorithms for computing perfect matchings in bipartite and general graphs. These algorithms are of great importance for the complexity theory, since they can be easily parallelized, which is not true for “classical” matching algorithms such as Edmond-Blossom. In the talk we present the following two algorithms:
1. The randomised algebraic algorithm for verifying the existence of a perfect matching in bipartite and non-bipartite graphs. The algorithm for bipartite graphs verifies whether the determinant of the adjacency matrix is non-zero, and the general algorithm uses a similar approach for Tutte’s matrices. The existence algorithm can be modified to find a perfect matching, as a consequence we have that finding perfect matchings is in RNC.

2. Derandomized version  of the algorithm for verifying the existence of bipartite perfect matchings running in quasi-polynomial time. Similarly it can be modified to find perfect matchings, which puts the bipartite matching problem in quasi-NC.

Reply all
Reply to author
0 new messages