Ivan Baburin: algebraic tools for graph matchings (13/11/2023)

Kolmogorov seminar on computational and descriptional complexity (founded by Kolmogorov around 1979).
One can easily find out (with small error probability) whether there is a perfect matching in a bipartite graph by replacing edges in its matrix by random numbers and computing the determinant. A bit complicated trick is needed in the non-bibartite case (one considers a skew-symmetric matrix and analyzes more carefully why matchings are not canceled out and why everything cancels out if there are no matchings). One can derandomize this algorithm and get some quasipolynomial parallelizable one (sketch)