15th International Colloquium on Structural Information and Communication Complexity


June 17-20, 2008
Villars-sur-Ollon, Switzerland

The program below is still preliminary and subject to modifications.

Facilities are provided by the hotel for watching the football games of the EURO competition!

Tuesday June 17
16h30 Registration
18h00 Welcome reception
Wednesday June 18
09h00 Opening
09h15 Invited speaker: Nicola Santoro

The purpose of this talk is to provide an introduction to "Distributed Computing by Mobile Entities", a wide and wild research field whose exploration has only recently begun. The focus will be in particular on computational models and exemplar problems, their origins, theoretical relevance, and current status.

Nicola Santoro is Professor of Computer Science at Carleton University. He has been involved in distributed computing from the beginning of the field, contributing extensively on the algorithmic aspects. He is a founder of the main theoretical conferences in the field (PODC, DISC, SIROCCO). He has recently authored the book "Design and Analysis of Distributed Algorithms" (Wiley 2007). His current research is on distributed algorithms for mobile agents, autonomous mobile robots, and mobile sensor systems.

10h15 Coffee break
10h45 Session 1 (Chair: Peter Widmayer)
  • Gathering problem of two asynchronous mobile robots with semi-dynamic compasses
    Nobuhiro Inuzuka, Yuichi Tomida, Taisuke Izumi, Yoshiaki Katayama and Koichi Wada
  • Locating and repairing faults in a network with mobile agents
    Colin Cooper, Ralf Klasing and Tomasz Radzik
  • Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots
    Paola Flocchini, David Ilcinkas, Andrzej Pelc and Nicola Santoro
12h15 Lunch (+ SC meeting)
13h45 Session 2 (Chair: Masafumi Yamashita)
  • Average binary long-lived Consensus: quantifying the stabilization role played by memory
    Florent Becker, Rapaport Ivan, Éric Rémila and Sergio Rajsbaum
  • Distributed Approximation Algorithm for Resource Clustering
    Olivier Beaumont, Nicolas Bonichon, Philippe Duchon and Hubert Larcheveque
  • Sharpness: A tight condition for Throughput Scalability
    Augustin Chaintreau
15h15 Coffee break
15h45 Session 3 (Chair: Andrzej Pelc)
  • Discovery of Network Properties with All-Shortest-Paths Queries
    Davide Bilo, Thomas Erlebach, Matus Mihalak and Peter Widmayer
  • Recovering the Long Range Links in Augmented Graphs
    Pierre Fraigniaud, Emmanuelle Lebhar and Zvi Lotker
  • Computing Frequent Elements using Gossip
    Bibudh Lahiri and Srikanta Tirthapura
17h15 Business meeting and open discussion
19h30 Conference dinner
Thursday June 19
08h45 Invited speaker: Boaz Patt-Shamir

In recommendation systems (e.g., for books or movies), the system tracks which product each user liked in the past, and tries to deduce which other products the user is likely to be satisfied with. Recommendation systems can help users who share many preferences with many other users by means of "collaborative filtering." Most current approaches to on-line recommendation systems employ algebraic techniques such as Singular Value Decomposition (SVD), which are computationally intensive and, more important, often applicable only under some additional strong conditions. We overview a new approach which demonstrates that simple combinatorial algorithms can make good recommendations that guarantee that the cost per user is only polylogarithmic factor over optimal, without restricting the allowed inputs.

Boaz Patt-Shamir has received his BSc , MSc and PhD from Tel Aviv University, Weizmann Institute and MIT, respectively. He taught in Northeastern University and MIT, and since 1997 he is with the Department of Electrical Engineering in Tel Aviv University, where he directs the Laboratory of Advanced Communication. In 2002-2004 he spent an extended sabbatical in HP Labs in Cambridge (Mass.), where he developed an interest in recommendation systems. His other research interests include classical distributed algorithms, algorithms for communication networks, and self-stabilization.

09h45 Coffee break
10h15 Session 4 (Chair: Paola Flocchini)
  • Maintaining Consistent Transactional States Without a Global Clock
    Hillel Avni and Nir Shavit
  • Equal-Area Locus-Based Convex Polygon Decomposition
    David Adjiashvili and David Peleg
  • On the power of local orientations
    Monika Steinová
  • Best Effort and Priority Queuing Policies for Buffered Crossbar Switches
    Alex Kesselman, Kirill Kogan and Michael Segal
12h15 Lunch
13h45 Session 5 (Chair: Shmuel Zaks)
  • Word-of-Mouth: Rumor Dissemination in Social Networks
    Jan Kostka, Yvonne Anne Oswald and Roger Wattenhofer
  • Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games
    Konstantinos Kollias
  • Computing Approximate Nash Equilibria in Network Congestion Games
    Andreas Emil Feldmann, Heiko Roeglin and Berthold Voecking
15h15 Coffee break
16h00 Social event and dinner
Friday June 20
08h45 Session 6 (Chair: Shay Kutten)
  • On the Performance of Beauquier and Debas' Self-Stabilizing Algorithm for Mutual Exclusion
    Viacheslav Chernoy, Mordechai Shalom and Shmuel Zaks
  • Self-stabilizing Cuts in Synchronous Networks
    Thomas Sauerwald and Dirk Sudholt
  • Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs
    Toshimitsu Masuzawa and Sebastien Tixeuil
10h15 Coffee break
10h45 Session 7 (Chair: Pierre Fraigniaud)
  • Gathering with Minimum Delay in Sensor Networks
    Jean-Claude Bermond, Luisa Gargano and Adele Rescigno
  • Centralized communication in radio networks with strong interference
    František Galcík
  • Fast Radio Broadcasting with Advice
    David Ilcinkas, Dariusz Kowalski and Andrzej Pelc
12h15 Closing lunch