BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Algorithmic Robustness in the Semirandom\, Online\, and Streaming 
 Settings
DTSTART:20231221T130000
DTEND:20231221T150000
DTSTAMP:20260407T021011Z
UID:74082c82758bf234ea7376b310e4329d46ab15d9ab11c442bb2541a7
CATEGORIES:Conferences - Seminars
DESCRIPTION:Davide Mazzali\nEDIC candidacy exam\nExam president: Prof. Fri
 edrich Eisenbrand\nThesis advisor: Prof. Ola Svensson\nThesis co-advisor: 
 Prof Michael Kapralov\nCo-examiner: Prof. Mika Göös\n\nAbstract\nWe cons
 ider algorithmic problems in non conventional settings such as average-cas
 e analysis and online and sublinear regimes. In such contexts\, we first m
 odel the nature of the input and how an algorithm shall interact with it. 
 One can think of an algorithm as robust to a model if it achieves certain 
 desired guarantees against it. In this report\, we summarize three papers 
 each showing the limitation and capabilities of algorithms for diverse pro
 blems and models: first\, we present an algorithm to solve the semirandom 
 planted clique problem in polynomial time\; second\, we discuss connection
 s between randomness and the power of adversaries in online problems\; thi
 rd\, we show how to encapsulate a streaming algorithm so as to make it res
 ilient to adaptive inputs. Following these themes\, we intend to study the
  capabilities and robustness of algorithms in both well-established and ne
 wer\, harder models.  We conclude the report by discussing how we plan to
  do so.\n\nBackground papers\n- Algorithms approaching the threshold for s
 emi-random planted clique (https://dl.acm.org/doi/10.1145/3564246.3585184)
 \n- Adversarially robust streaming algorithms via differential privacy (ht
 tps://dl.acm.org/doi/10.1145/3556972)\n- On the power of randomization in 
 on-line algorithms (https://link.springer.com/article/10.1007/BF01294260)\
 n 
LOCATION:BC 010 https://plan.epfl.ch/?room==BC%20010
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR