SPAA 2006 Call for Papers

18th ACM Symposium on Parallelism in
Algorithms and Architectures

July 30 - August 2, 2006
Cambridge, MA, USA

The 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '05) is sponsored by the ACM Special Interest Groups on Algorithms and Computation Theory (SIGACT) and Computer Architecture (SIGARCH) and organized in cooperation with the European Association for Theoretical Computer Science.

SPAA '06 will feature regular papers, each with a 25-minute talk, and brief announcements, each with a 10-minute talk. The SPAA brief announcements are for brief communications including work in progress or demos.

Expanded and Revitalized Scope:

In a tradition starting in 2001, SPAA defines "parallel" very broadly to encompass any computational system, or model, that can perform multiple operations or tasks simultaneously. As a consequence, contributed papers are sought in ALL areas of parallel algorithms and architectures, and of related fields for SPAA 2006. This includes traditional parallel and distributed algorithms and architectures, plus new aspects including the internet, the web, peer-to-peer networks, sensor networks, quantum and DNA computing, etc.

A renaissance of parallel computing research is on the horizon since: (i) chip multi-cores are the wave of the future for all major hardware vendors, (ii) since 2003 clock frequency of CPUs is hardly advancing any more, (iii) the 6-decade quest for an easy-to-program parallel architecture paradigm is yet to provide a competitive alternative to the serial paradigm. Contributed papers on algorithmics, software and/or hardware that address this emerging renaissance are particularly welcome for SPAA 2006.

Topics of interest include, but are not limited to:

Parallel Computing Massive Parallelism
Parallel Algorithms Cluster Computing and Grid Computing
Parallel Complexity Theory Mobile and Wireless Computing
Parallel Computing and Applications The Internet and the World Wide Web
Models for Parallel and Distributed Computing Sensor Networks
Instruction Level Parallelism and VLSI Satellite and Radio Networks
Routing and Information Dissemination Other Large Networks
Parallel Data Structures Pricing and Equilibria in Networks
Compilers and Tools for Parallel Computing Quantum and DNA Computing
Memory-Aware Algorithms Parallel Data Bases and Data Mining
Supercomputer Architecture and Computing Metacomputing

Conference Presentation:

Regular presentations will be allotted a 25-minute talk and up to 10 pages in the proceedings. This format is intended for contributions reporting original research, submitted exclusively to this conference. Brief announcements will be allotted a 10-minute talk and a one-page abstract (each marked as a brief announcement) in the proceedings. This format is a forum for brief communications, which may be published later in other conferences.


Authors of contributed papers are encouraged to submit their manuscript electronically. More details will follow. The deadlines for electronic submissions are

These are firm deadlines. No extensions will be granted.

Authors who are unable to submit electronically should contact the program chair, Uzi Vishkin, at to receive instructions. Do not send electronic submissions to this email address.

Paper Submission Format:

The cover page should include

  1. title,
  2. authors and affiliation,
  3. postal and e-mail address of the contact author,
  4. a brief abstract describing the content of the paper, and
  5. an indication of whether this is a regular presentation or a brief announcement

If requested by the authors, an extended abstract that is not selected for a regular presentation will also be considered for the SPAA brief announcements. Such a request will not affect the consideration of the paper for a regular presentation.

Submissions of regular presentations should include an introduction understandable to a nonspecialist including motivation and previous work, and a technical exposition directed to a specialist. It should not exceed 10 printed pages in 11-point type or larger (excluding the cover page and the references). More details (such as figures and proofs) may be supplied in a clearly marked appendix to be read at the discretion of the program committee. A camera-ready copy of each accepted paper must prepared according to ACM guidelines for inclusion in the proceedings of the conference.

A submission for the SPAA brief announcements should be no longer than 3 pages on letter-size paper using at least 11-point font.


Authors will be sent notification of acceptance or rejection by e-mail or letter mailed on or before May 15. A camera-ready copy of each accepted abstract must be prepared according to ACM guidelines for inclusion in the proceedings of the conference and must be received by June 1.

Program Chair
Uzi Vishkin, University of Maryland Institute for Advanced Computer Studies (UMIACS)

Program Committee
Michael Bender, SUNY Stony Brook
Babak Falsafi, Carnegie Mellon U.
Anja Feldmann, TU Munich
Ashish Goel, Stanford U.
Robert Kleinberg, U.C. Berkeley and Cornell U.
Elias Koutsoupias, U. of Athens
Geoff Lowney, Intel
Gary Miller, Carnegie Mellon U.
Jaime Moreno, IBM
Vijaya Ramachandran, U. Texas, Austin
John Reif, Duke U.
Christian Scheideler, TU Munich
Baruch Schieber, IBM
Nir Shavit, Tel Aviv U.
Mary Vernon, U. Wisconsin
Roger Wattenhofer, ETH Zurich
Katherine Yelick, U.C. Berkeley and LBNL

Christian Scheideler
Last modified: September 8, 2005