Fast, Communication and Space Efficient Algorithms for Matching

Thumbnail

Event details

Date 16.07.2018
Hour 14:0016: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.
 

Practical information

  • General public
  • Free

Contact

Tags

EDIC candidacy exam

Share