Fast, Communication and Space Efficient Algorithms for Matching
Event details
| Date | 16.07.2018 |
| Hour | 14:00 › 16:00 |
| Speaker | Jakab Tardos |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
The matching problem is one of the most well-studied combinatorial optimization problems that lies at the core of several fundamental computational primitives. Sublinear algorithms for matching, i.e. algorithms with resource requirements are smaller than the size of the input that they operate on and that are hence adequate for large data analysis, have received significant attention in the literature recently, but many exciting questions remain tantalizingly open. This thesis will focus on designing fast, communication and space efficient algorithms for the matching problem. Specific directions include local algorithms, streaming algorithms and MPC algorithms for matching, as well as lower bounds on space/communication/approximation tradeoffs in these models.
Background papers
Online Bipartite Matching with Amortized O(log2n) Replacements, by Bernstein, A., et al.
Improved Constant-time Approximation Algorithms for Maximum Matchings and Other Optimization Problems, by Yoshida,Y., et al.
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs, by Assadi, S. et al.
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
The matching problem is one of the most well-studied combinatorial optimization problems that lies at the core of several fundamental computational primitives. Sublinear algorithms for matching, i.e. algorithms with resource requirements are smaller than the size of the input that they operate on and that are hence adequate for large data analysis, have received significant attention in the literature recently, but many exciting questions remain tantalizingly open. This thesis will focus on designing fast, communication and space efficient algorithms for the matching problem. Specific directions include local algorithms, streaming algorithms and MPC algorithms for matching, as well as lower bounds on space/communication/approximation tradeoffs in these models.
Background papers
Online Bipartite Matching with Amortized O(log2n) Replacements, by Bernstein, A., et al.
Improved Constant-time Approximation Algorithms for Maximum Matchings and Other Optimization Problems, by Yoshida,Y., et al.
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs, by Assadi, S. et al.
Practical information
- General public
- Free
Contact
- EDIC - [email protected]