LIPIcs, Volume 246
DISC 2022, October 25-27, 2022, Augusta, Georgia, USA
Editors: Christian Scheideler
Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Shuma Kumamoto, Shuji Kijima, and Tomoyuki Shirai. The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kumamoto_et_al:LIPIcs.AofA.2024.22, author = {Kumamoto, Shuma and Kijima, Shuji and Shirai, Tomoyuki}, title = {{The Recurrence/Transience of Random Walks on a Bounded Grid in an Increasing Dimension}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.22}, URN = {urn:nbn:de:0030-drops-204577}, doi = {10.4230/LIPIcs.AofA.2024.22}, annote = {Keywords: Random walk, dynamic graph, recurrence, transience, coupling} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Andréa Werneck Richa. Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots (Invited Talk). In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{richa:LIPIcs.SAND.2024.3, author = {Richa, Andr\'{e}a Werneck}, title = {{Algorithmic Programmable Matter: From Local Markov Chains to "Dumb" Robots}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.3}, URN = {urn:nbn:de:0030-drops-198811}, doi = {10.4230/LIPIcs.SAND.2024.3}, annote = {Keywords: Programmable matter, Self-organizing particle systems, Biologically-inspired distributed algorithms, Local Markov chains, Emergent collective behavior} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Kristian Hinnenthal, David Liedtke, and Christian Scheideler. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hinnenthal_et_al:LIPIcs.SAND.2024.15, author = {Hinnenthal, Kristian and Liedtke, David and Scheideler, Christian}, title = {{Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {15:1--15:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.15}, URN = {urn:nbn:de:0030-drops-198930}, doi = {10.4230/LIPIcs.SAND.2024.15}, annote = {Keywords: Programmable Matter, Shape Formation, 3D Model, Finite Automaton} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Andreas Padalkin, Manish Kumar, and Christian Scheideler. Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{padalkin_et_al:LIPIcs.SAND.2024.18, author = {Padalkin, Andreas and Kumar, Manish and Scheideler, Christian}, title = {{Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.18}, URN = {urn:nbn:de:0030-drops-198963}, doi = {10.4230/LIPIcs.SAND.2024.18}, annote = {Keywords: programmable matter, modular robot system, reconfiguration, locomotion} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Siddharth Gupta, Marc van Kreveld, Othon Michail, and Andreas Padalkin. Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 26:1-26:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gupta_et_al:LIPIcs.SAND.2024.26, author = {Gupta, Siddharth and van Kreveld, Marc and Michail, Othon and Padalkin, Andreas}, title = {{Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {26:1--26:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.26}, URN = {urn:nbn:de:0030-drops-199044}, doi = {10.4230/LIPIcs.SAND.2024.26}, annote = {Keywords: Modular robots, Collision detection, Computational Geometry, Complexity} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 1-790, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{scheideler:LIPIcs.DISC.2022, title = {{LIPIcs, Volume 246, DISC 2022, Complete Volume}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {1--790}, 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}, URN = {urn:nbn:de:0030-drops-171908}, doi = {10.4230/LIPIcs.DISC.2022}, annote = {Keywords: LIPIcs, Volume 246, DISC 2022, Complete Volume} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{scheideler:LIPIcs.DISC.2022.0, author = {Scheideler, Christian}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {0:i--0:xx}, 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.0}, URN = {urn:nbn:de:0030-drops-171917}, doi = {10.4230/LIPIcs.DISC.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Sepehr Assadi. Graph Coloring, Palette Sparsification, and Beyond (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi:LIPIcs.DISC.2022.1, author = {Assadi, Sepehr}, title = {{Graph Coloring, Palette Sparsification, and Beyond}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-171920}, doi = {10.4230/LIPIcs.DISC.2022.1}, annote = {Keywords: Graph coloring, Palette Sparsification, Sublinear Algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Roberto Baldoni. Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science? (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{baldoni:LIPIcs.DISC.2022.2, author = {Baldoni, Roberto}, title = {{Managing the Cyber Risk in a Decoupled World: Does This Bring Potential Opportunities in Computer Science?}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-171931}, doi = {10.4230/LIPIcs.DISC.2022.2}, annote = {Keywords: Supply chain decoupling, technology risk, cyber attacks, computing paradigms and methodologies} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Jennifer L. Welch. Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{welch:LIPIcs.DISC.2022.3, author = {Welch, Jennifer L.}, title = {{Using Linearizable Objects in Randomized Concurrent Programs}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {3:1--3:1}, 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.3}, URN = {urn:nbn:de:0030-drops-171946}, doi = {10.4230/LIPIcs.DISC.2022.3}, annote = {Keywords: Concurrent objects, strong linearizability, impossibility proofs, message-passing systems, randomized algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{albouy_et_al:LIPIcs.DISC.2022.4, author = {Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois}, title = {{Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {4:1--4:22}, 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.4}, URN = {urn:nbn:de:0030-drops-171953}, doi = {10.4230/LIPIcs.DISC.2022.4}, annote = {Keywords: Reliable Broadcast, Byzantine Faults, Synchronous Systems, Good-case latency, Deterministic Algorithms} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss. Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{amram_et_al:LIPIcs.DISC.2022.5, author = {Amram, Gal and Hayoun, Avi and Mizrahi, Lior and Weiss, Gera}, title = {{Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {5:1--5:20}, 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.5}, URN = {urn:nbn:de:0030-drops-171964}, doi = {10.4230/LIPIcs.DISC.2022.5}, annote = {Keywords: Snapshot, Linearizability, Verification, Formal Methods} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anagnostides_et_al:LIPIcs.DISC.2022.6, author = {Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis}, title = {{Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {6:1--6:20}, 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.6}, URN = {urn:nbn:de:0030-drops-171978}, doi = {10.4230/LIPIcs.DISC.2022.6}, annote = {Keywords: Distributed algorithms, Laplacian solvers, low-congestion shortcuts} }