Dagstuhl-Seminar 25181
Learned Predictions for Data Structures and Running Time
( 27. Apr – 02. May, 2025 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/25181
Organisatoren
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK)
- Benjamin J. Moseley (Carnegie Mellon University - Pittsburgh, US)
- Shikha Singh (Williams College - Williamstown, US)
- Sergei Vassilvitskii (Google - New York, US)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Programm
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. Ideal outcomes include the development of new beyond-worst-case data structures and algorithms, a formal framework to model and analyze predictions, and improved heuristics that bring theory closer to practice.
This seminar will specifically focus on developing foundations for: (1) learned predictions for data structure design, and (2) learned predictions for offline optimization.
Learned Predictions for Data Structure Design. There is strong empirical evidence that augmenting worst-case data structures with machine-learned advice leads to improved running times. These results showcase the potential of learned data structures. This seminar will focus on how to theoretically understand the power and limitations of predictions through the algorithms-with-predictions model. This model has the potential to fundamentally change how the community thinks about designing worst-case data structures ‒ by leveraging predictions that are learnable, incur minimal overhead, and deliver significant speedups on most datasets while simultaneously being robust towards adversarial inputs.
Learned Predictions for Offline Optimization. Traditional running time analysis assumes that problems are solved from scratch. However, algorithms are often run on different data sets over time. These prior runs can encode information that can be used to improve run times in the future. An intuitive approach to speed up an algorithm is to start with some previously computed solution, referred to as a warm start.
Warm-start algorithm design is not new and is commonly used by heuristics. However, most prior work on this topic is empirical. There is a need for a theoretical foundation of warm-start heuristics via the algorithms-with-predictions model.
There has been some preliminary work in the community toward this goal which showcases the potential of the area and serves as a proof-of-concept for other researchers. In particular, recent results show that warm-start can lead to faster algorithms speeding up the Hungarian algorithm for computing weighted bipartite matching. This has since been extended for other graph algorithms. The area of warm-start algorithm design has the potential to grow into an area as deep and interesting as the line of work using predictions online in the competitive analysis model. This seminar will bring together researchers from this area and organize sessions and discussions that build toward this vision.
Creative Commons BY 4.0
Inge Li Gørtz, Benjamin J. Moseley, Shikha Singh, and Sergei Vassilvitskii
Please log in to DOOR to see more details.
- Antonios Antoniadis (University of Twente, NL) [dblp]
- Martin Aumüller (IT University of Copenhagen, DK) [dblp]
- Ioana Oriana Bercea (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Gerth Stølting Brodal (Aarhus University, DK) [dblp]
- Christian Coester (University of Oxford, GB) [dblp]
- Alexander Conway (Cornell Tech - New York, US) [dblp]
- Michael Dinitz (Johns Hopkins University - Baltimore, US) [dblp]
- Christoph Dürr (Sorbonne University - Paris, FR) [dblp]
- Martin Farach-Colton (NYU - New York, US) [dblp]
- Paolo Ferragina (Sant'Anna School of Advanced Studies - Pisa, IT) [dblp]
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK) [dblp]
- John Iacono (ULB - Brussels, BE) [dblp]
- Sungjin Im (University of California - Santa Cruz, US) [dblp]
- Riko Jacob (IT University of Copenhagen, DK) [dblp]
- Rob Johnson (Broadcom - San Jose, US) [dblp]
- Hanna Komlós (NYU - New York, US) [dblp]
- László Kozma (FU Berlin, DE) [dblp]
- William Kuszmaul (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Silvio Lattanzi (Google - Barcelona, ES) [dblp]
- Thomas Lavastida (University of Texas - Dallas, US) [dblp]
- Alexander Lindermayr (Universität Bremen, DE) [dblp]
- Quanquan C. Liu (Yale University - New Haven, US) [dblp]
- Samuel McCauley (Williams College - Williamstown, US) [dblp]
- Ulrich Carsten Meyer (Goethe University - Frankfurt am Main, DE) [dblp]
- Benjamin J. Moseley (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Yasamin Nazari (VU Amsterdam, NL) [dblp]
- Kim Thang Nguyen (University of Grenoble, FR)
- Debmalya Panigrahi (Duke University - Durham, US) [dblp]
- Cynthia A. Phillips (Sandia National Labs - Albuquerque, US) [dblp]
- Adam Polak (Bocconi University - Milan, IT) [dblp]
- Rajeev Raman (University of Leicester, GB) [dblp]
- Golnoosh Shahkarami (MPI für Informatik - Saarbrücken, DE)
- Shikha Singh (Williams College - Williamstown, US) [dblp]
- Clifford Stein (Columbia University - New York, US) [dblp]
- Ola Svensson (EPFL - Lausanne, CH) [dblp]
- Ali Vakilian (TTIC - Chicago, US) [dblp]
- Jan van den Brand (Georgia Institute of Technology - Atlanta, US) [dblp]
- Sergei Vassilvitskii (Google - New York, US) [dblp]
- Ellen Vitercik (Stanford University, US) [dblp]
- Sebastian Wild (University of Liverpool, GB) [dblp]
- Chenyang Xu (East China Normal University - Shanghai, CN) [dblp]
- Helen Xu (Georgia Institute of Technology - Atlanta, US) [dblp]
Klassifikation
- Data Structures and Algorithms
Schlagworte
- Algorithms with predictions
- learning-augmented algorithms
- beyond-worst-case analysis
- data structures
- approximation algorithms
