Thomas Sauerwald

ACM Trans. Algorithms, October, 2024

The Power of Filling in Balanced Allocations.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., March, 2024

Rumors with Changing Credibility.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Balanced Allocations with the Choice of Noise.

[BibT_eX]

[DOI]

J. ACM, December, 2023

On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?

[BibT_eX]

[DOI]

Varun Kanade

Frederik Mallmann-Trenn

ACM Trans. Algorithms, April, 2023

Multiple random walks on graphs: mixing few to cover many.

[BibT_eX]

[DOI]

Nicolás Rivera

Comb. Probab. Comput., 2023

Mean-Biased Processes for Balanced Allocations.

[BibT_eX]

[DOI]

CoRR, 2023

Balanced Allocation in Batches: The Tower of Two Choices.

[BibT_eX]

[DOI]

CoRR, 2023

Tight Bounds for Repeated Balls-Into-Bins.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Balanced Allocations in Batches: The Tower of Two Choices.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Balanced Allocations with Heterogeneous Bins: The Power of Memory.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

The Support of Open Versus Closed Random Walks.

[BibT_eX]

[DOI]

He Sun

Danny Vagnozzi

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Time Dependent Biased Random Walks.

[BibT_eX]

[DOI]

John Haslegrave

ACM Trans. Algorithms, 2022

The power of two choices for random walks.

[BibT_eX]

[DOI]

Agelos Georgakopoulos

John Haslegrave

Comb. Probab. Comput., 2022

Balanced Allocations in Batches: Simplified and Generalized.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Brief Announcement: Tight Bounds for Repeated Balls-into-Bins.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Balanced Allocations: Caching and Packing, Twinning and Thinning.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Accelerated Information Dissemination on Networks with Local and Global Edges.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2022

Balanced Allocations with Incomplete Information: The Power of Two Queries.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2020

Spread of Information and Diseases via Random Walks in Sparse Graphs.

[BibT_eX]

[DOI]

George Giakkoupis

Hayk Saribekyan

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Random Walks on Randomly Evolving Graphs.

[BibT_eX]

[DOI]

Leran Cai

Luca Zanetti

Proceedings of the Structural Information and Communication Complexity, 2020

Choice and Bias in Random Walks.

[BibT_eX]

[DOI]

Agelos Georgakopoulos

John Haslegrave

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities.

[BibT_eX]

[DOI]

Luca Zanetti

CoRR, 2019

The Dispersion Time of Random Walks on Finite Graphs.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract.

[BibT_eX]

[DOI]

Varun Kanade

Frederik Mallmann-Trenn

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities.

[BibT_eX]

[DOI]

Luca Zanetti

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks.

[BibT_eX]

[DOI]

Distributed Comput., 2017

Multiple Random Walks on Paths and Grids.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Randomized Load Balancing on Networks with Stochastic Inputs.

[BibT_eX]

[DOI]

Leran Cai

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Balls into bins via local search: Cover time and maximum load.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

A simple approach for adapting continuous load balancing processes to discrete settings.

[BibT_eX]

[DOI]

Hoda Akbari

Distributed Comput., 2016

2015

Randomized diffusion for indivisible loads.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Asymptotic Bounds on the Equilateral Dimension of Hypercubes.

[BibT_eX]

[DOI]

Lorenz Minder

Sven-Ake Wegner

Graphs Comb., 2015

Randomized Rumour Spreading: The Effect of the Network Topology.

[BibT_eX]

[DOI]

Konstantinos Panagiotou

Xavier Pérez-Giménez

He Sun

Comb. Probab. Comput., 2015

Faster Rumor Spreading With Multiple Calls.

[BibT_eX]

[DOI]

Konstantinos Panagiotou

Ali Pourmiri

Electron. J. Comb., 2015

Communication Complexity of Quasirandom Rumor Spreading.

[BibT_eX]

[DOI]

Algorithmica, 2015

Lock-Free Algorithms under Stochastic Schedulers.

[BibT_eX]

[DOI]

Dan Alistarh

Milan Vojnovic

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Ultra-Fast Load Balancing on Scale-Free Networks.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Randomised broadcasting: Memory vs. randomness.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Quasirandom Rumor Spreading.

[BibT_eX]

[DOI]

Benjamin Doerr

ACM Trans. Algorithms, 2014

Distributed Selfish Load Balancing on Networks.

[BibT_eX]

[DOI]

Martin Hoefer

ACM Trans. Algorithms, 2014

Cutoff phenomenon for random walks on Kneser graphs.

[BibT_eX]

[DOI]

Ali Pourmiri

Discret. Appl. Math., 2014

HIT'nDRIVE: Multi-driver Gene Prioritization Based on Hitting Time.

[BibT_eX]

[DOI]

Süleyman Cenk Sahinalp

Proceedings of the Research in Computational Molecular Biology, 2014

