SIROCCO 2022 - Paderborn - Germany
Paderborn Photos

Paderborn University Logo

Paderborn SFB 901 Logo

Paderborn University Photo

29th International Colloquium on

Structural Information and Communication Complexity


June 27 - June 29, 2022, Paderborn, Germany

Keynote Speakers

George Giakkoupis

INRIA Rennes, France

George Giakkoupis is a researcher at INRIA in Rennes, France. He obtained his PhD from the University of Toronto in 2009. Before joining INRIA, he was a postdoctoral fellow at University Paris 7, and a PIMS postdoctoral fellow at the University of Calgary. His research focuses on the design and analysis of distributed algorithms, with emphasis on probabilistic algorithms.

Keynote Title:

Simple Efficient Distributed Processes on Graphs


In this talk, I will discuss two examples of simple, local, and distributed random processes on graphs. Both processes are arguably the simplest ones that solve the corresponding problems. The first one is the well-studied edge flip process, which transforms any connected regular graph into a regular expander. I will give an overview of recent results showing that this process is very efficient. The second process constructs a maximal independent set for any given graph. Despite being strikingly simple, this process has received hardly any attention so far. I will present some preliminary results, for certain graph families, and conjecture that the process is efficient on any graph.

Maurice Herlihy

Brown University, USA

Maurice Herlihy has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University and the staff of DEC Cambridge Research Lab. He is the recipient of the 2003 Dijkstra Prize in Distributed Computing, the 2004 Gödel Prize in theoretical computer science, the 2008 ISCA influential paper award, the 2012 Edsger W. Dijkstra Prize, and the 2013 Wallace McDowell award. He received a 2012 Fulbright Distinguished Chair in the Natural Sciences and Engineering Lecturing Fellowship, and he is fellow of the ACM, a fellow of the National Academy of Inventors, the National Academy of Engineering, and the National Academy of Arts and Sciences.

Keynote Title:

Correctness Conditions for Cross-Chain Deals


Modern distributed data management systems face a new challenge: how can autonomous, mutually-distrusting parties cooperate safely and effectively? Addressing this challenge brings up questions familiar from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial.
We propose the notion of a cross-chain deal, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange.

Gillat Kol

Princeton University, USA

Gillat Kol is an assistant professor at the department of Computer Science at Princeton University. Prior to joining Princeton, she was a member in the School of Math at the Institute for Advanced Study (IAS). She earned a PhD and an MSc in Computer Science from the Weizmann Institute. Gillat's research is in the interplay between information theory and computational complexity theory with focus on communication complexity and its many applications.

Keynote Title:

Interactive Coding for Wireless Systems


As wireless systems have become massively popular, theoretical models for such systems (e.g., radio networks, shared blackboard, beeping) have become the topic of numerous works. However, the effect of noise on such models is still not well understood. In this talk, I will survey some of the recent work in the field of interactive error correcting codes for wireless systems, where we attempt to convert an interactive protocol designed assuming a noiseless wireless channel to a protocol that works even if the channel is noisy and corrupts some of the communication.

Christian Scheideler

Paderborn University, Germany

(2022 SIROCCO Prize Awardee)

Christian Scheideler has a Diploma in CS and PhD from Paderborn University. After spending a postdoc year at the Weizmann Institute and obtaining his Habilitation in Paderborn, he spent five years as assistant professor at Johns Hopkins University and three years as associate professor at Technical University of Munich. Since 2009 he is a full professor at Paderborn University and has served as department chair from 2013-2017 and again since 2021. His research interests are distributed algorithms and data structures, randomized algorithms and stochastic processes, robust distributed systems, network theory, and programmable matter.

Keynote Title:

Getting Closer to the Programmable Matter Vision – Extensions of the Amoebot Model


The Amoebot model has been proposed as a model for programmable matter. However, many important issues are not captured in the basic form of this model, including rapid shape transformation, energy, fault-tolerance, and the 3D case. I propose various extensions in my talk. First of all, reconfigurable circuit extension that allows many central problems like leader election, compass alignment, and symmetry checks to be solved significantly faster than in the basic model. This will then provide the base for synchronization and energy distribution which will be important for rapid shape transformation. On top of that, I propose a simple extension to address fault-tolerance. Finally, I also prose an extension to the 3D case. For all of these extensions, I will present first results to illustrate their usefulness.