BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Random Instances and Randomness in Algorithms
DTSTART:20190703T130000
DTEND:20190703T150000
DTSTAMP:20260501T144428Z
UID:b10769cf939752ffc0b11700e4c5544732ce7349d53b0b315c46edb4
CATEGORIES:Conferences - Seminars
DESCRIPTION:Xinrui Jia\nEDIC candidacy exam\nExam president: Prof. Michael
  Kapralov\nThesis advisor: Prof. Ola Svensson\nCo-examiner: Prof. Friedric
 h Eisenbrand\n\nAbstract\nThere are two main ways that randomness is used 
 in algorithms. The first is randomness in the input\, and the other is acc
 ess to random bits in algorithm design. These aspects are connected and th
 e goal is to design better algorithms with provable guarantees. We study a
  framework in maximizing submodular functions subject to independence cons
 traints\, derandomization of a parallel algorithm\, and a lower bound for 
 the complexity of the perfect matching polytope. The objective is to apply
  similar techniques to investigate random algorithms.\n\nBackground papers
 \nBipartite Perfect Matching is in quasi-NC\, by Fenner\, S.\, et al. arxi
 v.org 2016.\nThe matching polytope has exponential extensioncomplexity\, b
 y Rothvoss\, T. arxiv.org 2017.\nSubmodular Function Maximization via the 
 Multilinear Relaxationand Contention Resolution Schemes\,by Chekuri\, C.\,
  et al. arxiv.org 2014.\n 
LOCATION:BC 229 https://plan.epfl.ch/?room==BC%20229
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR