Program
PROGRAM OF THE 30TH INTERNATIONAL COLLOQUIUM ON STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, SIROCCO 2023
JUNE 6TH TO 9TH, 2023
ALCALA DE HENARES
SPAIN
Monday, June 5
19:00 – 19:30 Conference opening by local authority
19:30 – 20:30 Reception
Tuesday, June 6
9:15 – 9:30 Opening remarks by Sergio Rajsbaum, PC Chair, and Joshua Daymude, Andréa Richa and Christian Scheideler, organizers of Special Models session
Special Models of Computation Session
9:30 – 10:30 Yuval Emek. Chair: Christian Scheideler.
Stone Age Model, Bio-Inspired Models
10:30 – 10:50 Coffee Break
10:50 – 11:50 Frederik Mallmann-Trenn. Chair: Christian Scheideler.
Learning Hierarchically-Structured Concepts in Spiking Neural Networks
11:50 – 12:50 Joshua Daymude. Chair: Andréa Richa.
(Almost) Ten Years of the Amoebot Model of Programmable Matter
12:50 – 14:40 Lunch
14:40 – 15:40 Roger Wattenhofer. Chair: Andréa Richa.
Swarm Intelligence: Does it exist, and how can we find it?
15:40 – 16:10 Coffee Break
SIROCCO 2023
16:10 – 17:10 Session 1. Mobile agents. Chair: Sergio Rajsbaum.
Wednesday, June 7
9:30 – 10:30 Keynote 1: Stefan Schmid. Chair: Sergio Rajsbaum.
Self-adjusting networks
10:30 – 10:50 Coffee Break
10:50 – 11:50 Session 2. Communication Complexity, Distributed Sampling, Packet Forwarding. Chair : Luisa Gargano.
11:50 – 12:50 Session 3. Networks. Chair: Boaz Patt-Shamir.
12:50 – 14:40 Lunch
14:40 – 15:40 Session 4. Robots. Chair : Luisa Gargano.
15:40 – 16:10 Coffee Break
16:10 – 17:10 Keynote 2: Michael Schapira. Chair: Boaz Patt-Shamir.
Towards Learning-Powered Networked Systems
18:10 – 19:10 Business Meeting
Thursday, June 8
9:30 – 10:30 Keynote 3: Bernadette Charron-Bost. Chair: Sergio Rajsbaum.
Computable Functions in Anonymous Networks
10:30 – 10:50 Coffee Break
10:50 – 11:50 Session 5. Distributed graph algorithms. Chair: Alkida Balliu.
11:50 – 12:50 Session 6. Distributed graph algorithms. Chair: Dennis Olivetti.
12:50 – 14:20 Lunch
14:20 – 15:40 Session 7. Blockchains. Chair: Sara Tucci.
15:40 – 16:10 Coffee Break
16:10 – 17:10 Keynote 4: Seth Gilbert. Chair: Sergio Rajsbaum.
To Catch a (Distributed) Thief
18:10 – 21:30 Social excursion and banquet
Friday, June 9
9:20 – 9:30 Introduction to 30th Anniversary and to SIROCCO Prize lecture (Alkida Balliu)
9:30 – 10:30 Boaz Patt-Shamir (SIROCCO Prize lecture). Chair: Alkida Balliu.
Algorithmic recommender systems
10:30 – 11:00 Sara Tucci. Chair: Alkida Balliu.
Leader election in blockchains
11:00 – 11:30 Coffee Break
11:30 – 12:00 Jukka Suomela. Chair: Dennis Olivetti.
What really happened in Helsinki and can you mend it?
12:00 – 12:30 Rotem Oshman. Chair: Dennis Olivetti.
Computationally-bounded local decision
12:30 – 13:00 Michel Raynal. Chair: Dennis Olivetti.
Informatics, distributed computing, and our job: a personal view
13:00 – 14:30 Lunch
14:30 – 15:00 Pierre Fraigniaud. Chair: Sergio Rajsbaum
A perspective on the scientific trajectory of SIROCCO during 30 years
15:00 – 15:30 David Peleg. Chair: Sergio Rajsbaum
Realizing network specifications
15:30 – 16:00 Coffee Break
16:00 – 16:30 Pierluigi Crescenzi. Chair: Alkida Balliu
SIROCCO for dummies
16:30 – 17:00 Nicola Santoro. Chair: Alkida Balliu
SIROCCO at 30
17:00 – 17:15 Closing of the conference
Session details: Papers
Session 1 Mobile agents
- Konstantinos Georgiou, Nikolaos Giachoudis and Evangelos Kranakis. Overcoming Probabilistic Faults in Disoriented Linear Search
- Jared Coleman, Lorand Cheng and Bhaskar Krishnamachari. Search and Rescue on the Line
- Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger and David Wehner. Zero-Memory Graph Exploration with Unknown Inports
Session 2 Communication Complexity, Distributed Sampling, Packet Forwarding
- Lila Fontes, Mathieu Laurière, Sophie Laplante and Alexandre Nolin. The communication complexity of functions with large outputs. (Best Paper Award)
- Sriram Pemmaraju and Joshua Sobel. Exact Distributed Sampling
- Cameron Matsui and Will Rosenbaum. Packet Forwarding with Swaps
Session 3 Networks
- Luisa Gargano and Adele A. Rescigno. Spanning Trees with Few Branch Vertices in Graphs of Bounded Neighborhood Diversity
- Vitaly Aksenov, Anton Paramonov, Iosif Salem and Stefan Schmid. Self-Adjusting Linear Networks with Ladder Demand Graph
- Sam Coy, Artur Czumaj, Christian Scheideler, Philipp Schneider and Julian Werthmann. Routing Schemes for Hybrid Communication Networks in Unit-Disk Graphs
Session 4 Robots
- Abir Islam, Jared Saia and Varsha Dani. Boundary Sketching With Asymptotically Optimal Distance and Rotation (Best Student Paper Award)
- Yuichi Asahiro and Masafumi Yamashita. Compatibility of convergence algorithms for autonomous mobile robots
- Jean-Lou De Carufel, Paola Flocchini, Nicola Santoro and Frederic Simard. Cops & Robber on Periodic Temporal Graphs : Characterization and Improved Bounds
Session 5 Distributed graph algorithms
- Sameep Dahal and Jukka Suomela. Distributed Half-Integral Matching and Beyond (Best Student Paper Award)
- Pierre Fraigniaud, Maël Luce and Ioan Todinca. On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST model
- Tijn de Vos. Minimum Cost Flow in the CONGEST Model
Session 6 Distributed graph algorithms
- Duncan Adamson, Magnús M. Halldórsson and Alexandre Nolin. Distributed Coloring of Hypergraphs
- Yi-Jun Chang. The Energy Complexity of Diameter and Minimum Cut Computation in Bounded-genus Networks
- Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Energy-Efficient Distributed Algorithms for Synchronous Networks
Session 7 Blockchains
- Stefan Schmid, Jakub Svoboda and Michelle Yeo. Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation (Best Paper Award)
- Zeta Avarikioti, Lefteris Kokoris-Kogias, Antoine Desjardins and Roger Wattenhofer. Divide & Scale: Formalization and Roadmap to Robust Sharding
- Zeta Avarikioti, Lioba Heimbach, Roland Schmid, Laurent Vanbever, Roger Wattenhofer and Patrick Wintermeyer. FnF-BFT: A BFT protocol with provable performance under attack
- Ramesh Adhikari and Costas Busch. Lockless Blockchain Sharding with Multiversion Control