BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Fast\, Communication and Space Efficient Algorithms for Matching
DTSTART:20180716T140000
DTEND:20180716T160000
DTSTAMP:20260407T034458Z
UID:68e52abc6e38e4f1efbbcf23858da6e7c428a864a90eea54a1ade80e
CATEGORIES:Conferences - Seminars
DESCRIPTION:Jakab Tardos\nEDIC candidacy exam\nExam president: Prof. Fried
 rich Eisenbrand\nThesis advisor: Prof. Michael Kapralov\nCo-examiner: Prof
 . Ola Svensson\n\nAbstract\nThe matching problem is one of the most well-s
 tudied combinatorial optimization problems that lies at the core of severa
 l 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\, stre
 aming algorithms and MPC algorithms for matching\, as well as lower bounds
  on space/communication/approximation tradeoffs in these models.\n\nBackgr
 ound papers\nOnline Bipartite Matching with Amortized O(log2n) Replacement
 s\, by Bernstein\, A.\, et al.\nImproved Constant-time Approximation Algor
 ithms for Maximum Matchings and Other Optimization Problems\, by Yoshida\
 ,Y.\, et al.\nCoresets Meet EDCS: Algorithms for Matching and Vertex Cover
  on Massive Graphs\, by Assadi\, S. et al.\n 
LOCATION:BC 129 https://plan.epfl.ch/?room==BC%20129
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR