# 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

- Randomised Algorithms, in particular for distributed computing (visualisations: Balanced Allocations in Batches, Balls-into-Bins Processes (by Dimitris Los), poster on Load Balancing)
- Markov Chains and Random Walks (slides on Coalescing Walks and Random Walks on Dynamic Graphs)
- Machine Learning and Data Science

## Research Projects and Funding

I am currently a Mercator Fellow of the grant Algorithms, Dynamics, and Information Flow in Networks (ADYN) funded by German Research Council (DFG). From 2016-2021, 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. From 2015-2019, I was a co-PI of the grant "Analysis of Discrete Load Balancing on Heterogeneous Networks" (ADLON) funded by the German Research Council (DFG). From 2014-2015, I was the PI 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, 10/2019-03/2023)
- Jedidiah Koh (Part II student, 2022-23)
- 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)

## Recent Publications

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

**Balanced Allocations with the Choice of Noise**(with Dimitrios Los)

Journal of the ACM, pages 1-84, 2023. Preliminary Version in Proceedings of the 41st ACM Symposium on Principle of Distributed Computing (PODC), pages 164-175,*Best Student Paper Award.*2022.**The Power of filling in balanced allocations**(with Dimitrios Los and John Sylvester)

SIAM Journal on Discrete Mathematics, pages 1-38, 2023.**The Support of Open Versus Closed Random Walks**(with He Sun and Danny Vagnozzi)

In Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP), Track A, pages 103:1-103:21, 2023.**Balanced Allocations in Batches: The Tower of Two Choices**(with Dimitrios Los)

In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms (SPAA), pages 51-61, 2023.**Tight Bounds for Repeated Balls-into-Bins**(with Dimitrios Los)

In Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 45:1--45:2, 2023. Preliminary Version in Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 419-421, 2022.**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), pages 4448-4477, 2023.**On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?**(with Varun Kanade and Frederik Mallmann-Trenn)

ACM Transactions on Algorithms, Volume 19, Issue 2, pages 1-46, 2023. Preliminary Version in Proceedings of the 30st ACM-SIAM Symposium on Disccrete Algorithms (SODA), pages 956-965, 2019.**Balanced Allocations with the Choice of Noise**(with Dimitrios Los)

In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing, pages 164-175, 2022.**Balanced Allocations in Batches: Simplified and Generalized**(with Dimitrios Los)

In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 389-399, 2022.**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)**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)**Time Dependent Biased Random Walks**(with John Haslegrave and John Sylvester)

In ACM Transactions of Algorithms, Volume 18, Issue 2, pages 1-30, 2022.**The power of two choices for random walks**(with Agelos Georgakopoulos, John Haslegrave and John Sylvester)

Combinatorics, Probability and Computing, Volume 31, Issue 1, pages 73-100, 2021. Preliminary Version in Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS), pages 76:1-76:19, 2020.**Multiple Random Walks on Graphs: Mixing a Few to Cover Many**(with Nicolas Rivera and John Sylvester)

Combinatorics, Probability and Computing, Volume 32, Issue 4, pages 594-637, 2023. Preliminary Version 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)

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 Colloquium on Automata, Languages, and Programming (ICALP), pages 93:1-93:15, 2019.**On coalesence time in graphs: When is coalescing as fast as meeting?: Extended Abstract**(with Varun Kanade and Frederik Mallmann-Trenn)

In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algortihms (SODA), pages 956-965, 2019.**The Dispersion Time of Random Walks on Finite Graphs**(with Nicolas Rivera, John Sylvester and Alexandre Stauffer)

In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 103-113, 2019.

## Program Committees

EURO-PAR 2022, CIAC 2022, 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 (2015-2022)

## Invited Talks and Workshops

