Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Thomas Sauerwald, He Sun, and Danny Vagnozzi. The Support of Open Versus Closed Random Walks. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 103:1-103:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{sauerwald_et_al:LIPIcs.ICALP.2023.103, author = {Sauerwald, Thomas and Sun, He and Vagnozzi, Danny}, title = {{The Support of Open Versus Closed Random Walks}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {103:1--103:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.103}, URN = {urn:nbn:de:0030-drops-181556}, doi = {10.4230/LIPIcs.ICALP.2023.103}, annote = {Keywords: support of random walks, eigenvalue multiplicity} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Dimitrios Los and Thomas Sauerwald. Tight Bounds for Repeated Balls-Into-Bins. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 45:1-45:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{los_et_al:LIPIcs.STACS.2023.45, author = {Los, Dimitrios and Sauerwald, Thomas}, title = {{Tight Bounds for Repeated Balls-Into-Bins}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {45:1--45:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.45}, URN = {urn:nbn:de:0030-drops-176975}, doi = {10.4230/LIPIcs.STACS.2023.45}, annote = {Keywords: Repeated balls-into-bins, self-stabilizing systems, balanced allocations, potential functions, random walks} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Dimitrios Los and Thomas Sauerwald. Balanced Allocations with Incomplete Information: The Power of Two Queries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 103:1-103:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{los_et_al:LIPIcs.ITCS.2022.103, author = {Los, Dimitrios and Sauerwald, Thomas}, title = {{Balanced Allocations with Incomplete Information: The Power of Two Queries}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {103:1--103:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.103}, URN = {urn:nbn:de:0030-drops-156994}, doi = {10.4230/LIPIcs.ITCS.2022.103}, annote = {Keywords: power-of-two-choices, balanced allocations, potential functions, thinning} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise Molitor. The Impact of Geometry on Monochrome Regions in the Flip Schelling Process. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 29:1-29:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.ISAAC.2021.29, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise}, title = {{The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.29}, URN = {urn:nbn:de:0030-drops-154623}, doi = {10.4230/LIPIcs.ISAAC.2021.29}, annote = {Keywords: Agent-based Model, Schelling Segregation, Spin System} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Multiple Random Walks on Graphs: Mixing Few to Cover Many. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 107:1-107:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{rivera_et_al:LIPIcs.ICALP.2021.107, author = {Rivera, Nicol\'{a}s and Sauerwald, Thomas and Sylvester, John}, title = {{Multiple Random Walks on Graphs: Mixing Few to Cover Many}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {107:1--107:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.107}, URN = {urn:nbn:de:0030-drops-141764}, doi = {10.4230/LIPIcs.ICALP.2021.107}, annote = {Keywords: Multiple Random walks, Markov Chains, Random Walks, Cover Time} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald. Spread of Information and Diseases via Random Walks in Sparse Graphs. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{giakkoupis_et_al:LIPIcs.DISC.2020.9, author = {Giakkoupis, George and Saribekyan, Hayk and Sauerwald, Thomas}, title = {{Spread of Information and Diseases via Random Walks in Sparse Graphs}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.9}, URN = {urn:nbn:de:0030-drops-130873}, doi = {10.4230/LIPIcs.DISC.2020.9}, annote = {Keywords: parallel random walks, information dissemination, infectious diseases} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour. Dynamic Averaging Load Balancing on Cycles. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 7:1-7:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{alistarh_et_al:LIPIcs.ICALP.2020.7, author = {Alistarh, Dan and Nadiradze, Giorgi and Sabour, Amirmojtaba}, title = {{Dynamic Averaging Load Balancing on Cycles}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.7}, URN = {urn:nbn:de:0030-drops-124142}, doi = {10.4230/LIPIcs.ICALP.2020.7}, annote = {Keywords: Algorithms, Load Balancing} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. Choice and Bias in Random Walks. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 76:1-76:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{georgakopoulos_et_al:LIPIcs.ITCS.2020.76, author = {Georgakopoulos, Agelos and Haslegrave, John and Sauerwald, Thomas and Sylvester, John}, title = {{Choice and Bias in Random Walks}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {76:1--76:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.76}, URN = {urn:nbn:de:0030-drops-117612}, doi = {10.4230/LIPIcs.ITCS.2020.76}, annote = {Keywords: Power of Two Choices, Markov Chains, Random Walks, Cover Time, Markov Decision Processes} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Thomas Sauerwald and Luca Zanetti. Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 93:1-93:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{sauerwald_et_al:LIPIcs.ICALP.2019.93, author = {Sauerwald, Thomas and Zanetti, Luca}, title = {{Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {93:1--93:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.93}, URN = {urn:nbn:de:0030-drops-106696}, doi = {10.4230/LIPIcs.ICALP.2019.93}, annote = {Keywords: random walks, dynamic graphs, hitting times} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{friedrich_et_al:LIPIcs.ESA.2017.37, author = {Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sauerwald, Thomas and Sutton, Andrew M.}, title = {{Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.37}, URN = {urn:nbn:de:0030-drops-78356}, doi = {10.4230/LIPIcs.ESA.2017.37}, annote = {Keywords: satisfiability, random structures, random SAT, power law distribution, scale-freeness, phase transitions} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Leran Cai and Thomas Sauerwald. Randomized Load Balancing on Networks with Stochastic Inputs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 139:1-139:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{cai_et_al:LIPIcs.ICALP.2017.139, author = {Cai, Leran and Sauerwald, Thomas}, title = {{Randomized Load Balancing on Networks with Stochastic Inputs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {139:1--139:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.139}, URN = {urn:nbn:de:0030-drops-74839}, doi = {10.4230/LIPIcs.ICALP.2017.139}, annote = {Keywords: random walks, randomized algorithms, parallel computing} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald. Multiple Random Walks on Paths and Grids. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 44:1-44:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{ivaskovic_et_al:LIPIcs.STACS.2017.44, author = {Ivaskovic, Andrej and Kosowski, Adrian and Pajak, Dominik and Sauerwald, Thomas}, title = {{Multiple Random Walks on Paths and Grids}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.44}, URN = {urn:nbn:de:0030-drops-69897}, doi = {10.4230/LIPIcs.STACS.2017.44}, annote = {Keywords: random walks, randomized algorithms, parallel computing} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun. Balls into bins via local search: cover time and maximum load. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 187-198, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{bringmann_et_al:LIPIcs.STACS.2014.187, author = {Bringmann, Karl and Sauerwald, Thomas and Stauffer, Alexandre and Sun, He}, title = {{Balls into bins via local search: cover time and maximum load}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {187--198}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.187}, URN = {urn:nbn:de:0030-drops-44570}, doi = {10.4230/LIPIcs.STACS.2014.187}, annote = {Keywords: Balls and Bins, Stochastic Process, Randomized Algorithm} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
George Giakkoupis, Thomas Sauerwald, He Sun, and Philipp Woelfel. Low Randomness Rumor Spreading via Hashing. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 314-325, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{giakkoupis_et_al:LIPIcs.STACS.2012.314, author = {Giakkoupis, George and Sauerwald, Thomas and Sun, He and Woelfel, Philipp}, title = {{Low Randomness Rumor Spreading via Hashing}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {314--325}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.314}, URN = {urn:nbn:de:0030-drops-34417}, doi = {10.4230/LIPIcs.STACS.2012.314}, annote = {Keywords: Parallel and Distributed Computing, Randomness, Rumor Spreading} }
Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)
Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing Consensus with the Power of Two Choices. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{doerr_et_al:DagSemProc.09371.6, author = {Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian}, title = {{Stabilizing Consensus with the Power of Two Choices}}, booktitle = {Algorithmic Methods for Distributed Cooperative Systems}, pages = {1--21}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9371}, editor = {S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.6}, URN = {urn:nbn:de:0030-drops-24290}, doi = {10.4230/DagSemProc.09371.6}, annote = {Keywords: Distributed consensus} }
Feedback for Dagstuhl Publishing