AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

One of the difficulties that dynamic algorithms need to deal with is the fact that future updates and queries are unknown. Sometimes dynamic problems are studied in the offline variant, where we assume that the whole sequence of queries and updates is known in advance. What happens if we assume – in the spirit of learning-augmented algorithms – that a black-box predictor gives us some approximate knowledge about the yet unseen part of the input? The talk will be about our ongoing work related to speeding-up dynamic algorithms using possibly imperfect knowledge about future requests. I'll give a big-picture overview, explain basic assumptions, talk about some preliminary results, and state a bunch of open problems (some of them might be easy). This is joint work with many people, including Jan van den Brand, Sebastian Forster, Danupon Nanongkai, and Yasamin Nazari.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online, but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.