TITLE: Computing with Uncertainty SPEAKER: Thomas Erlebach (The University of Leicester) ABSTRACT: We consider problems where the input data is initially uncertain but the exact value of an input item can be obtained at a certain cost. For example, a typical setting is that instead of an exact value, only an interval containing the exact value is given. An update of an input item then reveals its exact value. This scenario models real-world situations where only estimates of some input parameters are known initially, but it is possible to obtain the actual values of the input parameters with some extra effort. An algorithm performs a number of updates until it has gathered sufficient information to output a correct solution to the problem. The goal is to minimise the number of updates. We discuss several problems in the setting of computing with uncertainty, including the minimum spanning tree problem and the minimum multicut problem in trees. Algorithms are evaluated using competitive analysis, comparing the number of updates that the algorithm makes on an instance of the problem to the best possible number of updates that suffices to solve that instance. (The talk is based on joint work with Michael Hoffmann, Frank Kammer, Danny Krizanc, Matus Mihalak, and Rajeev Raman.)