SPAA 2007 Call for Participation and Program

---------------------------------------------------------------------
                 CALL FOR PARTICIPATION - SPAA 2007
  19th ACM Symposium on Parallelism in Algorithms and Architectures
                   San Diego, CA, June 9-11, 2007
                   http://www.spaa-conference.org
---------------------------------------------------------------------

Please be aware of the following deadlines:

 Early registration deadline: May 11, 2007
 Hotel deadline             : May  9, 2007


The conference program is below.

---------------------------------------------------------------------

SPAA 2007 Program:
==================

Friday, June 8:

07:00 - 09:00 pm: SPAA reception (tentative)

--------------------------

Saturday, June 9:

08:00 - 08:45: Breakfast

08:45 - 10:00: Network Theory

Pierre Fraigniaud, Cyril Gavoille,  Adrian Kosowski, Emmanuelle Lebhar, and
Zvi Lotker.
Universal Augmentation Schemes for Network Navigability: Overcoming the
$\sqrt n$-Barrier.

Robert Krauthgamer.
On Triangulation of Simple Networks.

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi and Udi Wieder.
Strongly-Bounded Sparse Decompositions of Minor Free Graphs.

10:00 - 10:30: Morning Break

10:30 - 11:45: Scheduling

Guolong Lin and Rajmohan Rajaraman.
Approximation Algorithms for Multiprocessor Scheduling under Uncertainty.

Michael A. Bender and Cynthia Phillips.
Scheduling DAGs on Asynchronous Processors.

Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S.
Sayedi-Roshkhar, and Morteza Zadimoghaddam.
Scheduling to Minimize Gaps and Power Consumption.

11:45 - 12:00: Small Break

12:00 - 12:30: Brief Announcements I: Parallel and Multicore Systems

Ganapathy Senthilkumar, Murali Velamati, Naresh Jayam, Arun Thondapu,
Pallav Baruah, Ashok Srinivasan, Raghunath Sharma, and Shakthi Kapoor.
Brief Announcement: Feasibility Study of MPI implementation on the
Heterogeneous Multi-Core Cell BE Architecture.

Srinivas Sridharan, Arun Rodrigues. and Peter Kogge.
Brief Announcement: Evaluating Synchronization Techniques for Light-weight
Multithreaded/Multicore Architectures.

Woongki Baek, JaeWoong Chung, Chi Cao Minh, Christos Kozyrakis, and
Kunle Olukotun.
Brief Announcement: Towards Soft Optimization Techniques for Parallel
Cognitive Applications.

12:30 - 01:50: Lunch Break

01:50 - 03:30: Cache-Oblivious/Cache-Aware Algorithms

Elias Vicari, Riko Jacob, Michael A. Bender, Gerth S. Brodal, and Rolf
Fagerberg.
Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model.

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

Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel,
Bradley C. Kuszmaul, and Jelani Nelson.
Cache-Oblivious Streaming B-trees.

Kamen Yotov, Tom Roeder, Keshav Pingali, John Gunnels, and Fred Gustavson.
An Experimental Comparison of Cache-oblivious and Cache-aware Programs.

03:30 - 04:00: Afternoon Break

04:00 - 05:40: Multicore Architectures and Algorithms

Shimin Chen, Phillip Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia
Ailamaki, Guy Blelloch, Babak Falsafi, Limor Fix, Nikos Hardavellas,
Todd Mowry and Chris Wilkerson.
Scheduling Threads for Constructive Cache Sharing on CMPs.

Ernie Chan, Enrique S. Quintana-Orti, Gregorio Quintana-Orti, and
Robert van de Geijn.
SuperMatrix Out-of-Order Scheduling of Matrix Operations for SMP and Multi-Core
Architectures.

Jeffery A Brown, Rakesh Kumar, and Dean Tullsen.
Proximity-Aware Directory-based Coherence for Multi-core Processor
Architectures.

Guangming Tan, Ninghui Sun, and Guangrong Gao.
A Parallel Dynamic Programming Algorithm on a Multi-core Architecture.

--------------------------

Sunday, June 10:

08:00 - 08:45: Breakfast

08:45 - 10:00: Distributed Network Algorithms

Fabian Kuhn, Thomas Locher, and Roger Wattenhofer.
Tight Bounds for Distributed Selection.

Pierre Fraigniaud, Amos Korman, and Emmanuelle Lebhar.
Local MST Computation with Short Advice.

Fabian Kuhn and Thomas Moscibroda.
Distributed Approximation of Capacitated Dominating Sets.

10:00 - 10:30: Morning Break

10:30 - 11:45: Packing, Coloring, and Load Balancing

Piotr Berman, Jieun Jeong , Shiva Kasiviswanathan, and Bhuvan Urgaonkar.
Packing to Angles and Sectors.

