SIROCCO 2024

31st International Colloquium On Structural Information and Communication Complexity

May 27th - May 29th, 2024
Vietri sul Mare, Salerno, Italy

Regular papers

• Keren Censor-Hillel, Yuka Machino and Pedro Soto. Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens.
• Leyla Biabiani and Ami Paz. \(k\)-Center Clustering in Distributed Models.
• Panagiota Fatourou, Nikos Giachoudis and George Mallis. Highly-Efficient Persistent FIFO Queues.
• Arnaud Casteigts and Timothée Corsini. In Search of the Lost Tree: Hardness and relaxation of spanning trees in temporal graphs.
• Magnús M. Halldórsson and Dror Rawitz. Distributed Fractional Local Ratio and IS Approximation.
• Tugkan Batu, Amitabh Trehan and Chhaya Trehan. All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.
• Lucianna Kiffer and Rajmohan Rajaraman. Stability of P2P Networks Under Greedy Peering.
• Hongyan Ji and Sriram Pemmaraju. Towards singular optimality in the presence of local initial knowledge.
• Jérémie Chalopin, Shantanu Das and Maria Kokkou. Deterministic Leader Election for Stationary Programmable Matter in the Presence of Obstacles.
• Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, Pierre Fraigniaud and Corentin Travers. Non-Negotiating Distributed Computing.
• Gadi Taubenfeld. Reaching Agreement Among \(k\) out of \(n\) Processes.
• Anaïs Durand, Michel Raynal and Gadi Taubenfeld. Better Sooner Rather Than Later.
• Serafino Cicerone, Alessia Di Fonso, Gabriele Di Stefano, Alfredo Navarra and Francesco Piselli. Mutual visibility in hypercube-like graphs.
• John Augustine, William K. Moses Jr. and Gopal Pandurangan. Awake Complexity of Distributed Minimum Spanning Tree.
• Henrik Lievonen, Timothé Picavet and Jukka Suomela. Distributed Binary Labeling Problems in High-Degree Graphs.
• Irina Kostitsyna, David Liedtke and Christian Scheideler. Universal Coating by 3D Programmable Matter.
• Lelia Blin, Gabriel Le Bouder and Franck Petit. Optimal Memory Requirement for Self-Stabilizing Token Circulation.
• Quentin Bramas, Sayaka Kamei, Anissa Lamani and Sebastien Tixeuil. Stand-Up Indulgent Gathering on Rings.
• Philipp Schneider, Christian Chachin and Ignacio Amores Sesar. An Analysis of Avalanche Consensus.
• Paweł Garncarek, Costas Busch and Dariusz Kowalski. Locally Balanced Allocations under Strong Byzantine Influence.
• Majd Khoury and Keren Censor-Hillel. On Distributed Computation of the Minimum Triangle Edge Transversal.
• Vignesh Manoharan and Vijaya Ramachandran. Computing Replacement Paths in the CONGEST Model.
• Guillermo Toyos-Marfurt and Petr Kuznetsov. On the Bit Complexity of Iterated Memory.
• Colette Johnen, Adnane Khattabi, Alessia Milani and Jennifer Welch. Efficient Wait-Free Linearizable Implementations of Approximate Bounded Counters Using Read-Write Registers.

Brief announcements

• Saswata Jana, Giuseppe F. Italiano, Manas Jyoti Kashyop, Athanasios L. Konstantinidis, Evangelos Kosinas and Partha Sarathi Mandal. Online Drone Scheduling for Last-mile Delivery.
• Yannis Stamatiou, Vasiliki Liagkou, Panagiotis Nastou and Paul Spirakis. On the existence of consensus converging organized groups in large social networks.
• Hugo Rincon Galeana and Ulrich Schmid. Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems.
• Erik van den Akker, Kevin Buchin and Klaus-Tycho Foerster. Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs.
• Keita Nakajima, Kaito Takase and Koichi Wada. Efficient Self-stabilizing Simulations of Energy-Restricted Mobile Robots by Asynchronous Luminous Mobile Robots.
• Emmanuelle Anceaume, Davide Frey and Arthur Rauch. Sharding in permissionless systems in presence of an adaptive adversary.