13 października 2022 13:15
[Seminarium ZOK] Spyros Angelopoulos: Online Computation with Untrusted and Noisy Advice
Abstract: In the last decade, a large number of online problems have
been studied under the advice complexity model, in which the algorithm
is enhanced by some error-free, and often overly powerful information
concerning its input. In this presentation I will survey some recent
contributions towards more realistic models that consider advice as
information elicited by imperfect binary queries. In particular I will
discuss the untrusted advice model, in which the focus is on Pareto
tradeoffs between the consistency and the robustness of the algorithm,
and the noisy advice model, in which the performance is evaluated in
terms of the advice error. The presentation will highlight new
theoretical results, both from the point of view of upper and lower
bounds, as well as findings from the experimental evaluation of the
algorithms.