Dagstuhl-Seminar — Learned Predictions for Data Structures and Running Time

A long-standing question in theoretical computer science is to offer analysis tools for improving performance on typical everyday, non-worst-case instances. A recent model addressing this goal is the algorithms-with-predictions model: each problem instance comes with a possibly error-prone prediction, and the worst-case running time is given as a function of the error in that prediction. This model reflects how recent advances in machine learning are able to make reasonably good predictions on practical ‒ even very complex ‒ datasets. The algorithms-with-predictions model has been used to give strong approximation-ratio guarantees for fundamental online algorithms like scheduling and caching. How to leverage predictions to speed up running time of offline algorithms and data structures has received less attention. This Dagstuhl Seminar aims to bring together researchers from the data structures, combinatorial optimization and learned predictions communities to address the challenges of adopting learned predictions for improving running time guarantees.