# Thomas Sauerwald

University Senior Lecturer at the Department of Computer Science (since October 2018), at the department since July 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

- Markov chains and Random walks
- Randomised algorithms (in particular for load balancing (Poster) or information dissemination)
- Distributed computing
- Graph Theory
- Game Theory

## Research Projects and Funding

I have funding for 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 started in May 2016, and its aims are to explore new algorithms based on multiple random walks that are able to cope with complex data sets and networks. I am currently a Mercator Fellow of the project "Analysis of Discrete Load Balancing on Heterogeneous Networks" (ADLON) (with Tobias Friedrich, HPI Potsdam), funded by the German Research Council. From November 2014-October 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.

## Selected Works

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

**The Power of Two Choices for Random Walks: Hitting, Covering and Complexity**(with Agelos Georgakopoulos, John Haslegrave and John Sylvester)

In Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS), to appear, 2020.**Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities**(with Luca Zanetti)

In Proceedings of the 46th International Colloqium 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 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 956--965, 2019. arxiv**Multiple Random Walks on Paths and Grids**(with Andrej Ivaskovic, Adrian Kosowski and Dominik Pajak)

In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 44:1-44:14, 2017.**Lock-Free Algorithms under Stochastic Schedulers**(with Dan Alistarh and Milan Vojnovic)

In Proceedings of the 34st ACM Symposium on Principles of Distributed Computing (PODC), pages 251-260, 2015.**Randomized Diffusion for Indivisible Loads**(with Petra Berenbrink, Colin Cooper, Tom Friedetzky and Tobias Friedrich)

Journal of Computer and System Sciences, 81(1):159-185, 2015. Preliminary version appeared in SODA'11, pages 429-439.**Randomized Rumor Spreading in Dynamic Graphs**(with George Giakkoupis and Alexandre Stauffer)

In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 495-507, 2014.**HIT'nDRIVE: Multi-Driver Gene Prioritization based on Hitting Time**(with Raunak Shrestha, Ermin Hodzic, Jake Yeung, Kendric Wang, Phuong Dao, Shawn Anderson, Himisha Beltran, Mark A. Rubin, Colin C. Collins, Gholamreza Haffari and S. Chenk Sahinalp)

In Proceedings of the 18th Annual International Conference on Research in Computational Molecular Biology (RECOMB), pages 293-306, 2014.**Distributed Selfish Load Balancing on Networks**(with Petra Berenbrink and Martin Hoefer)

ACM Transactions on Algorithms, 11(1): 2:1-2:29, 2014. Preliminary version appeared in SODA'11, pages 1487-1497.**Quasirandom Rumor Spreading**(with Benjamin Doerr and Tobias Friedrich)

ACM Transactions on Algorithms 11(2): 9:1-9:35, 2014. Preliminary versions appeared in SODA'08, pages 773-781 and ICALP'09, pages 366-377.**Balls into Bins via Local Search**(with Paul Bogdan, Alexandre Stauffer and He Sun)

In Proceedings of the 24th ACM Symposium on Discrete Algorithms (SODA), pages 16-34, 2013. Full version available on Arxiv.**Tight Bounds For Randomized Load Balancing on Arbitrary Network Topologies**(with He Sun)

In Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 341-350, 2012. Full version available on Arxiv.**Quasirandom Load Balancing**(with Tobias Friedrich and Martin Gairing)

SIAM Journal on Computing, 41(4):747-771, 2012. Preliminary version appeared in SODA'10, pages 1620-1629.**Counting Arbitrary Subgraphs in Data Streams**(with Daniel M. Kane, Kurt Mehlhorn and He Sun)

In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 598-609, 2012.**Rumor Spreading and Vertex Expansion**(with George Giakkoupis)

In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1623-1641, 2012.**Ultra-Fast Rumor Spreading in Social Networks**(with Nikolas Fountoulakis and Konstantinos Panagiotou)

In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1642-1661, 2012.**Tight Bounds for the Cover Time of Multiple Random Walks**(with Robert Elsässer)

Theoretical Computer Science, 412(24): 2623-2641, 2011. Preliminary version appeared in ICALP'09, pages 415-426.**On Mixing and Edge Expansion Properties in Randomized Broadcasting**

Algorithmica, 56(1):51-88, 2010. Preliminary version appeared in ISAAC'07, pages 196-207.**Expansion and the Cover Time of Parallel Random Walks**

In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), pages 315-324, 2010.**Speeding Up Random Walks with Neighborhood Exploration**(with Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik)

In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1422-1435, 2010.**The Impact of Randomization in Smoothing Networks**(with Marios Mavronicolas)

Distributed Computing, 22(5-6), pages 381-411, 2010. Preliminary version appeared in PODC'08, pages 345-354.**Near-Perfect Load Balancing by Randomized Rounding**(with Tobias Friedrich)

In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 121-130, 2009.

## Program Committees

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

- 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 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 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)
- Invited 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 Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl, 20-25 January 2013)

## Teaching

- Easter term 2018/19: Part II course Advanced Algorithms
- Lent term 2018/19: Part II course 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"