tgoop.com/UTCS_SA/528
Last Update:
How to Count with Polynomials?
میلاد برزگر، محقق پسادکتری پژوهشگاه دانشهای بنیادی (IPM)
Counting perfect matchings in bipartite graphs is a fundamental problem in theoretical computer science (TCS) and combinatorial optimization. In TCS, the goal is to find (approximation) algorithms, and in combinatorics, the aim is to bound the number of perfect matchings in a specific class of graphs. In this talk, I will focus on regular bipartite graphs and discuss (1) deterministic approximation algorithms for the number of perfect matchings in these graphs, and (2) the Schrijver-Valiant conjecture, which determines the minimum number of perfect matchings in d-regular bipartite graphs of a given size. This conjecture was proposed by Schrijver and Valiant in 1980 and resolved by Schrijver in 1998. Schrijver’s proof is considered to be one of the most complicated and least understood arguments in graph theory!
One of the high points of matching counting (!) is Leonid Gurvits’ ingenious work in the early 2000s. He came up with a neat elementary argument for both (1) and (2). In fact, he created a machinery known as the “capacity method” that has since found many more applications. Gurvits’ approach is based on the “geometry of polynomials,” which is the study of the analytic properties of (multivariate) polynomials with complex or real coefficients. This work kick started a new trend known as the “polynomial paradigm.” Over the last two decades, people have used tools from the geometry of polynomials to solve a number of notorious open problems in mathematics and TCS. In this talk, I will go through Gurvits’ argument and the consequences of his ideas. In particular, I will try to highlight the importance of the notion of “capacity” and its applications in counting and optimization.
پیشنیاز های علمی: آشنایی با جبرخطی و احتمال
