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

18:00 – 19:00 Registration at Colegio San Ildefonso.

19:00 – 19:30 Conference opening by Juan Ramon Velasco, Vicerrector de Innovación Docente y Transformación Digital, Universidad de Alcalá, at the Capilla of Colegio San Ildefonso.

19:30 – 20:30 Reception at Colegio San Ildefonso.

Tuesday, June 6

8:30 – 9:15 Registration at Facultad de Filosofía y Letras (aka Colegio de Málaga).

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 (at Facultad de Filosofía y Letras)

9:30 – 10:30 Yuval Emek. Chair: Christian Scheideler.

A Decade of Stone Age Distributed Computing [slides]

10:30 – 10:50 Coffee Break at the patio of Facultad de Filosofía y Letras

10:50 – 11:50 Frederik Mallmann-Trenn. Chair: Christian Scheideler.

Learning Hierarchically-Structured Concepts in Spiking Neural Networks [slides]

11:50 – 12:50 Joshua Daymude. Chair: Andréa Richa.

(Almost) Ten Years of the Amoebot Model of Programmable Matter [slides]

12:50 – 14:40 Lunch at Colegio San Ildefonso

14:40 – 15:40 Roger Wattenhofer. Chair: Andréa Richa.

Swarm Intelligence: Does it exist, and how can we find it? [slides]

15:40 – 16:10 Coffee Break at Colegio San Ildefonso

SIROCCO 2023 (at Facultad de Filosofía y Letras)

16:10 – 17:10 Session 1. Mobile agents. Chair: Sergio Rajsbaum.  

  • Konstantinos Georgiou, Nikolaos Giachoudis and Evangelos Kranakis. Overcoming Probabilistic Faults in Disoriented Linear Search [slides]
  • 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

18:30 – 20:00 Guided city visit or university visit (two groups)

Wednesday, June 7

SIROCCO 2023 (at Facultad de Filosofía y Letras)

9:30 – 10:30 Keynote 1: Stefan Schmid. Chair: Sergio Rajsbaum.

Self-adjusting networks [slides]

10:30 – 10:50 Coffee Break at the patio of Facultad de Filosofía y Letras

10:50 – 11:50 Session 2. Communication Complexity, Distributed Sampling, Packet Forwarding. Chair : Luisa Gargano.

  • Lila Fontes, Mathieu Laurière, Sophie Laplante and Alexandre Nolin.  The communication complexity of functions with large outputs. (Best Paper Award) [slides]
  • Sriram Pemmaraju and Joshua Sobel. Exact Distributed Sampling [slides]
  • Cameron Matsui and Will Rosenbaum. Packet Forwarding with Swaps

11:50 – 12:50 Session 3. Networks. Chair: Boaz Patt-Shamir.

  • Luisa Gargano and Adele A. Rescigno. Spanning Trees with Few Branch Vertices in Graphs of Bounded Neighborhood Diversity [slides]
  • 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 [slides]

12:50 – 14:40 Lunch at Colegio San Ildefonso

14:40 – 15:40 Session 4. Robots. Chair : Luisa Gargano.

  • Abir Islam, Jared Saia and Varsha Dani. Boundary Sketching With Asymptotically Optimal Distance and Rotation (Best Student Paper Award) [slides]
  • 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

15:40 – 16:10 Coffee Break at Colegio San Ildefonso

16:10 – 17:10 Keynote 2: Michael Schapira. Chair: Boaz Patt-Shamir.

Towards Learning-Powered Networked Systems

17:25 – 18:25 Business Meeting

Thursday, June 8

SIROCCO 2023 (at Facultad de Filosofía y Letras)

9:30 – 10:30 Keynote 3: Bernadette Charron-Bost. Chair: Sergio Rajsbaum.

Computable Functions in Anonymous Networks

10:30 – 10:50 Coffee Break at the patio of Facultad de Filosofía y Letras

10:50 – 11:50 Session 5. Distributed graph algorithms. Chair: Alkida Balliu.

  • 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 [slides]
  • Tijn de Vos. Minimum Cost Flow in the CONGEST Model [slides]

11:50 – 12:50 Session 6. Distributed graph algorithms. Chair: Dennis Olivetti. 

  • Duncan Adamson, Magnús M. Halldórsson and Alexandre Nolin. Distributed Coloring of Hypergraphs [slides]
  • Yi-Jun Chang. The Energy Complexity of Diameter and Minimum Cut Computation in Bounded-genus Networks [slides]
  • Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. Energy-Efficient Distributed Algorithms for Synchronous Networks

12:50 – 14:20 Lunch at Colegio San Ildefonso

14:20 – 15:40 Session 7. Blockchains. Chair: Sara Tucci.

  • Stefan Schmid, Jakub Svoboda and Michelle Yeo. Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation (Best Paper Award) [slides]
  • Zeta Avarikioti, Lefteris Kokoris-Kogias, Antoine Desjardins and Roger Wattenhofer. Divide & Scale: Formalization and Roadmap to Robust Sharding [slides]
  • 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

15:40 – 16:10 Coffee Break at Colegio San Ildefonso

16:10 – 17:10 Keynote 4: Seth Gilbert. Chair: Sergio Rajsbaum.

To Catch a (Distributed) Thief

18:30 – 20:00 Guided city visit or university visit (two groups)

20:30 – 23:00 Banquet at Restarurante La Cúpula

Friday, June 9

30th Anniversary of SIROCCO Session (at Facultad de Filosofía y Letras)

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 at the patio of Facultad de Filosofía y Letras

11:30 – 12:00 Jukka Suomela. Chair: Dennis Olivetti.

What really happened in Helsinki and can you mend it? [slides]

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 at Colegio San Ildefonso

14:30 – 15:00 Pierre Fraigniaud. Chair: Sergio Rajsbaum

A perspective on the scientific trajectory of SIROCCO during 30 years [slides]

15:00 – 15:30 David Peleg. Chair: Sergio Rajsbaum

Realizing network specifications

15:30 – 16:00 Coffee Break at Colegio San Ildefonso

16:00 – 16:30 Pierluigi Crescenzi. Chair: Alkida Balliu

SIROCCO for dummies [slides]

16:30 – 17:00 Nicola Santoro. Chair: Alkida Balliu

SIROCCO at 30

17:00 – 17:15 Closing of the conference