Randomized Rumor Spreading in Dynamic Graphs.

[BibT_eX]

[DOI]

George Giakkoupis

Alexandre Stauffer

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Fast message dissemination in random geometric networks.

[BibT_eX]

[DOI]

Distributed Comput., 2013

Threshold Load Balancing in Networks.

[BibT_eX]

[DOI]

Martin Hoefer

CoRR, 2013

Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions.

[BibT_eX]

[DOI]

Alexandre Stauffer

Algorithmica, 2013

Balls-into-bins with nearly optimal load distribution.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Balls into Bins via Local Search.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Brief announcement: threshold load balancing in networks.

[BibT_eX]

[DOI]

Martin Hoefer

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012

Quasirandom Load Balancing.

[BibT_eX]

[DOI]

Martin Gairing

SIAM J. Comput., 2012

Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning.

[BibT_eX]

[DOI]

Algorithmica, 2012

Low Randomness Rumor Spreading via Hashing.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Rumor spreading and vertex expansion.

[BibT_eX]

[DOI]

George Giakkoupis

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Ultra-fast rumor spreading in social networks.

[BibT_eX]

[DOI]

Nikolaos Fountoulakis

Konstantinos Panagiotou

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Counting Arbitrary Subgraphs in Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies.

[BibT_eX]

[DOI]

He Sun

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Tight bounds for the cover time of multiple random walks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Smoothed analysis of balancing networks.

[BibT_eX]

[DOI]

Dan Vilenchik

Random Struct. Algorithms, 2011

Quasirandom rumor spreading: An experimental analysis.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2011

Stabilizing consensus with the power of two choices.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Rumor Spreading and Vertex Expansion on Regular Graphs.

[BibT_eX]

[DOI]

Alexandre Stauffer

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Faster Coupon Collecting via Replication with Applications in Gossiping.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

A self-stabilizing algorithm for cut problems in synchronous networks.

[BibT_eX]

[DOI]

Dirk Sudholt

Theor. Comput. Sci., 2010

The impact of randomization in smoothing networks.

[BibT_eX]

[DOI]

Marios Mavronicolas

Distributed Comput., 2010

The Cover Time of Deterministic Random Walks.

[BibT_eX]

[DOI]

Electron. J. Comb., 2010

On Mixing and Edge Expansion Properties in Randomized Broadcasting.

[BibT_eX]

[DOI]

Algorithmica, 2010

Brief Announcement: Stabilizing Consensus with the Power of Two Choices.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 24th International Symposium, 2010

Efficient Broadcast on Random Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Speeding Up Random Walks with Neighborhood Exploration.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Expansion and the cover time of parallel random walks.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Discrete load balancing is (almost) as easy as continuous load balancing.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

2009

On the runtime and robustness of randomized broadcasting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

A new diffusion-based multilevel algorithm for computing graph partitions.

[BibT_eX]

[DOI]

Burkhard Monien

J. Parallel Distributed Comput., 2009

Quasirandom Rumor Spreading on Expanders.

[BibT_eX]

[DOI]

Benjamin Doerr

Electron. Notes Discret. Math., 2009

On randomized broadcasting in Star graphs.

[BibT_eX]

[DOI]

Ulf Lorenz

Discret. Appl. Math., 2009

Near-perfect load balancing by randomized rounding.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Cover Time and Broadcast Time.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

A randomized, o(log w)-depth 2 smoothing network.

[BibT_eX]

[DOI]

Marios Mavronicolas

Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness.

[BibT_eX]

[DOI]

Benjamin Doerr

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

The Weighted Coupon Collector's Problem and Applications.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

Randomized protocols for information dissemination.

[BibT_eX]

[DOI]

PhD thesis, 2008

On Radio Broadcasting in Random Geometric Graphs.

[BibT_eX]

[DOI]

Leszek Gasieniec

Proceedings of the Distributed Computing, 22nd International Symposium, 2008

The power of memory in randomized broadcasting.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Self-stabilizing Cuts in Synchronous Networks.

[BibT_eX]

[DOI]

Dirk Sudholt

Proceedings of the Structural Information and Communication Complexity, 2008

A new diffusion-based multilevel algorithm for computing graph partitions of very high quality.

[BibT_eX]

[DOI]

Burkhard Monien

Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008

Randomisierte Protokolle für die Verteilung von Information [Randomized Protocols for Information Dissemination].

[BibT_eX]

[DOI]

Proceedings of the Ausgezeichnete Informatikdissertationen 2008, 2008

2007

Agent-based randomized broadcasting in large networks.

[BibT_eX]

[DOI]

Ulf Lorenz

Discret. Appl. Math., 2007

Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

2006

Analyzing Disturbed Diffusion on Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

On Randomized Broadcasting in Star Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

2004

Agent-Based Information Handling in Large Networks.

[BibT_eX]

[DOI]

Ulf Lorenz