Explorable Uncertainty and Untrusted Predictions

7^th June 2022, 13:00 Ashton Lecture Theatre
Prof. Thomas Erlebach
Department of Computer Science, Durham University

Abstract

The research area of explorable uncertainty is concerned with problems where some of the input data is uncertain, but queries can be executed to reveal the true values of uncertain input elements. Uncertain values are typically given in the form of intervals. The goal is to minmise the number of queries that are needed until a provably correct solution can be output. In addition to the intervals, we may have access to predictions of the true values, possibly obtained via machine learning. Our aim is then to devise query strategies that benefit from accurate predictions but do not get misled too much by incorrect predictions. In this talk, we will discuss some recent progress in this combined setting, including query strategies for minimum spanning trees with edge uncertainty that benefit from good predictions while maintaining the best possible worst-case competitive ratio even if the predictions are arbitrarily wrong.

The talk is mainly based on joint work with Murilo Santos de Lima, Nicole Megow and Jens Schlöter. Supported by EPSRC project EP/S033483/2 (ACUTE).

Additional Materials

• https://arxiv.org/abs/2011.07385