Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis - Aaron Putterman скачать в хорошем качестве

Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis - Aaron Putterman

Computer Science/Discrete Mathematics Seminar I 11:00am|Simonyi Hall 101 and Remote Access Topic: Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis Speaker: Aaron (Louie) Putterman Affiliation: Harvard University Date: November 17, 2025 Over 40 years ago, Karp, Upfal, and Wigderson posed a central open question in parallel computation: how many adaptive rounds are needed to find a basis of a matroid using only independence queries? Their pioneering work gave an upper bound of O(n‾√) rounds and a lower bound of roughly Ω(n1/3) rounds---bounds that have stood unchanged ever since. In this talk, I will present recent progress on this classic problem. We give a new parallel algorithm that, with high probability, finds a matroid basis in O(n3/7) rounds, breaking the long-standing O(n‾√) barrier. For the important special case of partition matroids, we obtain an optimal O(n1/3) -round algorithm, settling their complexity. Our approach introduces a new matroid decomposition technique which may be of independent interest, and also yields faster parallel algorithms for the classic matroid intersection problem, among others. Based on joint work with Sanjeev Khanna and Junkai Song (Penn).