SPAA 2007 Conference Program
Contents:
The SPAA Best Paper Awards go to
- Pierre Fraigniaud, Cyril Gavoille, Emmanuelle Lebhar, Zvi Lotker and Adrian Kosowski
Universal Augmentation Schemes for Network Navigability: Overcoming the $\sqrt n$-Barrier
- Fabian Kuhn, Thomas Locher and Roger Wattenhofer
Tight Bounds for Distributed Selection
Congratulations! The awards will be given to the authors during the SPAA business meeting.
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
To download the SPAA program, click here.
Christian Scheideler
Last modified: September 4, 2006