SPAA

The papers of this volume were presented at the 15th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA, previously known as the Annual Symposium on Parallel Algorithms and Architectures), held June 7--9, 2003, in San Diego, CA, USA, as part of the Federated Computing Research Conference (FCRC). The conference was sponsored by the Special Interest Group on Algorithms and Computation Theory (SIGACT) and the Special Interest Group on Computer Architecture (SIGARCH) of the ACM, in cooperation with the European Association of Theoretical Computer Science (EATCS). The 38 technical presentations were selected by the Program Committee out of 106 submissions during the Program Committee Meeting in Paderborn, March 8--9, 2003. The committee based its decisions on perceived quality and originality, and on the appropriateness to the theme of the Symposium. The mix of the selected papers reflects the unique nature of the Symposium in bringing together theory and practice of parallel computing, and in defining "parallel" very broadly to encompass any computational "device" that can perform multiple operations or tasks simultaneously. The 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. In addition to technical presentations this volume also includes 9 brief communications presented at the SPAA revue. These communications were selected from those papers submitted as revue only or as both regular and revue. The Committee's decisions were based on the perceived interest of the contributions. They may serve as a basis for further significant advances in parallel computing. Extended versions of these papers may be published later in other conferences or journals. The Program Committee would like to thank all who submitted papers, and all colleagues listed below who helped by providing reviews.