Talk by Tony Wirth (University of Sydney) on Coverage Problems in Streams

On October 2, 2025, 11:00-12:00, we are happy to host a talk by Tony Wirth on coverage problems in streams. The talk will take place in Erzherzog-Johann-Platz 1, 1040 Wien, in Seminarraum FB 02 10 (second floor). You are most welcome to join us.

Title: Coverage problems in streams

Speaker: Tony Wirth, University of Sydney

Abstract: Set Cover and Maximum-k-Coverage are fundamental NP-hard computational problems. The greedy algorithm for set selection is known to be effective and, in some sense, optimal. However, realizing the greedy approach on streamed data (indeed on data in external memory) is not obvious. In this presentation, I recap several of my works on coverage in streams, including multi-pass streams, random-order streams and dynamic streams, some lower bounds, and on practical approaches to accelerate the principled application of greedy. This includes collaborations with Graham Cormode, Howard Karloff, Amit Chakrabarti, Stephen Jaud, Farhana Choudhury, and Rowan Warneke. Time permitting, I will talk to my latest work on Maximum Unique Coverage, an elegant variant, with Phil Cervenjak, Junhao Gan, and William Umboh.

About: Since April 2024, Tony Wirth has been Professor in the School of Computer Science at The University of Sydney, now Interim Head of School. Prior to this, he had a 19-year career in the School of Computing and Information Systems at Melbourne, also his undergraduate institution. His PhD was at Princeton, advised by Moses Charikar. Tony’s interests are several, and include: approximation algorithms for graph problems, specifically correlation clustering; streaming problems, specifically max coverage and set cover; search with errors; and compression and search in text archives and streams.