Computer Laboratory

Thomas Sauerwald

University Lecturer at the Computer Laboratory (since July 2013).

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

Research Interests


  • Randomized algorithms
  • Markov chains and random walks
  • Distributed computing
  • Graph Theory
  • Game Theory

Selected Publications


For the complete list of my publications, please see my DBLP entry.

Load Balancing  The problem of load balancing on large networks is to find distributed algorithms that balance the load across the units of the network efficiently. Most of our work focuses on two popular communication models, the diffusion and the matching model. For both models, we analyze several iterative protocols that employ the idea of randomized rounding. We show that these protocols almost achieve the same discrepancy within the same number of rounds as their counterparts for the case of divisible load.

  • Balls into Bins via Local Search: Cover Time and Maximum Load (with Karl Bringmann, Alexandre Stauffer and He Sun)
    In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pages 187-198, 2014. Full version available on Arxiv.  
  • 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.  
  • Distributed Selfish Load Balancing on Networks (with Petra Berenbrink and Martin Hoefer)
    ACM Transactions on Algorithms, to appear. Preliminary version appeared in SODA'11.  
  • 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.  
  • Smoothed Analysis of Balancing Networks (with Tobias Friedrich and Dan Vilenchik)
    Random Structures & Algorithms, 39(1):115-138, 2011. Preliminary version appeared in ICALP'09, pages 472-483.    
  • 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.  

Rumor Spreading  Randomized rumor spreading are simple epidemic protocols that spread one message (rumor) from one node to all other nodes. This is done by allowing nodes to exchange the rumor with a randomly chosen neighbor in each round. The main question is to determine the number of required rounds to spread the rumor to all nodes on different networks. Our research includes: (1) analyzing the rumor spreading time on different network models, e.g., social networks; (2) studying the relation to graph parameters such as vertex- or edge expansion; (3) understanding the randomness requirement of rumor spreading.

  • 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.
  • Low Randomness Rumor Spreading via Hashing (with George Giakkoupis, He Sun and Philipp Woelfel)
    In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 314-325, 2012.
  • Quasirandom Rumor Spreading (with Benjamin Doerr and Tobias Friedrich)
    ACM Transactions on Algorithms, to appear. Preliminary versions appeared in SODA'08 and ICALP'09.
  • On Mixing and Edge Expansion Properties in Randomized Broadcasting
    Algorithmica, 56(1):51-88, 2010. Preliminary version appeared in ISAAC'07, pages 196-207.

Random Walks  The cover time of random walks is an ubiquitous parameter of graphs, which has many interesting relations to electrical networks, spectral graph theory, probability theory, complexity theory etc. We study different ways to speed up random walks with the aim of decreasing their cover time. For instance, we examine random walks that are able to explore their neighborhood in each step or analyze the cover time of parallel random walks.

  • 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.  
  • The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks (with Ralf Klasing, Adrian Kosowski and Dominik Pajak)
    In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 365-374, 2013.  
  • 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.  
  • 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.  
  • Cover Time and Broadcast Time (with Robert Elsässer)
    In Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS), pages 373-384, 2009.

Short Bio


since 07/2013 Lecturer at the University of Cambridge, United Kingdom
08/2012 - 06/2013 Independent Research Group Leader (W2) of the group Efficient Algorithms for Massive Graphs at the Cluster of Excellence on Multimodal Computing and Interaction, Saarbrücken, Germany
10/2010 - 06/2013 Research Associate and later Senior Researcher at Max Planck Institute for Informatics, Saarbrücken, Germany
10/2009 - 09/2010 Postdoc at the School of Computing Science at Simon Fraser University, Burnaby, Canada supported by the Pacific Institute for the Mathematical Sciences (PIMS)
09/2008 - 08/2009 Postdoc at the International Computer Science Institute (ICSI), Berkeley, USA
10/2005 - 07/2008   Ph. D. in Computer Science within the PaSCo graduate school at the University of Paderborn

Teaching

I taught the second part of Algorithms in the Lent term Link