Faster Matroid Intersection - Winter 2020 Theory Seminar

Offered By: Paul G. Allen School via YouTube

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!

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.

Syllabus

Winter 2020 Theory Seminar: Faster Matroid Intersection, Sam Wong (MSR)

Taught by

Paul G. Allen School

Related Courses

Matroid Tautological Classes in Types A and B
Fields Institute via YouTube The Geometry of Geometries - Matroid Theory, Old and New
International Mathematical Union via YouTube Linear Matroid Matching in the Oracle Model
Hausdorff Center for Mathematics via YouTube Correlation Inequalities for Schur Functions and Young Tableaux
Institute for Pure & Applied Mathematics (IPAM) via YouTube Toric Matroid Bundles - Algebraic Geometry and Combinatorics
Fields Institute via YouTube