Thomas Sauerwald

146 papers A* 30A 15B 20Misc 2Journal 69Unranked 8

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	(Almost) Perfect Discrete Iterative Load Balancing. SODA Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald
2026	A*	`conf`	Time-Biased Random Walks and Robustness of Expanders. SODA Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
2025	J	`jnl`	(Almost) Perfect Discrete Iterative Load Balancing. CoRR Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald
2024	J	`jnl`	An Improved Drift Theorem for Balanced Allocations. ACM Trans. Algorithms Dimitrios Los, Thomas Sauerwald
2024	A	`conf`	Rumors with Changing Credibility. ITCS Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester
2024	J	`jnl`	The Power of Filling in Balanced Allocations. SIAM J. Discret. Math. Dimitrios Los, Thomas Sauerwald, John Sylvester
2024	J	`jnl`	Time-Biased Random Walks and Robustness of Expanders. CoRR Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
2023	J	`jnl`	An Improved Drift Theorem for Balanced Allocations. CoRR Dimitrios Los, Thomas Sauerwald
2023	J	`jnl`	Balanced Allocation in Batches: The Tower of Two Choices. CoRR Dimitrios Los, Thomas Sauerwald
2023	B	`conf`	Balanced Allocations in Batches: The Tower of Two Choices. SPAA Dimitrios Los, Thomas Sauerwald
2023	A*	`conf`	Balanced Allocations with Heterogeneous Bins: The Power of Memory. SODA Dimitrios Los, Thomas Sauerwald, John Sylvester
2023	J	`jnl`	Balanced Allocations with Heterogeneous Bins: The Power of Memory. CoRR Dimitrios Los, Thomas Sauerwald, John Sylvester
2023	J	`jnl`	Balanced Allocations with the Choice of Noise. J. ACM Dimitrios Los, Thomas Sauerwald
2023	J	`jnl`	Mean-Biased Processes for Balanced Allocations. CoRR Dimitrios Los, Thomas Sauerwald, John Sylvester
2023	J	`jnl`	Multiple random walks on graphs: mixing few to cover many. Comb. Probab. Comput. Nicolás Rivera, Thomas Sauerwald, John Sylvester
2023	J	`jnl`	On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ACM Trans. Algorithms Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
2023	J	`jnl`	Rumors with Changing Credibility. CoRR Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester
2023	A*	`conf`	The Support of Open Versus Closed Random Walks. ICALP Thomas Sauerwald, He Sun, Danny Vagnozzi
2023	A	`conf`	Tight Bounds for Repeated Balls-Into-Bins. STACS Dimitrios Los, Thomas Sauerwald
2022	B	`conf`	Accelerated Information Dissemination on Networks with Local and Global Edges. SIROCCO Sarel Cohen, Philipp Fischbeck, Tobias Friedrich, Martin S. Krejca, Thomas Sauerwald
2022	B	`conf`	Balanced Allocations in Batches: Simplified and Generalized. SPAA Dimitrios Los, Thomas Sauerwald
2022	J	`jnl`	Balanced Allocations in Batches: Simplified and Generalized. CoRR Dimitrios Los, Thomas Sauerwald
2022	A	`conf`	Balanced Allocations with Incomplete Information: The Power of Two Queries. ITCS Dimitrios Los, Thomas Sauerwald
2022	A*	`conf`	Balanced Allocations with the Choice of Noise. PODC Dimitrios Los, Thomas Sauerwald
2022	J	`jnl`	Balanced Allocations with the Choice of Noise. CoRR Dimitrios Los, Thomas Sauerwald
2022	A*	`conf`	Balanced Allocations: Caching and Packing, Twinning and Thinning. SODA Dimitrios Los, Thomas Sauerwald, John Sylvester
2022	B	`conf`	Brief Announcement: Tight Bounds for Repeated Balls-into-Bins. SPAA Dimitrios Los, Thomas Sauerwald
2022	J	`jnl`	The Power of Filling in Balanced Allocations. CoRR Dimitrios Los, Thomas Sauerwald, John Sylvester
2022	J	`jnl`	The power of two choices for random walks. Comb. Probab. Comput. Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester
2022	J	`jnl`	Tight Bounds for Repeated Balls-into-Bins. CoRR Dimitrios Los, Thomas Sauerwald
2022	J	`jnl`	Time Dependent Biased Random Walks. ACM Trans. Algorithms John Haslegrave, Thomas Sauerwald, John Sylvester
2021	J	`jnl`	Balanced Allocations with Incomplete Information: The Power of Two Queries. CoRR Dimitrios Los, Thomas Sauerwald
2021	J	`jnl`	Balanced Allocations: Caching and Packing, Twinning and Thinning. CoRR Dimitrios Los, Thomas Sauerwald, John Sylvester
2021	A*	`conf`	Multiple Random Walks on Graphs: Mixing Few to Cover Many. ICALP Nicolás Rivera, Thomas Sauerwald, John Sylvester
2020	A	`conf`	Choice and Bias in Random Walks. ITCS Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester
2020	J	`jnl`	Multiple Random Walks on Graphs: Mixing Few to Cover Many. CoRR Nicolás Rivera, Thomas Sauerwald, John Sylvester
2020	B	`conf`	Random Walks on Randomly Evolving Graphs. SIROCCO Leran Cai, Thomas Sauerwald, Luca Zanetti
2020	J	`jnl`	Random walks on randomly evolving graphs. CoRR Leran Cai, Thomas Sauerwald, Luca Zanetti
2020	A	`conf`	Spread of Information and Diseases via Random Walks in Sparse Graphs. DISC George Giakkoupis, Hayk Saribekyan, Thomas Sauerwald
2020	J	`jnl`	Time Dependent Biased Random Walks. CoRR John Haslegrave, Thomas Sauerwald, John Sylvester
2019	A*	`conf`	On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. SODA Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
2019	A*	`conf`	Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. ICALP Thomas Sauerwald, Luca Zanetti
2019	J	`jnl`	Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities. CoRR Thomas Sauerwald, Luca Zanetti
2019	B	`conf`	The Dispersion Time of Random Walks on Finite Graphs. SPAA Nicolás Rivera, Thomas Sauerwald, Alexandre Stauffer, John Sylvester
2019	J	`jnl`	The Power of Two Choices for Random Walks. CoRR Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester
2018	J	`jnl`	The dispersion time of random walks on finite graphs. CoRR Nicolas Rivera, Alexandre Stauffer, Thomas Sauerwald, John Sylvester
2017	A	`conf`	Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. ESA Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, Andrew M. Sutton
2017	J	`jnl`	Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. CoRR Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, Andrew M. Sutton
2017	A	`conf`	Multiple Random Walks on Paths and Grids. STACS Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, Thomas Sauerwald
2017	A*	`conf`	Randomized Load Balancing on Networks with Stochastic Inputs. ICALP Leran Cai, Thomas Sauerwald
2017	J	`jnl`	Randomized Load Balancing on Networks with Stochastic Inputs. CoRR Leran Cai, Thomas Sauerwald
2017	J	`jnl`	The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. Distributed Comput. Ralf Klasing, Adrian Kosowski, Dominik Pajak, Thomas Sauerwald
2016	J	`jnl`	A simple approach for adapting continuous load balancing processes to discrete settings. Distributed Comput. Hoda Akbari, Petra Berenbrink, Thomas Sauerwald
2016	J	`jnl`	Balls into bins via local search: Cover time and maximum load. Random Struct. Algorithms Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2016	J	`jnl`	On coalescence time in graphs-When is coalescing as fast as meeting? CoRR Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald
2015	J	`jnl`	Asymptotic Bounds on the Equilateral Dimension of Hypercubes. Graphs Comb. Lorenz Minder, Thomas Sauerwald, Sven-Ake Wegner
2015	J	`jnl`	Communication Complexity of Quasirandom Rumor Spreading. Algorithmica Petra Berenbrink, Robert Elsässer, Thomas Sauerwald
2015	J	`jnl`	Faster Rumor Spreading With Multiple Calls. Electron. J. Comb. Konstantinos Panagiotou, Ali Pourmiri, Thomas Sauerwald
2015	A*	`conf`	Lock-Free Algorithms under Stochastic Schedulers. PODC Dan Alistarh, Thomas Sauerwald, Milan Vojnovic
2015	J	`jnl`	Randomized Rumour Spreading: The Effect of the Network Topology. Comb. Probab. Comput. Konstantinos Panagiotou, Xavier Pérez-Giménez, Thomas Sauerwald, He Sun
2015	J	`jnl`	Randomized diffusion for indivisible loads. J. Comput. Syst. Sci. Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, Thomas Sauerwald
2015	—	`conf`	Ultra-Fast Load Balancing on Scale-Free Networks. ICALP (2) Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger, Thomas Sauerwald
2014	J	`jnl`	Asymptotic bounds on the equilateral dimension of hypercubes. CoRR Lorenz Minder, Thomas Sauerwald, Sven-Ake Wegner
2014	A	`conf`	Balls into bins via local search: cover time and maximum load. STACS Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2014	J	`jnl`	Cutoff Phenomenon for Random Walks on Kneser Graphs. CoRR Ali Pourmiri, Thomas Sauerwald
2014	J	`jnl`	Cutoff phenomenon for random walks on Kneser graphs. Discret. Appl. Math. Ali Pourmiri, Thomas Sauerwald
2014	J	`jnl`	Distributed Selfish Load Balancing on Networks. ACM Trans. Algorithms Petra Berenbrink, Martin Hoefer, Thomas Sauerwald
2014	B	`conf`	HIT'nDRIVE: Multi-driver Gene Prioritization Based on Hitting Time. RECOMB Raunak Shrestha, Ermin Hodzic, Jake Yeung, Kendric Wang, Thomas Sauerwald, Phuong Dao, Shawn Anderson, Himisha Beltran, Mark A. Rubin, Colin C. Collins, Gholamreza Haffari, Süleyman Cenk Sahinalp
2014	J	`jnl`	Quasirandom Rumor Spreading. ACM Trans. Algorithms Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
2014	J	`jnl`	Randomised broadcasting: Memory vs. randomness. Theor. Comput. Sci. Petra Berenbrink, Robert Elsässer, Thomas Sauerwald
2014	—	`conf`	Randomized Rumor Spreading in Dynamic Graphs. ICALP (2) George Giakkoupis, Thomas Sauerwald, Alexandre Stauffer
2013	A*	`conf`	Balls into Bins via Local Search. SODA Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun
2013	J	`jnl`	Balls into bins via local search: cover time and maximum load. CoRR Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun
2013	B	`conf`	Balls-into-bins with nearly optimal load distribution. SPAA Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, Alexandre Stauffer
2013	A*	`conf`	Brief announcement: threshold load balancing in networks. PODC Martin Hoefer, Thomas Sauerwald
2013	J	`jnl`	Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. Algorithmica Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer
2013	J	`jnl`	Fast message dissemination in random geometric networks. Distributed Comput. Artur Czumaj, Robert Elsässer, Leszek Gasieniec, Thomas Sauerwald, Xin Wang
2013	B	`conf`	Faster Rumor Spreading with Multiple Calls. ISAAC Konstantinos Panagiotou, Ali Pourmiri, Thomas Sauerwald
2013	A*	`conf`	The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks. PODC Ralf Klasing, Adrian Kosowski, Dominik Pajak, Thomas Sauerwald
2013	J	`jnl`	Threshold Load Balancing in Networks. CoRR Martin Hoefer, Thomas Sauerwald
2012	A*	`conf`	A simple approach for adapting continuous load balancing processes to discrete settings. PODC Hoda Akbari, Petra Berenbrink, Thomas Sauerwald
2012	J	`jnl`	Balls into Bins via Local Search CoRR Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, He Sun
2012	J	`jnl`	Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning. Algorithmica Henning Meyerhenke, Thomas Sauerwald
2012	—	`conf`	Counting Arbitrary Subgraphs in Data Streams. ICALP (2) Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun
2012	A	`conf`	Low Randomness Rumor Spreading via Hashing. STACS George Giakkoupis, Thomas Sauerwald, He Sun, Philipp Woelfel
2012	J	`jnl`	Quasirandom Load Balancing. SIAM J. Comput. Tobias Friedrich, Martin Gairing, Thomas Sauerwald
2012	A*	`conf`	Rumor spreading and vertex expansion. SODA George Giakkoupis, Thomas Sauerwald
2012	J	`jnl`	Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies CoRR Thomas Sauerwald, He Sun
2012	A*	`conf`	Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies. FOCS Thomas Sauerwald, He Sun
2012	A*	`conf`	Ultra-fast rumor spreading in social networks. SODA Nikolaos Fountoulakis, Konstantinos Panagiotou, Thomas Sauerwald
2011	B	`conf`	Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. ISAAC Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer
2011	A*	`conf`	Distributed Selfish Load Balancing on Networks. SODA Petra Berenbrink, Martin Hoefer, Thomas Sauerwald
2011	B	`conf`	Faster Coupon Collecting via Replication with Applications in Gossiping. MFCS Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald
2011	J	`jnl`	Quasirandom rumor spreading: An experimental analysis. ACM J. Exp. Algorithmics Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
2011	A*	`conf`	Randomized Diffusion for Indivisible Loads. SODA Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, Thomas Sauerwald
2011	A*	`conf`	Rumor Spreading and Vertex Expansion on Regular Graphs. SODA Thomas Sauerwald, Alexandre Stauffer
2011	J	`jnl`	Smoothed analysis of balancing networks. Random Struct. Algorithms Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik
2011	B	`conf`	Stabilizing consensus with the power of two choices. SPAA Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler
2011	J	`jnl`	Tight bounds for the cover time of multiple random walks. Theor. Comput. Sci. Robert Elsässer, Thomas Sauerwald
2010	J	`jnl`	A self-stabilizing algorithm for cut problems in synchronous networks. Theor. Comput. Sci. Thomas Sauerwald, Dirk Sudholt
2010	A	`conf`	Brief Announcement: Stabilizing Consensus with the Power of Two Choices. DISC Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler
2010	—	`conf`	Communication Complexity of Quasirandom Rumor Spreading. ESA (1) Petra Berenbrink, Robert Elsässer, Thomas Sauerwald
2010	A*	`conf`	Discrete load balancing is (almost) as easy as continuous load balancing. PODC Robert Elsässer, Thomas Sauerwald
2010	A*	`conf`	Efficient Broadcast on Random Geometric Graphs. SODA Milan Bradonjic, Robert Elsässer, Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer
2010	A*	`conf`	Expansion and the cover time of parallel random walks. PODC Thomas Sauerwald
2010	J	`jnl`	On Mixing and Edge Expansion Properties in Randomized Broadcasting. Algorithmica Thomas Sauerwald
2010	J	`jnl`	Quasirandom Load Balancing CoRR Tobias Friedrich, Martin Gairing, Thomas Sauerwald
2010	A*	`conf`	Quasirandom Load Balancing. SODA Tobias Friedrich, Martin Gairing, Thomas Sauerwald
2010	J	`jnl`	Quasirandom Rumor Spreading CoRR Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
2010	J	`jnl`	Quasirandom Rumor Spreading: An Experimental Analysis CoRR Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
2010	B	`conf`	Randomised Broadcasting: Memory vs. Randomness. LATIN Petra Berenbrink, Robert Elsässer, Thomas Sauerwald
2010	J	`jnl`	Smoothed Analysis of Balancing Networks CoRR Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik
2010	A*	`conf`	Speeding Up Random Walks with Neighborhood Exploration. SODA Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik, Thomas Sauerwald
2010	J	`jnl`	The Cover Time of Deterministic Random Walks CoRR Tobias Friedrich, Thomas Sauerwald
2010	Misc	`conf`	The Cover Time of Deterministic Random Walks. COCOON Tobias Friedrich, Thomas Sauerwald
2010	J	`jnl`	The Cover Time of Deterministic Random Walks. Electron. J. Comb. Tobias Friedrich, Thomas Sauerwald
2010	J	`jnl`	The impact of randomization in smoothing networks. Distributed Comput. Marios Mavronicolas, Thomas Sauerwald
2009	J	`jnl`	A new diffusion-based multilevel algorithm for computing graph partitions. J. Parallel Distributed Comput. Henning Meyerhenke, Burkhard Monien, Thomas Sauerwald
2009	B	`conf`	A randomized, o(log w)-depth 2 smoothing network. SPAA Marios Mavronicolas, Thomas Sauerwald
2009	J	`jnl`	Cover Time and Broadcast Time CoRR Robert Elsässer, Thomas Sauerwald
2009	A	`conf`	Cover Time and Broadcast Time. STACS Robert Elsässer, Thomas Sauerwald
2009	A*	`conf`	Near-perfect load balancing by randomized rounding. STOC Tobias Friedrich, Thomas Sauerwald
2009	J	`jnl`	On randomized broadcasting in Star graphs. Discret. Appl. Math. Robert Elsässer, Ulf Lorenz, Thomas Sauerwald
2009	J	`jnl`	On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci. Robert Elsässer, Thomas Sauerwald
2009	J	`jnl`	Quasirandom Rumor Spreading on Expanders. Electron. Notes Discret. Math. Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
2009	A	`conf`	Quasirandom Rumor Spreading: An Experimental Analysis. ALENEX Benjamin Doerr, Tobias Friedrich, Marvin Künnemann, Thomas Sauerwald
2009	—	`conf`	Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness. ICALP (1) Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
2009	—	`conf`	Smoothed Analysis of Balancing Networks. ICALP (2) Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik
2009	—	`conf`	Stabilizing Consensus with the Power of Two Choices. Algorithmic Methods for Distributed Cooperative Systems Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler
2009	Misc	`conf`	The Weighted Coupon Collector's Problem and Applications. COCOON Petra Berenbrink, Thomas Sauerwald
2009	—	`conf`	Tight Bounds for the Cover Time of Multiple Random Walks. ICALP (1) Robert Elsässer, Thomas Sauerwald
2008	A	`conf`	A new diffusion-based multilevel algorithm for computing graph partitions of very high quality. IPDPS Henning Meyerhenke, Burkhard Monien, Thomas Sauerwald
2008	A	`conf`	On Radio Broadcasting in Random Geometric Graphs. DISC Robert Elsässer, Leszek Gasieniec, Thomas Sauerwald
2008	A*	`conf`	Quasirandom rumor spreading. SODA Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
2008	—	`ch.`	Randomisierte Protokolle für die Verteilung von Information [Randomized Protocols for Information Dissemination]. Ausgezeichnete Informatikdissertationen Thomas Sauerwald
2008	—	`—`	Randomized protocols for information dissemination. Thomas Sauerwald
2008	B	`conf`	Self-stabilizing Cuts in Synchronous Networks. SIROCCO Thomas Sauerwald, Dirk Sudholt
2008	A*	`conf`	The impact of randomization in smoothing networks. PODC Marios Mavronicolas, Thomas Sauerwald
2008	A*	`conf`	The power of memory in randomized broadcasting. SODA Robert Elsässer, Thomas Sauerwald
2007	J	`jnl`	Agent-based randomized broadcasting in large networks. Discret. Appl. Math. Robert Elsässer, Ulf Lorenz, Thomas Sauerwald
2007	A	`conf`	Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs. STACS Robert Elsässer, Thomas Sauerwald
2007	B	`conf`	On Mixing and Edge Expansion Properties in Randomized Broadcasting. ISAAC Thomas Sauerwald
2006	B	`conf`	Analyzing Disturbed Diffusion on Networks. ISAAC Henning Meyerhenke, Thomas Sauerwald
2006	B	`conf`	On the Runtime and Robustness of Randomized Broadcasting. ISAAC Robert Elsässer, Thomas Sauerwald
2005	B	`conf`	On Randomized Broadcasting in Star Graphs. WG Robert Elsässer, Thomas Sauerwald
2004	B	`conf`	Agent-Based Information Handling in Large Networks. MFCS Robert Elsässer, Ulf Lorenz, Thomas Sauerwald