Talk on 13 November
31 views
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.
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
Forward
0 new messages