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).
| 12:30 | Opening |
| Session 1: Classical Advice (Chair: Dennis Komm) | |
| 12:35 | Hans-Joachim Böckenhauer, Jan Dreier, Fabian Frei, and Peter Rossmanith: Advice for proportional online knapsack with removable items (slides) |
| 13:00 | Shahin Kamali: Advice in the context of some geometric problems (slides, video) |
| 13:25 | Coffee break |
| Session 2: Advice-Related Models (Chair: Christoph Dürr) | |
| 13:50 | Joan Boyar, Kim S. Larsen, and Denis Pankratov: Priority algorithms — part 1: exact algorithms (slides, video) |
| 14:15 | Joan Boyar, Kim S. Larsen, and Denis Pankratov: Priority algorithms — part 2: lower bounds (slides, video) |
| 14:40 | Susanne Albers and Maximilian Janke: Scheduling in the random-order model (slides, video) |
| 15:05 | Coffee break |
| Session 3: Machine Learned Advice (Chair: Hans-Joachim Böckenhauer) | |
| 15:30 | Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev: Secretary and online matching problems with machine learned advice (slides, video) |
| 15:55 | Spyros Angelopoulus, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault: Untrusted advice (slides, video) |
| 16:20 | Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon: Online metric algorithms with untrusted predictions (slides, video) |
| 16:45 | Open 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
- Hans-Joachim Böckenhauer (ETH Zurich, co-chair)
- Joan Boyar (University of Southern Denmark)
- Christoph Dürr (Sorbonne Université)
- Dennis Komm (ETH Zurich, co-chair)
- Peter Rossmanith (RWTH Aachen University)
- Shahin Kamali (University of Manitoba)
Important Dates
- Submission Deadline June 30, 2020
- Notification of Acceptance July 14, 2020
- Workshop August 28, 2020