SPAA 2010 Conference Program


Contents:


Conference Program

The final SPAA program is available here. The rough schedule looks as follows: SPAA Best Paper Award:

"Basic Network Creation Games" by Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi and Tom Leighton

Keynote Speakers:

List of Accepted Papers

Regular papers:

Jongsoo Park and William Dally.
A Buffer-space Efficient and Deadlock-free Scheduling of Stream Applications on Multi-core Architectures

Alexander Fanghaenel, Sascha Geulen, Martin Hoefer and Berthold Vöcking.
Online Capacity Maximization in Wireless Networks

Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic and Calvin Newport.
Securing Every Bit: Authenticated Broadcast in Radio Networks

Matti Astrand and Jukka Suomela.
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

Dave Dice and Nir Shavit.
TLRW: Return of the Read-Write Lock

Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi and Tom Leighton.
Basic Network Creation Games

Gopal Pandurangan and Jen-Yeu Chen.
Optimal Gossip-Based Aggregate Computation

Ernie Chan, Andrew Chapman and Robert van de Geijn.
Managing the Complexity of Lookahead for LU Factorization with Pivoting

James Aspnes, David Eisenstat and Yitong Yin.
Low-Contention Data Structures

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs.
Scheduling Jobs with Varying Parallelizability to Reduce Variance

Petra Berenbrink, Andre Brinkmann, Tom Friedetzky and Lars Nagel.
Balls into Bins with with Related Random Choices

Arne Vater, Christian Ortolf and Christian Schindelhauer.
Tree Network Coding for Peer-to-Peer Networks

Yuxiong He, Charles Leiserson and William Leiserson.
The Cilkview Scalability Analyzer

Keren Censor Hillel.
Multi-Sided Shared Coins and Randomized Set-Agreement

Woongki Baek, Nathan Bronson, Christos Kozyrakis and Kunle Olukotun.
Implementing and Evaluating Nested Parallel Transactions in Software Transactional Memory

Charles Leiserson and Tao Schardl.
A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)

Pierre Fraigniaud and Andrzej Pelc.
Delays Induce an Exponential Memory Gap for Rendezvous in Trees

Seth Gilbert, Rachid Guerraoui, Faezeh Malakouti and Morteza Zadimoghaddam.
Collaborative Scoring with Dishonest Participants

Bastian Degener, Barbara Kempkes and Friedhelm Meyer auf der Heide.
A local O(n^2) gathering algorithm

Rachid Guerraoui, Thomas Henzinger, Michal Kapalka and Vasu Singh.
Transactions in the Jungle

Danny Hendler, Itai Incze, Nir Shavit and Moran Tzafrir.
Flat Combining and the Synchronization-Parallelism Tradeoff

Anne Benoit, Fanny Dufosse, Matthieu Gallet, Bruno Gaujal and Yves Robert.
Computing the throughput of probabilistic and replicated streaming applications

Erik Demaine and Morteza Zadimoghaddam.
Scheduling to Minimize Power Consumption using Submodular Functions

Michela Becchi, Surendra Byna, Srihari Cadambi and Srimat Chakradhar.
Data-Aware Scheduling of Legacy Kernels on Heterogeneous Platforms with Distributed Memory

Dave Dice, Yossi Lev, Virendra Marathe, Mark Moir, Marek Olszewski and Dan Nussbaum.
Simplifying Concurrent Algorithms by Exploiting Hardware TM

Phong Chuong, Faith Ellen and Vijaya Ramachandran.
Transaction Friendly Data Structures

Bertrand Ducourthial, Sofiane Khalfallah and Franck Petit.
Best-effort Group Service in Dynamic Networks

Peng Li, Kunal Agrawal, Jeremy Buhler and Roger D. Chamberlain.
Deadlock Avoidance for Streaming Computations with Filtering

Michael Spear.
Lightweight, Robust Adaptivity for Software Transactional Memory

Peter Krusche and Alexander Tiskin.
New algorithms for efficient parallel string comparison

Vijay Anand Korthikanti and Gul Agha.
Towards Optimizing Energy Costs of Algorithms for Shared Memory Architectures

George Giakkoupis and Pierre Fraigniaud.
On the Bit Communication Complexity of Randomized Rumor Spreading

Guy Blelloch, Phillip Gibbons and Harsha Vardhan Simhadri.
Low Depth Cache-Oblivious Algorithms

Michael Fischer, Xueyuan Su and Yitong Yin.
Assigning Tasks for Efficiency in Hadoop

Guy Blelloch and Kanat Tangwongsan.
Parallel Approximation Algorithms for Facility-Location Problems

Brief announcements:

Paolo Romano, Roberto Palmieri, Francesco Quaglia, Nuno Carvalho and Luis Rodrigues.
On Speculative Replication of Transactional Systems

Enoch Peserico.
Flashcrowding in tiled multiprocessors under thermal constraints

Youngjoon Jo and Milind Kulkarni.
Locality-aware Load Balancing for Speculatively-parallelized Irregular Applications

Arunabha Sen, Sujogya Banerjee, Pavel Ghosh, Sudheendra Murthy and Hung Ngo.
On Regenerator Placement and Routing Problems in Optical Networks

Ioannis Chatzigiannakis, Georgios Mylonas, Orestis Akribopoulos, Marios Logaras, Panagiotis Kokkinos and Paul Spirakis.
Fun In Numbers: A Platform for Sensor-based Multiplayer Pervasive Games

Hagit Attiya, Vincent Gramoli and Alessia Milani.
Combine: An Improved Directory-Based Consistency Protocol

Kunal Agrawal, ITing Lee and Jim Sukha.
Serial-Parallel Reciprocity in Dynamic Multithreaded Languages

Sina Meraji, Wei Zhang and Carl Tropper.
A Reinforcement Learning Approach for Dynamic Load-Balancing of Parallel Digital Logic Simulation

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui and Anne-Marie Kermarrec.
Byzantine Agreement with Homonyms

Laura Grigori, Pierre-Yves David, James Demmel and Sylvain Peyronnet.
Lower bounds on communication for sparse Cholesky factorization of a model problem