June 6, 2003, Friday

7pm - 9pm Reception

June 7, 2003, Saturday

8:00am - 9:00am Continental Breakfast
9:00am - 10:15am Session 1: Scheduling I
9:00am - 9:25am Optimal Sharing of Bags of Tasks in Heterogeneous Clusters
Micah Adler, Ying Gong, and Arnold L. Rosenberg
9:25am - 9:50am Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching
Nir Avrahami and Yossi Azar
9:50am - 10:15am Online Deadline Scheduling: Multiple Machines and Randomization
Jae-Ha Lee
10:15am - 10:30am Break
10:30am - 12:10pm Session 2: Routing I
10:30am - 10:55am A Practical Algorithm for Constructing Oblivious Routing Schemes
Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Raecke
10:55am - 11:20am A Polynomial-time Tree Decomposition to Minimize Congestion
Chris Harrelson, Kirsten Hildrum, and Satish Rao
11:20am - 11:45am Online Oblivious Routing
Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson
11:45am - 12:10pm Novel Architectures for P2P Applications: The Continuous-Discrete Approach
Moni Naor and Udi Wieder
12:30pm - 2:00pm Lunch
2:10pm - 3:25pm Session 3: Networks I
2:10pm - 2:35pm Optimal Fault-Tolerant Linear Arrays
Toshinori Yamada and Shuichi Ueno
2:35pm - 3:00pm The Effect of Communication Costs in Solid-State Quantum Computing Architectures
Dean Copsey, Mark Oskin, Tzvetan Metodiev, Frederic T. Chong, and Isaac Chuang
3:00pm - 3:25pm VLSI Layout of Trees into Grids of Minimum Width
Akira Matsubayashi
3:25pm - 3:45pm Break
3:45pm - 4:35pm Session 4: Algorithms I
3:45pm - 4:10pm I/O-Efficient Topological Sorting of Planar DAGs
Lars Arge, Laura Toma, and Norbert Zeh
4:10pm - 4:35pm MST Construction in O(loglog n) Communication Rounds
Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg
4:35pm - 4:45pm Break
4:45pm - 5:35pm Session 5: Scheduling II
4:45pm - 5:10pm A Proportionate Fair Scheduling Rule with Good Worst-case Performance
Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Goldberg, Paul Goldberg, and Mike Paterson
5:10pm - 5:35pm Integrated Prefetching and Caching in Single and Parallel Disk Systems
Susanne Albers and Markus Buettner
5:35pm - 6:35pm SPAA Revue I
5:35pm - 5:45pm High Throughput, Parallelized 128-bit AES Encryption in a Resource-Limited FPGA
Christopher Caltagirone and Kasi Anantha
5:45pm - 5:55pm MAPO: Using a Committee of Algorithm-Experts for Parallel Optimization of Costly Functions
Christine Shoemaker and Rommel Regis
5:55pm - 6:05pm Short Length Menger's Theorem and it's Relation to Reliable Optical Routing
Amitabha Bagchi, Amitabh Chaudhary, and Petr Kolman
6:05pm - 6:15pm Relaxing the Problem-Size Bound for Out-of-Core Columnsort
Geeta Chaudhry, Elizabeth A. Hamon, and Thomas H. Cormen
6:15pm - 6:25pm Bicriteria Approximation Algorithms for Scheduling Problems with Communication Delays
Evripidis Bampis and Alexander Kononov
6:25pm - 6:35pm The Complexity of Verifying Memory Coherence
Jason F. Cantin, Mikko H. Lipasti, and James E. Smith
8:30pm - 10:00pm Business Meeting

June 8, 2003, Sunday

