LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Breaking the √n Barrier: New Parallel Algorithms for Finding a Matroid Basis
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Breaking the √n Barrier: New Parallel Algorithms for Finding a Matroid Basis

66 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Aaron (Louie) Putterman of Harvard University presents new results on a parallel computation problem open since Karp, Upfal, and Wigderson's work over 40 years ago: how many adaptive rounds of independence queries are needed to find a basis of a matroid. He introduces an algorithm that finds a basis in O(n^3/7) rounds with high probability, improving on the long-standing O(sqrt n) bound, and shows that for partition matroids the optimal round complexity is O(n^1/3), settling that special case. The talk explains the new matroid decomposition technique behind these results and its further applications to parallel algorithms for matroid intersection. Delivered as an Institute for Advanced Study Computer Science/Discrete Mathematics Seminar, the talk presents joint work with Sanjeev Khanna and Junkai Song of the University of Pennsylvania, aimed at an audience already familiar with matroid theory and parallel complexity.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 6 m
Compared with MathematicsShorter than 69%
Source channelInstitute for Advanced Study (YouTube)