Virtual satellite workshop of MFCS 2020 on August 28, 2020

Registration and Program

A formal registration is not necessary. The program consists of the following eight invited talks.

All times are Central European Summer Time (CEST).

Session 1: Classical Advice (Chair: Dennis Komm)
12:35Hans-Joachim Böckenhauer, Jan Dreier, Fabian Frei, and Peter Rossmanith: Advice for proportional online knapsack with removable items (slides)
13:00Shahin Kamali: Advice in the context of some geometric problems (slides, video)
13:25Coffee break
Session 2: Advice-Related Models (Chair: Christoph Dürr)
13:50Joan Boyar, Kim S. Larsen, and Denis Pankratov: Priority algorithms — part 1: exact algorithms (slides, video)
14:15Joan Boyar, Kim S. Larsen, and Denis Pankratov: Priority algorithms — part 2: lower bounds (slides, video)
14:40Susanne Albers and Maximilian Janke: Scheduling in the random-order model (slides, video)
15:05Coffee break
Session 3: Machine Learned Advice (Chair: Hans-Joachim Böckenhauer)
15:30Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev: Secretary and online matching problems with machine learned advice (slides, video)
15:55Spyros Angelopoulus, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault: Untrusted advice (slides, video)
16:20Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon: Online metric algorithms with untrusted predictions (slides, video)
16:45Open end discussion

Call for Papers

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.

There will be no formal proceedings.

Important Note: OLAWA will be held fully virtually using Zoom. We will inform all participants by e-mail around 30 minutes prior to its start. Please contact us if you would like to join.

Program Committee

Important Dates