List of accepted papers for SPAA 2005:


Regular papers:

Coloring Unstructured Radio Networks
Thomas Moscibroda and Roger Wattenhofer

Randomized Queue Management for DiffServ
Nir Andelman

Is partial quantum search of a database any easier?
Lov K Grover and Jaikumar Radhakrishnan

Windows Scheduling of Arbitrary Length Jobs on Parallel Machines
Amotz Bar-Noy and Richard E. Ladner and Tami Tamir and Tammy VanDeGrift

Admission Control to Minimize Rejections and Online Set Cover with Repetitions
Noga Alon and Yossi Azar and Shai Gutner

Name Independent Routing for Growth Bounded Networks
Ittai Abraham and Dahlia Malkhi

Parallel Scheduling of Complex Dags under Uncertainty
Grzegorz Malewicz

Randomization does not reduce the average delay in parallel packet switches
Hagit Attiya and David Hay

On Distributed Smooth Scheduling
Ami Litman and Shiri Moran-Schein

The Expansion and Mixing Time of Skip Graphs with Applications
Jamse Aspnes and Udi Wieder

Decentralized Algorithms using both Local and Random Probes for P2P Load Balancing
Krishnaram Kenthapadi and Gurmeet Singh Manku

Fast Construction of Overlay Networks
Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu and Yitong Yin

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees
Randeep S. Bhatia and Nicole Immorlica and Tracy Kimbrel and Vahab S. Mirrokni and Seffi Naor and Baruch Schieber

Broadcasting on Networks of Workstations
Samir Khuller and Yoo-Ah Kim and Yung-Chun (Justin) Wan

Lexicographic QoS Scheduling for Parallel I/O
Ajay Gulati and Peter Varman

Dynamic Page Migration with Stochastic Requests
Marcin Bienkowski

Adversarial Contention Resolution for Simple Channels
Michael A. Bender and Martin Farach-Colton and Simai He and Bradley C. Kuszmaul and Charles E. Leiserson

An Adaptive Power Conservation Scheme for Heterogeneous Wireless Sensor
Ioannis Chatzigiannakis and Athanassios Kinalis and Sotiris Nikoletseas

Weighted Distributed Hash Tables
Christian Schindelhauer and Gunnar Schomaker

Peer-to-Peer Networks based on Random Transformations of Connected Regular Undirected Graphs
Peter Mahlmann and Christian Schindelhauer

A Truthful Mechanism for the Non-Utilitarian Minimum Radius Spanning Tree Problem
Guido Proietti and Peter Widmayer

Scheduling Malleable Tasks with Precedence Constraints
Klaus Jansen and Hu Zhang

Irrigating Ad Hoc Networks in Constant Time
D. Dubhashi and O. Haggstrom and C. Johansson and A. Panconesi and M. Sozio

Constant Density Spanners for Wireless Ad-Hoc Networks
Melih Onus and Andrea Richa and Kishore Kothapalli and Christian Scheideler

Radio Communication in Random Graphs
Robert Elsaesser and Leszek Gasieniec

Using Elimination to Implement Scalable FIFO Queues
Mark Moir and Daniel Nussbaum and Ori Shalev and Nir Shavit

Selfish Routing with Incomplete Information
Martin Gairing and Burkhard Monien and Karsten Tiemann

Oblivious Routing on Geometric Networks
Costas Busch and Malik Magdon-Ismail and Jing Xi

Processor Efficient Parallel Matching
Piotr Sankowski

Finding Effective Support-Tree Preconditioners
Bruce M. Maggs and Gary L. Miller and Ojas Parekh and R. Ravi and Shan Leung Maverick Woo

Concurrent Cache-Oblivious Search Trees
Michael A. Bender and Jeremy T. Fineman and Seth Gilbert and Bradley C. Kuszmaul

Dynamic Circular Work-Stealing Deque
David Chase and Yossi Lev

Value-Maximizing Deadline Scheduling and its Application to Animation Rendering
Eric Anderson and Dirk Beyer and Kamalika Chaudhuri and Terence Kelly and Norman Salazar and Cipriano Santos

Parallelizing Time With Polynomial Circuits
Ryan Williams

Efficient Algorithms for Verifying Memory Consistency
Chaiyasit Manovit and Sudheendra Hangal

Collaborate With Strangers To Find Own Preferences
Awerbuch and Azar and Lotker and Patt-Shamir and Tuttle


Brief announcments:

A Segmented Parallel-Prefix VLSI Circuit with Small Delays for Small Segments
Bradley C. Kuszmaul

A Forward Planning Situated Protocol for Data Propagation in Wireless Sensor Networks based on Swarm Intelligence Techniques
Ioannis Chatzigiannakis and Sotiris Nikoletseas

Autonomous Virtual Mobile Nodes
Shlomi Dolev and Seth Gilbert and Elad Schiller and Alex Shvartsman and Jennifer Welch

A Space Lower Bound for Name-Independent Compact Routing in Trees
Kofi A. Laing and Rajmohan Rajaraman

On Competitive Online Read-many Parallel Disks Scheduling
Rahul Shah and Peter J. Varman and Jeffrey Scott Vitter