University Lecturer at the Computer Laboratory (since July 2013).
Dr Thomas Sauerwald
University of Cambridge
15 JJ Thomson Avenue
Cambridge CB3 0FD
|Email:||firstname.lastname at cl.cam.ac.uk|
|Phone:||+44 1223 763538|
|Fax:||+44 1223 334678|
- Randomised algorithms (in particular for load balancing (Poster) or information dissemination)
- Markov chains and random walks
- Distributed computing
- Graph Theory
- Game Theory
- 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
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, 2014. Preliminary version appeared in SODA'11, pages 1487-1497.
- Quasirandom Rumor Spreading (with Benjamin Doerr and
ACM Transactions on Algorithms, to appear. 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
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
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
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
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
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
In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 121-130, 2009.
ESA 2016, PODC 2016, SPAA 2016, ISAAC 2015, FCT 2015, IPDPS 2015, SODA 2015, DISC 2014, STACS 2013, SPAA 2012, SIROCCO 2012, SIROCCO 2010
Journal of Computer and System Sciences
- 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)