- Invited speaker at 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) (Bath, 17-21 June 2024)
- Invited speaker at Dagstuhl Seminar: Theory of Randomized Optimization Heuristics (Dagstuhl, 30 June-5 July 2024)
- Invited speaker at Workshop E-PIC: Probability, Information Theory and Computing (Dortmund, 17-21 April 2023)
- Participant at Oberwolfach Workshop Random Graphs: Combinatorics, Complex Network and Disordered Systems (Oberwolfach, 26-31 March 2023)
- Invited speaker at Summerschool on Algorithms, Dynamics, and Information Flow in Networks (Dortmund, 27 June-1 July 2022)
- Invited speaker at Workshop: Mathematics of Large Network (Budapest, 9-13 May 2022)
- Invited speaker at 8th Workshop on Advances in Distributed Graph Algorithms (Budapest, 14 October 2019)
- Invited speaker at 4th Algo UK Workshop (Warwick, 17-18 September 2019)
- Participant (and Runner) at 19th International Conference on Random Structures and Algorithms (Zurich, 15-19 July 2019)
- Invited speaker at Conference Analysis of and on Networks (Teesside, 22 March 2019)
- Invited speaker at Workshop on Distributed Algorithms @ Loughborough (Networks: Reliability, Routing and Memory) (Loughborough, 28 January 2019)
- Invited speaker at Workshop on Emergent Algorithms and Network Dynamics (Paris IHP, 10-11 October 2018)
- Invited speaker at Workshop on Structural Sparsity, Logic and Algorithms (Warwick, 18-21 June 2018)
- Invited speaker at British Colloquium for Theoretical Computer Science 2018 (Royal Holloway London, 26-28 March 2018)
- Invited speaker at London Mathematical Society - EPSRC Durham Symposium on Markov Processes, Mixing Times and Cutoff (Durham, 26 July-5 August 2017)
- Invited speaker at Workshop on Random Graphs and Random Processes (King's College London, 25 April 2017)
- Invited speaker at Dagstuhl Seminar Probabilistic Methods in the Design and Analysis of Algorithms (Dagstuhl, 4-9 April 2017)
- Invited speaker at Workshop on Random Processes in Discrete Structures 2016 (Warwick, 30 August-2 September 2016)
- Invited speaker at 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), (Helsinki, 19-21 July 2016)
- Invited speaker at Bristol Algorithms Day (Bristol, 2-3 Febrary 2016)
- Invited speaker at Random walks on graphs and potential theory (Warwick, 18-22 May 2015)
- Invited speaker at Oxford Algorithms Day (Oxford, 15 April 2015)
- invited speaker at Workshop on Randomized Algorithms for Distributed Computing and Networks (Rennes, 21 July 2014)
- Participant at ICERM Workshop on Stochastic Graph Models (Brown, 17-21 March 2014)
- Invited speaker at 2nd Workshop on Advanced in Distributed Graph Algorithms (Jerusalem, 14 October 2013)
- Invited speaker at Foundations of Network Science (Riga, 7 July 2013)
- Invited speaker at Dagstuhl Seminar Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl, 20-25 January 2013)

## Teaching

- Easter term 2023/24: Part IA course Introduction to Probability
- Lent term 2023/24: Part II course Randomised Algorithms
- Easter term 2022/23: Part IA course Introduction to Probability
- Lent term 2022/23: Part II course Randomised Algorithms
- Easter term 2021/22: Part IA course Introduction to Probability
- Lent term 2021/22: Part II course Randomised Algorithms
- Easter term 2020/21: Part IA course Introduction to Probability
- Easter term 2020/21: Part II course Advanced Algorithms
- Easter term 2019/20: Part IA course Introduction to Probability
- Easter term 2019/20: Part II course Advanced Algorithms
- Lent term 2019/20: Part II (Unit of Assessment) Probability and Computation
- Easter term 2018/19: Part II course Advanced Algorithms
- Lent term 2018/19: Part II (Unit of Assessment) Probability and Computation
- Michaelmas term 2018/19: MPhil course Machine Learning
- Easter term 2017/18: Part II course Advanced Algorithms
- Michaelmas term 2017/18: MPhil course Machine Learning and Algorithms for Data Mining
- Easter term 2016/17: Part II course Advanced Algorithms
- Lent term 2016/17: MPhil course Machine Learning and Algorithms for Data Mining
- Easter term 2015/16: Part II course Advanced Algorithms
- Lent term 2015/16: MPhil course Machine Learning and Algorithms for Data Mining
- Lent term 2015/16: Part IA course Algorithms
- Easter term 2014/15: Part II course Advanced Algorithms
- Lent term 2014/15: Part IA course Algorithms
- Lent term 2013/14: Part IA course Algorithms