PROGRAM FOR SPAA 2003

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

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