SPAA 2007 Conference Program


The SPAA Best Paper Awards go to Congratulations! The awards will be given to the authors during the SPAA business meeting.

List of Accepted Papers

Regular papers (37 out of 130 submissions):

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

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

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

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

Robert Krauthgamer
On triangulation of simple networks

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

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

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

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

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

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

Fabian Kuhn and Thomas Moscibroda
Distributed Approximation of Capacitated Dominating Sets

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

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

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

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

Michel Raynal and Gadi Taubenfeld
The notion of a Timed Register and its application to Indulgent Synchronization

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

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

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

Michael Bender and Cynthia Phillips
Scheduling DAGs on Asynchronous Processors

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

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

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

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

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

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

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

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

Udi Wieder
Balanced Allocations with Heterogenous Bins

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

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

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

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

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

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

Brief announcements:

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky
Weakening the online adversary just enough to get optimal conflict-free colorings for intervals

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

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

Eric Angel, Evripidis Bampis, Fanny Pascual and Alex-Ariel Tchetgnia
On the trade-off between truthfulness and approximation for scheduling selfish tasks

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

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

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

Anton Lokhmotov and Alan Mycroft
Optimal bit-reversal using vector permutations

Craig Zilles and Ravi Rajwar
Transactional Memory and the Birthday Paradox

Conference Program

To download the SPAA program, click here.

Christian Scheideler
Last modified: September 4, 2006