SPAA 2006 Conference Program


Contents:



Invited Talks

Why Intel is Designing Multi-Core Processors
Geoff Lowney

Chip-level Integration: The New Frontier for Microprocessor Architecture
Jaime H. Moreno

List of Accepted Papers

Regular papers:

Network Design with Weighted Players
Ho-Lin Chen and Tim Roughgarden

The Cache Complexity of Multithreaded Cache Oblivious Algorithms
Matteo Frigo and Volker Strumpen

On Space-Stretch Trade-Offs: Lower bounds
Ittai Abraham and Cyril Gavoille and Dahlia Malkhi

On Space-Stretch Trade-Offs: Upper bounds
Ittai Abraham and Cyril Gavoille and Dahlia Malkhi

On the Price of Heterogeneity in Parallel Systems
P. Brighten Godfrey and Richard M. Karp

Smooth Scheduling Under Variable Rates or The Analog-Digital Confinement Game
Ami Litman and Shiri Moran-Schein

Exponential Separation of Quantum and Classical Online Space Complexity
Francois Le Gall

Conflict-Free Coloring for Intervals: from Offline to Online
Amotz Bar-Noy and Panagiotis Cheilaris and Shakhar Smorodinsky

A Performance Analysis of Local Synchronization
Julia Lipman and Quentin F. Stout

Tell Me Who I Am: An Interactive Recommendation System
Noga Alon and Baruch Awerbuch and Yossi Azar and Boaz Patt-Shamir

Robust Network Computation
David Pritchard and Santosh Vempala

Tight bounds on the min-max boundary decomposition cost of weighted graphs
David Steurer

On the Communication Complexity of Randomized Broadcasting in Random-Like Graphs
Robert Elsaesser

Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networks
R. C. Chakinala and A. Kumarasubramanian and K. A. Laing and R. Manokaran and C. Pandu Rangan and R. Rajaraman

Modeling Instruction Placement on a Spatial Architecture
Martha Mercaldi and Steven Swanson and Andrew Petersen and Andrew Putnam and Andrew Schwerin and Mark Oskin and Susan Eggers

Fair Online Load Balancing
Niv Buchbinder and Seffi Naor

Power-aware scheduling for makespan and flow
David Bunde

Packet-Mode Emulation of Output-Queued Switches
Hagit Attiya and David Hay and Isaac Keslassy

Towards small world emergence
Philippe Duchon and Nicolas Hanusse and Emmanuelle Lebhar and Nicolas Schabanel

The price of Optimum in Stackelberg games on arbitrary networks and latency functions
Alexis Kaporis and Paul Spirakis

Minimizing the stretch when scheduling flows of biological requests
Arnaud Legrand and Alan Su and Frederic Vivien

Strip Packing with Precedence Constraints and Release Times
John Augustine and Sudarshan Banerjee and Sandy Irani

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem
Joachim Gehweiler and Christiane Lammersen and Christian Sohler

Distributed Random Digraph Transformations for Peer-to-Peer Networks
Peter Mahlmann and Christian Schindelhauer

A general approach for partitioning N-dimensional parallel nested loops with conditions
Arun Kejariwal and Hideki Saito and Xinmin Tian and Milind Girkar and Utpal Banerjee and Alexandru Nicolau and Constantine D. Polychronopoulos

Fault-Tolerant SemiFast Implementations of Atomic Read/Write Registers
Chryssis Georgiou and Nicolas C. Nicolaou and Alexander A. Shvartsman

Reconfigurable Resource Scheduling
C. Greg Plaxton and Yu Sun and Mitul Tiwari and Harrick Vin

Astronomical Real-Time Streaming Signal Processing on a Blue Gene/L Supercomputer
John W. Romein and P. Chris Broekema and Ellen van Meijeren and Kjeld van der Schaaf and Walther H. Zwart

Porting Between Itanium and Sparc Multiprocessing Systems
Lisa Higham and LillAnne Jackson

Deterministic load balancing and dictionaries in the parallel disk model
Mette Berger and Esben Rune Hansen and Rasmus Pagh and Mihai Patrascu and Milan Ruzic and Peter Tiedemann

Towards Automatic Parallelization of Tree Reductions in Dynamic Programming
Kiminori Matsuzaki and Zhenjiang Hu and Masato Takeichi

Efficient Parallel Algorithms for Dead Sensor Diagnosis and Multiple Access Channels
Michael T. Goodrich and Daniel S. Hirschberg