Deepak Ajwani, Khaled Elbassioni, Sathish Govindarajan, and Saurabh Ray.
Conflict-Free Coloring for Rectangle Ranges Using $\tO(n^{.382+\epsilon})$
Colors.

Udi Wieder.
Balanced Allocations with Heterogenous Bins.

11:45 - 12:00: Small Break

12:00 - 12:30: Brief announcements II: Diverse Algorithms

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, and Shakhar
Smorodinsky.
Brief Announcement: Weakening the Online Adversary Just Enough to Get Optimal
Conflict-free Colorings for Intervals.

Eric Angel, Evripidis Bampis, Fanny Pascual. and Alex-Ariel Tchetgnia.
Brief Announcement: On the Trade-off between Truthfulness and Approximation
for Scheduling Selfish Tasks.

Anton Lokhmotov and Alan Mycroft.
Brief Announcement: Optimal Bit-reversal Using Vector Permutations.

12:30 - 01:50: Lunch Break

01:50 - 03:30: Concurrent Programming

Michel Raynal and Gadi Taubenfeld.
The Notion of a Timed Register and its Application to Indulgent Synchronization.

Michael Spear, Arrvindh Shriraman, Luke Dalessandro, Sandhya Dwarkadas, and
Michael Scott.
Nonblocking Transactions Without Indirection Using Alert-on-Update.

Torvald Riegel, Christof Fetzer, and Pascal Felber.
Time-based Transactional Memory with Scalable Time Bases.

Shivali Agarwal, Rajkishore Barik, Dan Bonachea, Vivek Sarkar, Rudrapatna K.
Shyamasundar, and Katherine Yelick.
Deadlock-Free Scheduling of X10 Computations with Bounded Resources.

03:30 - 04:00: Afternoon Break

04:00 - 05:15: Algorithms for Wireless Networks

Joseph Wun-Tat Chan, Francis Y. L. Chin, Deshi Ye, and Yong Zhang.
Online Frequency Allocation in Cellular Networks.

Petra Berenbrink, Colin Cooper, and Zengjian Hu.
Energy Efficient Randomised Communication in Unknown AdHoc Networks.

Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide, and Jonas
Schrieb.
Local Strategies for Maintaining a Chain of Relay Stations between an Explorer
and a Base Station.

05:45 - 07:00: Turing Award Lecture (FCRC Plenary Session)

08:30 (tentative): SPAA Business Meeting

--------------------------

Monday, June 11:

08:00 - 08:45: Breakfast

08:45 - 10:00: Latency and Makespan

John Douceur, Jay Lorch, and Thomas Moscibroda.
Maximizing Total Upload in Latency-Sensitive P2P Applications.

Jack J. Dongarra, Emmanuel Jeannot, Erik Saule, and Zhiao Shi.
Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on
Heterogeneous Systems.

Susanne Albers, Fabian M?ller, and Swen Schmelzer.
Speed Scaling on Parallel Processors.

10:00 - 10:30: Morning Break

10:30 - 11:00: Brief Announcements III: Parallel Computing

Bradley C. Kuszmaul.
Brief Announcement: Cilk Provides the Best Overall Productivity for High
Performance Computing (and Won the HPC Challenge Award to Prove It).

Xingzhi Wen and Uzi Vishkin.
Brief Announcement: PRAM on Chip: First Commitment to Silicon.

Craig Zilles and Ravi Rajwar.
Brief Announcement: Transactional Memory and the Birthday Paradox.

11:00 - 11:30: Small Break

11:30 - 12:30: Keynote Speech (FCRC Plenary Session)

12:30 - 01:50: Lunch Break

01:50 - 03:30: Online Algorithms and Games

Adi Rosen and Gabriel Scalosub.
Rate vs. Buffer Size - Greedy Information Gathering on the Line.

Baruch Awerbuch and Thomas P. Hayes.
Online Collaborative Filtering with Nearly Optimal Dynamic Regret.

Yossi Azar, Iftah Gamzu, and Shai Gutner.
Truthful Unsplittable Flow for Large Capacity Networks.

Angelo Fanelli, Michele Flammini, and Luca Moscardelli.
On the Convergence of Multicast Games in Directed Networks.

03:30 - 04:00: Afternoon Break

04:00 - 05:15: Algorithms and Architectures

Benoit Hudson, Gary Miller, and Todd Phillips.
Sparse Parallel Delaunay Mesh Refinement.

Timothy Furtak, Jos? Nelson Amaral, and Robert Niewiadomski.
Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism
in Sorting Algorithms.

Koji Kobayashi, Shuichi Miyazaki, and Yasuo Okabe.
A Tight Bound on Online Buffer Management for Two-port Shared-Memory Switches.