SPAA 2005 Conference Program: ============================= Sunday, July 17, 2005 7:00 - 10:00 pm : Reception Monday, July 18 7:30 - 8:20 am : Continental Breakfast 8:20 - 10:00 : Session 1: Queuing and Scheduling (Chair: TBA) Randomized Queue Management for DiffServ Nir Andelman Randomization does not Reduce the Average Delay in Parallel Packet Switches Hagit Attiya and David Hay Dynamic Circular Work-Stealing Deque David Chase and Yossi Lev Lexicographic QoS Scheduling for Parallel I/O Ajay Gulati and Peter Varman 10:00 - 10:30 : Coffee Break 10:30 - 12:10 : Session 2: Joint Session (Chair: TBA) Distance Estimation and Object Location via Rings of Neighbors Aleksandrs Slivkins Building Scalable and Robust Peer-to-Peer Overlay Networks for Broadcasting using Network Coding Kamal Jain, Laszlo Lovasz and Philip A. Chou Coloring Unstructured Radio Networks Thomas Moscibroda and Roger Wattenhofer Name Independent Routing for Growth Bounded Networks Ittai Abraham and Dahlia Malkhi 12:10 - 1:45 : Lunch 1:45 - 3:25 : Session 3: Scheduling (Chair: TBA) Windows Scheduling of Arbitrary Length Jobs on Parallel Machines Amotz Bar-Noy, Richard E. Ladner, Tami Tamir, and Tammy VanDeGrift Parallel Scheduling of Complex Dags under Uncertainty Grzegorz Malewicz On Distributed Smooth Scheduling Ami Litman and Shiri Moran-Schein Scheduling Malleable Tasks with Precedence Constraints Klaus Jansen and Hu Zhang 3:25 - 4:05 : Coffee Break 4:05 - 5:20 : Session 4: Sensor Networks and Ad Hoc Networks (Chair: TBA) Irrigating Ad Hoc Networks in Constant Time D. Dubhashi, O. Haggstrom, C. Johansson, A. Panconesi and M. Sozio An Adaptive Power Conservation Scheme for Heterogeneous Wireless Sensor Networks Ioannis Chatzigiannakis, Athanassios Kinalis and Sotiris Nikoletseas Constant Density Spanners for Wireless Ad-Hoc Networks Melih Onus, Kishore Kothapalli, Andrea Richa and Christian Scheideler 8:00 - 10:00 : Business Meeting Tuesday, July 19 7:30 - 8:20 am : Continental Breakfast 8:20 - 10:00 : Session 5: Peer-to-Peer Networks (Chair: TBA) The Expansion and Mixing Time of Skip Graphs with Applications James 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, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin Peer-to-Peer Networks based on Random Transformations of Connected Regular Undirected Graphs Peter Mahlmann and Christian Schindelhauer 10:00 - 10.40 : Coffee Break 10.40 - 11:40 : Invited Talk (Chair: TBA) TBA Elias Koutsoupias 11:40 - 1:45 : Lunch 1:45 - 3:25 : Session 6: Parallel and Quantum Algorithms (Chair: TBA) Processor Efficient Parallel Matching Piotr Sankowski Parallelizing Time with Polynomial Circuits Ryan Williams Finding Effective Support-Tree Preconditioners Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung Maverick Woo Is Partial Quantum Search of a Database Any Easier? Lov K. Grover and Jaikumar Radhakrishnan 3:25 - 4:05 : Coffee Break 4:05 - 4:55 : Session 7: Game Theory (Chair: TBA) A Truthful Mechanism for the Non-Utilitarian Minimum Radius Spanning Tree Problem Guido Proietti and Peter Widmayer Selfish Routing with Incomplete Information Martin Gairing, Burkhard Monien and Karsten Tiemann 5:00 - 5:25 : Brief Announcements (Chair: TBA) 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 Ioannis Chtzigiannakis and Sotiris Nikoletseas Autonomous Virtual Mobile Nodes Shlomi Dolev, Seth Gilbert, Elad Schiller, 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, Peter J. Varman and Jeffrey Scott Vitter 6:00 - 11:00 : Banquet and Awards Ceremony Wednesday, July 20 7:30 - 8:20 am : Continental Breakfast 8.20 - 10.00 : Session 8: Algorithms and Data Structures (Chair: TBA) Weighted Distributed Hash Tables Christian Schindelhauer and Gunnar Schomaker Concurrent Cache-Oblivious Search Trees Michael A. Bender, Jeremey T. Fineman, Seth Gilbert and Bradley C. Kuszmaul Admission Control to Minimize Rejections and Online Set Cover with Repetitions Noga Alon, Yossi Azar and Shai Gutner Efficient Algorithms for Verifying Memory Consistency Chaiyasit Manovit and Sudheendra Hangal 10.00 - 10.30 : Coffee Break 10.30 - 12.10 : Session 9: Joint Session (Chair: TBA) Adaptive Routing with Stale Information Simon Fischer and Berthold Vöcking A Network Pricing Game for Selfish Traffic Ara Hayraptetyan, Eva Tardos and Tom Wexler Using Elimination to Implement Scalable FIFO Queues Mark Moir, Daniel Nussbaum, Ori Shalev and Nir Shavit Collaborate with Strangers to Find Own Preferences Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir and Mark Tuttle 12:10 - 1:45 : Lunch 1:45 - 3:25 : Session 10: Miscellaneous (Chair: TBA) Dynamic Page Migration with Stochastic Requests Marcin Bienkowski Broadcasting in Networks of Workstations Samir Khuller, Yoo-Ah Kim and Yung-Chun (Justin) Wan Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees Randeep S. Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Seffi Naor and Baruch Schieber Value-Maximizing Deadline Scheduling and its Application to Animation Rendering Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar and Cipriano Santos 3:25 - 3:45 : Coffee Break 3:45 - 5:00 : Session 11: Radio Networks (Chair: TBA) Radio Communication in Random Graphs Robert Elsaesser and Leszek Gasieniec Oblivious Routing in Geometric Networks Costas Busch, Malik Magdon-Ismail and Jing Xi Adversarial Contention Resolution for Simple Channels Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul and Charles E. Leiserson