Algorithmic Robustness in the Semirandom, Online, and Streaming Settings
Event details
| Date | 21.12.2023 |
| Hour | 13:00 › 15:00 |
| Speaker | Davide Mazzali |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Ola Svensson
Thesis co-advisor: Prof Michael Kapralov
Co-examiner: Prof. Mika Göös
Abstract
We consider algorithmic problems in non conventional settings such as average-case analysis and online and sublinear regimes. In such contexts, we first model 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 problems and models: first, we present an algorithm to solve the semirandom planted clique problem in polynomial time; second, we discuss connections between randomness and the power of adversaries in online problems; third, we show how to encapsulate a streaming algorithm so as to make it resilient to adaptive inputs. Following these themes, we intend to study the capabilities and robustness of algorithms in both well-established and newer, harder models. We conclude the report by discussing how we plan to do so.
Background papers
- Algorithms approaching the threshold for semi-random planted clique (https://dl.acm.org/doi/10.1145/3564246.3585184)
- Adversarially robust streaming algorithms via differential privacy (https://dl.acm.org/doi/10.1145/3556972)
- On the power of randomization in on-line algorithms (https://link.springer.com/article/10.1007/BF01294260)
Exam president: Prof. Friedrich Eisenbrand
Thesis advisor: Prof. Ola Svensson
Thesis co-advisor: Prof Michael Kapralov
Co-examiner: Prof. Mika Göös
Abstract
We consider algorithmic problems in non conventional settings such as average-case analysis and online and sublinear regimes. In such contexts, we first model 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 problems and models: first, we present an algorithm to solve the semirandom planted clique problem in polynomial time; second, we discuss connections between randomness and the power of adversaries in online problems; third, we show how to encapsulate a streaming algorithm so as to make it resilient to adaptive inputs. Following these themes, we intend to study the capabilities and robustness of algorithms in both well-established and newer, harder models. We conclude the report by discussing how we plan to do so.
Background papers
- Algorithms approaching the threshold for semi-random planted clique (https://dl.acm.org/doi/10.1145/3564246.3585184)
- Adversarially robust streaming algorithms via differential privacy (https://dl.acm.org/doi/10.1145/3556972)
- On the power of randomization in on-line algorithms (https://link.springer.com/article/10.1007/BF01294260)
Practical information
- General public
- Free