YoVDO

Faster Matroid Intersection - Winter 2020 Theory Seminar

Offered By: Paul G. Allen School via YouTube

Tags

Algorithms Courses Computer Science Courses Matroid Theory Courses

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

Information Theory
The Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera