In August 2020, I will be chairing a MFCS satellite workshop Online Algorithms with Advice and Related Models.
In computational complexity, advice commonly refers to side information supplied to an algorithm. In this workshop, we focus on online settings where the online player is given additional information on the yet unrevealed parts of the input sequence. Advice complexity theory studies such scenarios and how this additional knowledge affects the potential output quality. Of particular interest are information-theoretic lower bounds, that is, bounds that do not make any assumptions on the actual information that is supplied, but only on its quantity, and connections to related models such as randomized computations and machine learning.
Online algorithms with advice generalize many known approaches to get a more realistic picture of the hardness of online problems.
The goal of this workshop is to bring together researchers who are interested in the concept of advice algorithms and in particular in connections to the aforementioned randomized algorithms and machine learning theory.
Due to the current situation, the workshop will be fully online. If you wish to attend, please contact me via email. A Zoom link will be sent to you prior to the workshop.
