Department of Computer Science and Technology

Thomas Sauerwald

Professor of Algorithms and Probability at the Department of Computer Science and Technology (since October 2020, joined as a Lecturer in 2013)

Director of Studies at Emmanuel College (since October 2017).

Contact Details

Dr Thomas Sauerwald
University of Cambridge
Computer Laboratory
15 JJ Thomson Avenue
Cambridge CB3 0FD
United Kingdom

Email: firstname.lastname at cl.cam.ac.uk
Phone: +44 1223 763538
Fax: +44 1223 334678
Office: FC11

Research Interests

Research Projects and Funding

I was the PI of a five-year project "Dynamics of Multiple, Interacting and Concurrent Markov Chains" (DYNAMIC MARCH) as part of an ERC Starting Grant funded by the European Research Council. The project ran from 2016-2021, and its aims are to explore new algorithms based on multiple random walks that are able to cope with complex data sets and networks. In 2018, I was a Mercator Fellow as part of the project "Analysis of Discrete Load Balancing on Heterogeneous Networks" (ADLON) (co-PI together with Tobias Friedrich, HPI Potsdam), funded by the German Research Council (DFG). From 2014-2015, I was the principal investigator of the project "Random Walks on Massive Graphs" supported by the Isaac Newton Trust / University of Cambridge Early Career Support Scheme.

Supervised Postdocs and Students (recent)

  • James Alner (Part II student, 2020-21)
  • Leran Cai (PhD student, 10/2016-12/2020)
  • Dimitrios Los (PhD student, since 10/2019)
  • Vladimir Milenkovic (Part II student, 2019-20, Part III student 2020-21)
  • Charlotte Out (PhD Student, since 10/2022)
  • Nicolas Rivera (Postdoc, 09/2017-10/2020)
  • Hayk Saribekyan (PhD student, 10/2017-10/2021)
  • John Sylvester (Postdoc, 09/2017-06/2020)
  • Vu Phan Thanh (MPhil student, 2019-20)
  • Andor Vari-Vakas (Part II student, 2021-22)
  • Luca Zanetti (Postdoc, 06/2017-08/2020)

Selected Recent Publications

A complete list of my publications can be found at DBLP.

  • Balanced Allocations on Hetereogenous Bins: The Power of Memory (with Dimitrios Los and John Sylvester)
    In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), to appear, 2023.
  • Balanced Allocations with the Choice of Noise (with Dimitrios Los)
    In Proceedings of the 41st ACM Symposium on Principle of Distributed Computing (PODC), pages 164-175, Best Student Paper Award. 2022. (arxiv)
  • Balanced Allocations with Incomplete Information: The Power of Two Queries (with Dimitrios Los)
    In Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS), pages 103:1-103:23, 2022. (arxiv)
  • Balanced Allocations: Caching, Packing and Twinning and Thinning (with Dimitrios Los and John Sylvester)
    In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1847-1874, 2022. (arxiv)
  • Time Dependent Biased Random Walks (with John Haslegrave and John Sylvester)
    In ACM Transactions of Algorithms, to appear, 2021. (arxiv)
  • Multiple Random Walks on Graphs: Mixing a Few to Cover Many (with Nicolas Rivera and John Sylvester)
    In Proceedings of the 48th International Colloqoium on Automata, Languages, and Programming (ICALP), pages 107:1-107:16, 2021.
  • Choice and Bias in Random Walks (with Agelos Georgakopoulos, John Haslegrave and John Sylvester)
    Combinatorics, Probability and Computing, 2021, (to appear). Preliminary Version in Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS), pages 76:1-76:19, 2020.
  • Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities (with Luca Zanetti)
    In Proceedings of the 46th International Colloqoium on Automata, Languages, and Programming (ICALP), pages 93:1-93:15, 2019.
  • On coalescence time in graphs--When is coalescing as fast as meeting? (with Varun Kanade and Frederik Mallmann-Trenn)
    In Proceedings of the 30st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 956--965, 2019. arxiv

Program Committees

SODA 2021, ICALP 2020, IJCAI 2019, PODC 2019, SPAA 2018, STACS 2018, ICALP 2017, IPDPS 2017, SIROCCO 2016, ESA 2016, PODC 2016, SPAA 2016, ISAAC 2015, FCT 2015, IPDPS 2015, SODA 2015, DISC 2014, STACS 2013, SPAA 2012, SIROCCO 2012, SIROCCO 2010

Editorial Boards

Journal of Computer and System Sciences

Academic Activities

Teaching