Arrivals
The arrival day is Sunday, August 25. The check-in and welcome reception will be open from 17:00 to 21:00.
Program
Update: all plenary sessions will be held in the Museum room in the Castle.
Time | Aug 26, Monday | Aug 27, Tuesday | Aug 28, Wednesday | Aug 29, Thursday | Aug 30, Friday |
---|---|---|---|---|---|
7:30–9:00 | breakfast | breakfast | breakfast | breakfast | breakfast |
9:00–9:45 | introduction | Marcel Roeloffzen "Kinetic data structures" | 9:00–9:40 status report |
status report | status report |
Rik Sarkar "Range counting in planar graphs" | 9:40–10:00 Dorian Rudolf "Shape formation in 3D" |
||||
9:45–10:30 | Nicola Santoro | Alfredo Navarra "Pattern formation with fixed points in the plane" | 10:00–10:20 Vera Sacristán "Self-reconfiguring modular robots" |
working session | |
Christian Schindelhauer "Algorithms for self-calibrating localization" | 10:20–10:40 Christian Scheideler "LP-type problems" |
||||
10:30–11:00 | coffee break | coffee break | 10:45–11:15 coffee break |
coffee break | coffee break |
11:00–11:45 | Subhash Suri | Valentin Polishchuk "Motion conflict graphs" | 11:15–12:30 working session |
working session | wrap up session |
Fabian Kuhn TBA | |||||
11:45–12:30 | Christian Scheideler | Friedhelm Meyer auf der Heide TBA | |||
Pierre Fraigniaud "A Topological Perspective on Distributed Computing" | |||||
12:30–14:00 | lunch | lunch | lunch | lunch | lunch |
14:00–14:45 | Sándor Fekete | working session | excursion dinner at 20:00 at Restaurant Casa Artusi in Forlimpopoli |
working session | departures |
14:45–15:30 | Irina Kostitsyna | ||||
15:30–16:00 | coffee break | coffee break | coffee break | ||
16:00–16:45 | open problem session | working session | working session | ||
16:45–17:30 | |||||
19:30– ... | dinner at Cà de Bé | dinner at Enoteca Bistrot Colonna | dinner at La Grotta Bertinoro |
Tutorials
• Distributed geometric algorithms by mobile robots
Speaker: Nicola Santoro
Time: Monday, 9:45–10:30
Abstract: Within distributed computing, intensive investigations are being carried out on the computational and complexity issues arising in systems of mobile computational entities operating in Euclidean spaces. Totally autonomous, the entities, called robots and viewed as points, operate in Look-Compute-Move cycles {perceiving the position of the other robots, executing the same protocol to compute a destination point, and moving there), cooperating to solve some problems. Typical problems include pattern formation, gathering, scattering. The main algorithmic tools in the design of the solution protocols are geometric and the settings are fully distributed. Because the entities are mobile, the field is about kinematic geometry and design and analysis of distributed protocols. In this talk, I will describe the basic computational models, and overview some slgorithmic results as a way of explanation.
• Geometric constraint removal problems
Speaker: Subhash Suri
Time: Monday, 11:00–11:45
Abstract: Constraint removal or relaxation is a natural approach in optimization when the solution is either infeasible or unsatisfactory. This talk will explore the complexity and approximability of the following three problems in this framework:
- Shortest paths with obstacle removal,
- Minimum color paths, and
- Maximum exposure.
• Hybrid networks
Speaker: Christian Scheideler
Time: Monday, 14:00–14:45
Abstract: I will introduce a new communication model, called hybrid network, in which the nodes have the choice between two communication modes: a local mode that allows them to exchange messages with nearby nodes, and a global mode where communication between any pair of nodes is possible, but the amount of communication is limited. This can be motivated, for instance, by wireless networks in which we combine direct device-to-device communication with communication via the cellular infrastructure. I will show how to quickly build up a low-diameter, low-degree network of global edges (i.e., connections established via the global communication mode) on top of any network of local edges (i.e., connections given by the local communication mode) so that various problems such as computing minimum spanning trees and shortest paths can be solved much more efficiently than by just using the local edges.
• From nano to Mega: Coordinating swarms of objects at extreme dimensions
Speaker: Sándor Fekete
Time: Monday, 14:45–15:30
Abstract:
Coordinating and reconfiguring arrangements of objects poses important questions
at various dimensions, ranging from tiny particles all the way to far-away satellite swarms.
Ironically, systems of these very small and very large distances share a fundamental property:
It becomes difficult to use "external" computation, in which a powerful central computing device
is provided with input about the system, and output is fed back into the system. Instead, it
becomes important to consider "internal" computation, in which algorithms and execution
remain within the system itself, even if that comes at the expense of processing power.
Additional challenges arise from coordinating the parallel motion of larger and larger sets of
objects in a globally efficient manner.
This talk will describe a variety of algorithmic approaches to coordination and reconfiguration
challenges. These include (1) Algorithmic aspects of "programmable matter", i.e., algorithmic
methods for controlling structures that can change their physical properties (shape, density,
moduli, conductivity, optical properties, etc.) in a programmable fashion. (2) Optimization methods
for coordinated motion planning, in which a large swarm of objects needs to be reorganized in a
minimum amount of time. (3) Distributed approaches for coordinating the downlink activities of
satellite swarms with more than 1000 spacecraft.
• Hybrid programmable matter
Speaker: Irina Kostitsyna
Time: Monday, 11:45–12:30
Abstract: Recent developments in nanotechnology and the potential significance of its application to various areas, such as electronics, medicine, and energy, spiked an interest in computer science community for developing theoretical models of programmable matter. Programmable matter is any matter that has the ability to change its physical properties (like shape, density, moduli, conductivity, optical properties, etc.) based on user input or autonomous sensing. So far, only very primitive forms of adaptive programmable matter have been realized, and now is the right time to start developing fundamental models and approaches for the algorithmic study of programmable matter. A few models for programmable matter have been proposed already. For example, in tile self-assembly model semi-passive tiles attach to each other following certain rules growing into larger and larger structures, thus performing computation. Dealing with passive elements only does not allow one yet to create smart, adaptive materials. Thus, other suggested models consider computation on nanoscale by active agents. However, one can imagine, that for many practical problems, most of the nanostructures will remain static most of the time, with only small changes occurring over some short periods of time. In this case using active agents as static building blocks seems excessive. We envision a hybrid model, where the structures consist of static nanoscale materials which can be reconfigured by a comparatively small set of active agents. Thus, motivated by the problem of manipulating nanoscale materials by nanoscale active agents, we introduce a new theoretical model for programmable matter which combines active and passive agents.