Faster Matroid Intersection - Winter 2020 Theory Seminar

Faster Matroid Intersection - Winter 2020 Theory Seminar

Explore a cutting-edge lecture on faster matroid intersection algorithms presented by Sam Wong from Microsoft Research. Delve into the classic matroid intersection problem, examining both independence and rank oracle settings. Learn about new exact and approximate algorithms that improve upon previous running times, including an O(nr log r) exact algorithm for independence oracles and an O(n√r log n) exact algorithm for rank oracles. Discover how these advancements push the boundaries of computational efficiency in solving matroid intersection problems, with potential applications in various fields of computer science and optimization theory.