Publish and Perish: Definition and Analysis of an n-Person Publication Impact Game
Zvi Lotker, Boaz Patt-Shamir and Mark Tuttle

Towards a scalable and robust DHT
Baruch Awerbuch and Christian Scheideler


Brief announcements:

Compact routing with additive stretch using distance labelings
Arthur Brady and Lenore Cowen

An Implementation Report for Parallel Triangular Decompositions on a Shared Memory Multiprocessor
Marc Moreno Maza and Yzhen Xie

An empirical study to compare programmer effort of two parallel programming models
Lorin Hochstein, Victor R. Basili

The FG Programming Environment: Good and Good for You
Elena Riccio Davidson

The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework and Experimental Evaluation
Rezaul Alam Chowdhury and Vijaya Ramachandran

Parallel Depth First vs. Work Stealing Schedulers on CMP Architectures
Vasilis Liaskovitis and Shimin Chen and Phillip B. Gibbons and Anastassia Ailamaki and Guy Blelloch and Babak Falsafi and Limor Fix and Michael Kozuch and Todd C. Mowry and Chris Wilkerson

Semi-oblivious routing
Mohammad Hajiaghayi and Robert Kleinberg and Tom Leighton

Promoting Cooperation in Selfish Grids
Krzysztof Rzadca and Denis Trystram

Algorithms Minimizing Peak Energy on Mesh-Connected Systems
Quentin F. Stout

Energy Implications of Multiprocessor Synchronization
Tali Moreshet and R. Iris Bahar and Maurice Herlihy

Introducing the Hydra Parallel Programming System
Franklin E. Powers Jr. and Gita Alaghband

An Evolutionary Path towards Virtual Shared Memory with Random Access
Jonathan L. Brown and Sue Goudy and Mike Heroux and Shan Shan Huang and Zhaofang Wen

Conference Program

To download the SPAA program, click here.

Information about the Reception

Akamai Technologies is located in Cambridge at 8 Cambridge Center, which is located at the intersection of Galileo Galilei Way and Broadway, on the outskirts of Kendall Square. The main reception is on the first floor. Here is a map showing the location of Akamai (see the red square on the right side).

A trolley will leave the Charles Hotel at 5:45 pm and will run a continuous loop all night.

Via public transportation:
Take the Red Line T to Kendall / MIT. After exiting the station, go west on Main Street. The MIT Co-op will be on your right. Go right onto Ames Street, at the next intersection, Broadway, take a left. The Akamai building is on your left, just after the Residence Inn.

Information about the Social Event

The social event will be a dinner cruise with the Charles Riverboat Company, World Trade Center, 200 Seaport Boulevard, Boston. A bus service will be organized. For those not taking the bus, please arrive by 6:00pm. Here is a map showing the location of the Charles Riverboat Company (see the red circle in the lower right corner).

Directions to the Charles Riverboat Company Pier:

The vessel *Lexington* is located on the East Pier adjacent to the Boston Fish Pier at the World Trade Center at 200 Seaport Boulevard.

FROM NORTH OF BOSTON:
Take Route 93 South
Take exit 23 - Purchase Street - stay left
At light take left onto Seaport Boulevard (over Moakley Bridge)
After third set of lights the World Trade Center is on the left (long building with flags)
Parking is available at the Seaport Hotel Garage located on the right Charles Riverboat Company is the first dock on the right side of the World Trade Center

FROM THE WEST OF BOSTON:
Take Route 90 East - Mass Pike
Proceed directly into the Liberty Tunnel
Take exit marked South Boston
At light turn left - proceed to end of street - turn right onto Seaport Boulevard.
The World Trade Center (long building with flags) is directly on the left Parking is available at the Seaport Hotel Garage located on the right Charles Riverboat Company is the first dock on the right side of the World Trade Center

FROM SOUTH OF BOSTON:
Take Route 93 North
Take exit 20 - Logan Airport
Take exit marked South Boston
At light turn left - proceed to end of street - turn right onto Seaport Boulevard.
The World Trade Center (long building with flags) is directly on the left Parking is available at the Seaport Hotel Garage located on the right Charles Riverboat Company is the first dock on the right side of the World Trade Center

Note: The Big Dig may change road patterns the World Trade Center is in the southeast corner of the harbor - you can also use Congress Street or Summer Street to access the Seaport Boulevard area.

Christian Scheideler
Last modified: September 8, 2005