ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The program consists of several invited talks, which are aimed at the general DISC audience.

ADGA 2015 will be held on **Tuesday, 6 October 2015** in **Tokyo, Japan**, and will be co-located with **DISC 2015**. The workshop will be chaired by **Keren Censor-Hillel**.

For information about venue and registration, please go to the DISC 2015 website.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series.

**Schedule**:

**(Takes place in the HOUHOU room on the 4th floor at the Arcadia Ichigaya Hotel)**

09:00-10:00 **Merav Parter:
Fault Resilient Graph Structures slides**

10:00-10:15 Coffee Break

10:15-11:15

**Seth Gilbert:**

Bob the Builder vs. Fix-it-Felix: maintaining overlays in dynamic graphs slides

Bob the Builder vs. Fix-it-Felix: maintaining overlays in dynamic graphs slides

11:15-11:30 Coffee Break

11:30-12:30

**Stefan Schmid:**

The Zen of Consistent Distributed Network Updates slides

The Zen of Consistent Distributed Network Updates slides

12:30-14:00 Lunch

14:00-15:00 **Dana Ron:
On Centralized Sublinear Algorithms and Some Relations to Distributed Computing slides**

15:00-15:15 Coffee Break

15:15-16:15

**Sriram Pemmaraju:**

Designing Algorithms for the Congested Clique slides

Designing Algorithms for the Congested Clique slides

16:15-16:30 Coffee Break

16:30-17:30

**Peter Robinson:**

Distributed Computation of Large-scale Graph Problems slides

Distributed Computation of Large-scale Graph Problems slides

18:00-21:00 ** DISC reception **(Arcadia Ichigaya Hotel)

**Invited Speakers and Abstracts:**

**Seth Gilbert
**National University of Singapore

**Bob the Builder vs. Fix-it-Felix: maintaining overlays in dynamic graphs**

**Fault Resilient Graph Structures**

**Sriram V. Pemmaraju**

The University of Iowa

** Designing Algorithms for the Congested Clique**

In the last 5 years, we have seen a flurry of research on the design of algorithms in a simple distributed model of computing that has now come to be known as the \textit{congested clique} model. As the name suggests, the underlying communication network is a clique with the restriction that in each round, each communication link can carry a single message of size O(log n) bits (in each direction). Many classical graph problems such as minimum spanning tree, shortest paths, and graph coloring have been considered in the congested clique setting. Typically, the input to these problems is a subgraph of underlying clique such that each node initially only knows the edges incident on it. In this setting, even though n^2 messages can be exchanged in a round over the network, each node can only receive n messages, making it impossible for any node to quickly have access to the entire input.

In this talk, I will use example problems to sketch some techniques for designing fast algorithms in the congested clique model. I will then make connections between congested clique and well known models of parallel and distributed computing such as MapReduce and the BSP model, and the more recently introduced k-machine model. For these connections to be fruitful, one needs to design algorithms in the congested clique that are fast \textit{and} have small message complexity. I will end the talk by describing recent efforts at designing fast congested clique algorithms with low message complexity.

**Peter Robinson**

Queen’s University Belfast

**Distributed Computation of Large-scale Graph Problems**

During the academic year 2003-4 she was a fellow at the Radcliffe Institute for Advanced Study, Harvard University.

Her research focuses on Sublinear Approximation algorithms and in particular Property Testing.

**On Centralized Sublinear Algorithms and Some Relations to Distributed Computing**

(1) The average degree and the number of triangles

(2) The weight of a minimum spanning tree

(3) The size of a minimum vertex cover and a maximum matching

(4) The number of edges that should be added/removed in order to obtain various propertiesThe design of some of these algorithms is inspired and/or related to distributed network algorithms.

**Stefan Schmid**

TU Berlin & T-Labs, Berlin, Germany

**The Zen of Consistent Distributed Network Updates**