SPAA

It is our great pleasure to welcome you to the 29th ACM Symposium on Parallelism in Algorithms and Architectures -- SPAA 2017. The goal of SPAA is to develop a deeper understanding of parallelism in all its forms, bringing together the theory and practice of parallel computing. Over the last several years, the study of parallelism has significantly extended the state of the art in traditional areas of parallel computing but has also expanded to include various new models of parallel computation, new architectures, new techniques for managing parallelism, and new types of parallel systems -- in particular Spark, Hadoop, as well as MapReduce and its extension Flume. These increasingly important topics are also represented at SPAA this year.

The call for papers attracted 127 submissions. Out of these submissions, the program committee accepted 31 as regular papers (an acceptance rate of only 25%) and 14 as brief announcements (an acceptance rate of only 11%). The committee's decisions in accepting brief announcements were based on the perceived interest of these contributions, with the hope that extended versions of these announcements will be published later in other conferences or journals.

The keynote talks are given by Guy Blelloch (jointly with PODC) and Piotr Indyk.

The best paper award for SPAA 2017 is awarded to:

• Sepehr Assadi and Sanjeev Khanna: Randomized Composable Coresets for Matching an Vertex Cover

• Sudipto Guha, Yi Li and Qin Zhang: Distributed Partial Clustering

Assadi and Khanna consider the problems of finding maximum cardinality matchings and minimum vertex covers over randomized distributed inputs and achieve a constant approximation factor for maximum matching and an O(log n)-approximation factor for vertex cover. Guha, Li, and Zhang consider several fundamental and partial clustering problems such as k-center, k-median, and k-means with outliers in a distributed model, and provide algorithms with commu-nication sublinear of the input size.