Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 11:1-11:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cambus_et_al:LIPIcs.DISC.2023.11, author = {Cambus, M\'{e}lanie and Kuhn, Fabian and Pai, Shreyas and Uitto, Jara}, title = {{Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.11}, URN = {urn:nbn:de:0030-drops-191378}, doi = {10.4230/LIPIcs.DISC.2023.11}, annote = {Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. Conditionally Optimal Parallel Coloring of Forests. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 23:1-23:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{grunau_et_al:LIPIcs.DISC.2023.23, author = {Grunau, Christoph and Latypov, Rustam and Maus, Yannic and Pai, Shreyas and Uitto, Jara}, title = {{Conditionally Optimal Parallel Coloring of Forests}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.23}, URN = {urn:nbn:de:0030-drops-191494}, doi = {10.4230/LIPIcs.DISC.2023.23}, annote = {Keywords: massively parallel computation, coloring, forests, optimal} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{akbari_et_al:LIPIcs.ICALP.2023.10, author = {Akbari, Amirreza and Eslami, Navid and Lievonen, Henrik and Melnyk, Darya and S\"{a}rkij\"{a}rvi, Joona and Suomela, Jukka}, title = {{Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {10:1--10:20}, 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.10}, URN = {urn:nbn:de:0030-drops-180627}, doi = {10.4230/LIPIcs.ICALP.2023.10}, annote = {Keywords: Online computation, spatial advice, distributed algorithms, computational complexity} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup over Locality in MPC with Optimal Memory. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 9:1-9:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{balliu_et_al:LIPIcs.DISC.2022.9, author = {Balliu, Alkida and Brandt, Sebastian and Fischer, Manuela and Latypov, Rustam and Maus, Yannic and Olivetti, Dennis and Uitto, Jara}, title = {{Exponential Speedup over Locality in MPC with Optimal Memory}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.9}, URN = {urn:nbn:de:0030-drops-172003}, doi = {10.4230/LIPIcs.DISC.2022.9}, annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 15:1-15:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cambus_et_al:LIPIcs.DISC.2021.15, author = {Cambus, M\'{e}lanie and Choo, Davin and Miikonen, Havu and Uitto, Jara}, title = {{Massively Parallel Correlation Clustering in Bounded Arboricity Graphs}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {15:1--15:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.15}, URN = {urn:nbn:de:0030-drops-148173}, doi = {10.4230/LIPIcs.DISC.2021.15}, annote = {Keywords: MPC Algorithm, Correlation Clustering, Bounded Arboricity} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Yannic Maus and Jara Uitto. Efficient CONGEST Algorithms for the Lovász Local Lemma. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 31:1-31:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{maus_et_al:LIPIcs.DISC.2021.31, author = {Maus, Yannic and Uitto, Jara}, title = {{Efficient CONGEST Algorithms for the Lov\'{a}sz Local Lemma}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {31:1--31:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.31}, URN = {urn:nbn:de:0030-drops-148333}, doi = {10.4230/LIPIcs.DISC.2021.31}, annote = {Keywords: distributed graph algorithms, CONGEST, Lov\'{a}sz Local Lemma, locally checkable labelings} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Sebastian Brandt, Rustam Latypov, and Jara Uitto. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 50:1-50:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{brandt_et_al:LIPIcs.DISC.2021.50, author = {Brandt, Sebastian and Latypov, Rustam and Uitto, Jara}, title = {{Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {50:1--50:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.50}, URN = {urn:nbn:de:0030-drops-148521}, doi = {10.4230/LIPIcs.DISC.2021.50}, annote = {Keywords: Distributed computing, Locally checkable labeling problems, Trees, Massively Parallel Computation, Sublinear memory, 3-coloring} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Sebastian Brandt, Julian Portmann, and Jara Uitto. Tight Bounds for Deterministic High-Dimensional Grid Exploration. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 13:1-13:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{brandt_et_al:LIPIcs.DISC.2020.13, author = {Brandt, Sebastian and Portmann, Julian and Uitto, Jara}, title = {{Tight Bounds for Deterministic High-Dimensional Grid Exploration}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {13:1--13:16}, 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.13}, URN = {urn:nbn:de:0030-drops-130911}, doi = {10.4230/LIPIcs.DISC.2020.13}, annote = {Keywords: Mobile agents, finite automata, grid search} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 40:1-40:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{brandt_et_al:LIPIcs.DISC.2020.40, author = {Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara}, title = {{Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {40:1--40:3}, 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.40}, URN = {urn:nbn:de:0030-drops-131182}, doi = {10.4230/LIPIcs.DISC.2020.40}, annote = {Keywords: distributed algorithms, graph problems, semi-matching} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Distributed Recoloring. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 12:1-12:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bonamy_et_al:LIPIcs.DISC.2018.12, author = {Bonamy, Marthe and Ouvrard, Paul and Rabie, Mika\"{e}l and Suomela, Jukka and Uitto, Jara}, title = {{Distributed Recoloring}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.12}, URN = {urn:nbn:de:0030-drops-98012}, doi = {10.4230/LIPIcs.DISC.2018.12}, annote = {Keywords: Distributed Systems, Graph Algorithms, Local Computations} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Sebastian Brandt, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 13:1-13:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{brandt_et_al:LIPIcs.DISC.2018.13, author = {Brandt, Sebastian and Uitto, Jara and Wattenhofer, Roger}, title = {{A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.13}, URN = {urn:nbn:de:0030-drops-98029}, doi = {10.4230/LIPIcs.DISC.2018.13}, annote = {Keywords: Finite automata, Graph exploration, Mobile robots} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Sebastian Brandt, Seth Pettie, and Jara Uitto. Fine-grained Lower Bounds on Cops and Robbers. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 9:1-9:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{brandt_et_al:LIPIcs.ESA.2018.9, author = {Brandt, Sebastian and Pettie, Seth and Uitto, Jara}, title = {{Fine-grained Lower Bounds on Cops and Robbers}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.9}, URN = {urn:nbn:de:0030-drops-94725}, doi = {10.4230/LIPIcs.ESA.2018.9}, annote = {Keywords: Cops and Robbers} }
Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved Distributed Degree Splitting and Edge Coloring. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 19:1-19:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{ghaffari_et_al:LIPIcs.DISC.2017.19, author = {Ghaffari, Mohsen and Hirvonen, Juho and Kuhn, Fabian and Maus, Yannic and Suomela, Jukka and Uitto, Jara}, title = {{Improved Distributed Degree Splitting and Edge Coloring}}, booktitle = {31st International Symposium on Distributed Computing (DISC 2017)}, pages = {19:1--19:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-053-8}, ISSN = {1868-8969}, year = {2017}, volume = {91}, editor = {Richa, Andr\'{e}a}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.19}, URN = {urn:nbn:de:0030-drops-79794}, doi = {10.4230/LIPIcs.DISC.2017.19}, annote = {Keywords: Distributed Graph Algorithms, Degree Splitting, Edge Coloring, Discrepancy} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Sebastian Brandt, Yuval Emek, Jara Uitto, and Roger Wattenhofer. A Tight Lower Bound for the Capture Time of the Cops and Robbers Game. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 82:1-82:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{brandt_et_al:LIPIcs.ICALP.2017.82, author = {Brandt, Sebastian and Emek, Yuval and Uitto, Jara and Wattenhofer, Roger}, title = {{A Tight Lower Bound for the Capture Time of the Cops and Robbers Game}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {82:1--82:13}, 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.82}, URN = {urn:nbn:de:0030-drops-74134}, doi = {10.4230/LIPIcs.ICALP.2017.82}, annote = {Keywords: cops and robbers, capture time, lower bound} }
Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{langner_et_al:LIPIcs.OPODIS.2015.9, author = {Langner, Tobias and Keller, Barbara and Uitto, Jara and Wattenhofer, Roger}, title = {{Overcoming Obstacles with Ants}}, booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-98-9}, ISSN = {1868-8969}, year = {2016}, volume = {46}, editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.9}, URN = {urn:nbn:de:0030-drops-66005}, doi = {10.4230/LIPIcs.OPODIS.2015.9}, annote = {Keywords: Mobile agents, algorithms, treasure search} }
Feedback for Dagstuhl Publishing