Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Charlotte Out, Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Rumors with Changing Credibility. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 86:1-86:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{out_et_al:LIPIcs.ITCS.2024.86, author = {Out, Charlotte and Rivera, Nicol\'{a}s and Sauerwald, Thomas and Sylvester, John}, title = {{Rumors with Changing Credibility}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {86:1--86:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.86}, URN = {urn:nbn:de:0030-drops-196149}, doi = {10.4230/LIPIcs.ITCS.2024.86}, annote = {Keywords: Rumor spreading, epidemic algorithms, "fake news"} }
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 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Natalie Sauerwald, Yihang Shen, and Carl Kingsford. Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sauerwald_et_al:LIPIcs.WABI.2019.23, author = {Sauerwald, Natalie and Shen, Yihang and Kingsford, Carl}, title = {{Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.23}, URN = {urn:nbn:de:0030-drops-110537}, doi = {10.4230/LIPIcs.WABI.2019.23}, annote = {Keywords: topological data analysis, chromosome structure, Hi-C, topologically associating domains} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{enright_et_al:LIPIcs.MFCS.2019.57, author = {Enright, Jessica and Meeks, Kitty and Mertzios, George B. and Zamaraev, Viktor}, title = {{Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.57}, URN = {urn:nbn:de:0030-drops-110010}, doi = {10.4230/LIPIcs.MFCS.2019.57}, annote = {Keywords: Temporal networks, spreading processes, graph modification, parameterised complexity} }
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} }
Feedback for Dagstuhl Publishing