8:00am - 9:00am Continental Breakfast
9:00am - 10:15am Session 6: Algorithms II
9:00am - 9:25am Performance Comparison of MPI and three OpenMP Programming Styles on Shared Memory Multiprocessors
Geraud P. Krawezik and Franck Cappello
9:25am - 9:50am Quantifying Instruction Criticality for Shared Memory Multiprocessors
Tong Li, Alvin R. Lebeck, and Daniel J. Sorin
9:50am - 10:15am Asynchronous Parallel Disk Sorting
Roman Dementiev and Peter Sanders
10:15am - 10:30am Break
10:30am - 12:10pm Session 7: Networks II
10:30am - 10:55am Designing Overlay Multicast Networks for Streaming
Konstantin Andreev, Bruce Maggs, Adam Meyerson, and Ramesh Sitaraman
10:55am - 11:20am Combining Online Algorithms for Rejection and Acceptance
Yossi Azar, Avrim Blum, and Yishay Mansour
11:20am - 11:45am Off-line and On-line Guaranteed Start-up Delay for Media-on-Demand with Stream Merging
Amotz Bar-Noy, Justin Goshi, and Richard E. Ladner
11:45am - 12:10pm TCP is competitive agaist a limited adversary
Jeff Edmonds, Suprakash Datta, and Patrick Dymond
12:30pm - 2:00pm Lunch
2:10pm - 2:35pm Session 8: Routing II
2:10pm - 2:35pm Compact Routing with Name Independence
M. Arias, L. Cowen, K. Laing, R. Rajaraman, and O. Taka
2:35pm - 3:00pm Tree Based MPLS Routing
Anupam Gupta, Amit Kumar, and Mikkel Thorup
3:00pm - 3:25pm Throughput-Centric Routing Algorithm Design
Brian Towles, William J. Dally, and Stephen P. Boyd
3:25pm - 3:45pm Break
3:45pm - 5:00pm Session 9: Ad Hoc Networks
3:45pm - 4:10pm Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks
Costas Busch, Srikanth Surapaneni, and Srikanta Tirthapura
4:10pm - 4:35pm On Local Algorithms for Topology Control and Routing in Ad Hoc Networks
Lujun Jia, Rajmohan Rajaraman, and Christian Scheideler
4:35pm - 5:00pm Worst Case Mobility in Ad Hoc Networks
Christian Schindelhauer, Tamas Lukovszki, Stefan Ruehrup, and Klaus Volbert
5:00pm - 5:30pm SPAA Revue II
5:00pm - 5:10pm Buffer Overflows of Merging Streams
Alexander Kesselman, Zvi Lotker, Yishay Mansour, and Boaz Patt-Shamir
5:10pm - 5:20pm Randomized Permutations in a Coarse Grained Parallel Environment
Jens Gustedt
5:20pm - 5:30pm Efficient Galois Field Arithmetic on SIMD Architectures
Raghav Bhaskar, Pradeep K. Dubey, Vijay Kumar, Atri Rudra, and Animesh Sharma
5:45pm - 7:00pm FCRC Plenary Session: ACM Turing Lecture

June 9, 2003, Monday

8:00am - 9:00am Continental Breakfast
9:00am - 10:15am Session 10: Load Balancing
9:00am - 9:25am The Load Rebalancing Problem
Gagan Aggarwal, Rajeev Motwani, and An Zhu
9:25am - 9:50am Load Balancing of Unit Size Tokens and Expansion Properties of Graphs
Robert Elsaesser and Burkhard Monien
9:50am - 10:15am Cycle Stealing under Immediate Dispatch Task Assignment
Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, and Mark Squillante
10:15am - 10:30am Break
10:30am - 11:20pm Session 11: Algorithms III
10:30am - 10:55am Polynomial Time Algorithms for Network Information Flow
Peter Sanders, Sebastian Egner, and Ludo Tolhuizen
10:55am - 11:20am Improved Approximation Algorithms for the Freeze-Tag Problem
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He, and Joseph S. B. Mitchell
11:30am - 12:30pm FCRC Plenary Session
12:30pm - 2:00pm Lunch
2:10pm - 3:25pm Session 12: Distributed Computing
2:10pm - 2:35pm Toward A Decidable Notion of Sequential Consistency
Jesse D. Bingham, Anne Condon, and Alan J. Hu
2:25pm - 3:00pm NonBlocking k-Compare-Single-Swap
Victor Luchangco, Mark Moir, and Nir Shavit
3:00pm - 3:25pm Can we elect if we cannot compare?
Lali Barriere, Paola Flocchini, Pierre Fraigniaud, and Nicola Santoro
3:25pm - 3:45pm Break
3:45pm - 5:00pm Session 13: Networks III
3:45pm - 4:10pm Information Gathering in Adversarial Systems: Lines and Cycles
Kishore Kothapalli and Christian Scheideler
4:10pm - 4:35pm A Near Optimal Scheduler for Switch-Memory-Switch Routers
Adnan Aziz, Amit Prakash, and Vijaya Ramachandran
4:35pm - 5:00pm Scheduling Policies for CIOQ Switches
Alex Kesselman and Adi Rosen
5:00pm - 6:00pm FCRC Plenary Session: Knuth Prize Lecture
6pm END. See you next year in Barcelona

This page maintained by Cindy Phillips.

Last modified: May 7, 2003