SPAA

The papers in this volume were presented at the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), held on July 30 through August 2, 2006, in Cambridge, MA, USA. The conference was 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 (EATCS). Financial support was provided by the Akamai, Intel, Google, and Sun Microsystems Corporations, and the program committee meeting was partially supported by the University of Maryland Institute for Advanced Computer Studies (UMIACS).The forty-six contributed technical presentations that appeared at the Conference were selected by the program committee after electronic discussion and a meeting of one and a half day. The technical presentations were selected out of one hundred and two submitted extended abstracts. The meeting took place in College Park, MD, USA. The committee made its decisions based on perceived quality and originality, as well as appropriateness to the theme of the symposium. The mix of selected papers reflects the unique nature of SPAA in bringing together the theory and practice of parallel computing. SPAA defines parallelism very broadly to encompass any computational "device" or scheme that can perform multiple operations or tasks simultaneously or concurrently. This year, SPAA technical papers include, for example, papers in parallel programming models, game theory in networking, the Web, sensor networks and quantum computing. The technical papers in this volume are to be considered preliminary versions, and authors are generally expected to publish polished and complete versions in archival scientific journals.Twelve of the contributed presentations are brief announcements. Some of the brief announcements were accepted as "position papers". These twelve announcements were selected either from abstracts submitted to be considered as brief announcements or from extended abstracts submitted to be considered either as a technical presentation or as a brief announcement. The committee's decisions were based on the perceived interest of these contributions, with the goal that they serve as bases for further significant advances in parallelism in computing. The committee's decisions on position papers were based on the perceived interest in hearing the positions. They should not be viewed as an endorsement of these positions. Extended versions of the SPAA brief announcements may be published later in other conferences or journals.