The subtitle of this course was supposed to be the original title. Unfortunately, it has to offered under the title “New Trends in IT”, which is not related to the course.
The course revolves around the problem of Perfect Matchings in graphs. The study of Perfect Matchings in computer science has been quite extensive and influential. It has been studied in a variety of different algorithmic models — sequential, parallel, bounded-space, randomized, online, approximation, counting etc. It has generated many ingenious ideas which also apply to much more general settings, e.g., the primal-dual LP algorithms, the Isolation Lemma. In fact, the notion of polynomial time as a measure of efficient computation arose in the context of perfect matchings. The aim of this course is to study perfect matchings in these various paradigms, pick up different ideas it inspires and to get introduced to open research problems around it.
Perfect matching and characterizing its existence, Linear programming formulations, Greedy algorithm, Polynomial time algorithms, Randomized Parallel algorithms, Exact matching, Primal-dual LP algorithms, Extended formulations for linear programs, Matrix Scaling algorithm, Approximating the Permanent, Online Algorithms, #P-hardness of counting, Efficient counting in planar graphs and minor-free graphs, Parallel algorithms in planar graphs, Derandomization, Approximate counting of bipartite matchings.