SPAA 2015 Conference Program


List of Accepted Papers

Regular papers

Gary Miller, Richard Peng, Adrian Vladu and Shen Chen Xu.
Improved Parallel Algorithms for Spanners and Hopsets

Qin Zhang.
Communication-Efficient Multi-Machine Computation on Distributed Noisy Datasets

Nuno Diegues, Stoyan Garbatov and Paolo Romano.
Seer: Probabilistic Scheduling for Hardware Transactional Memory

Sungjin Im and Benjamin Moseley.
Scheduling in Bandwidth Constrained Tree Networks

Lingxiang Xiang and Michael L. Scott.
Conflict Reduction in Hardware Transactions Using Advisory Locks

Nachshon Cohen and Erez Petrank.
Efficient Memory Management for Lock-Free Data Structures with Optimistic Access

Oded Green, Marat Dukhan and Richard Vuduc.
Branch-Avoiding Graph Algorithms

Sungjin Im, Janardhan Kulkarni and Benjamin Moseley.
Temporal Fairness of Round Robin: Competitive Analysis for Lk-norms of Flow Time

Yossi Azar, Nikhil Devanur, Zhiyi Huang and Debmalya Panigrahi.
Speed Scaling in the Non-clairvoyant Model

Magnus M. Halldorsson, Sven Köhler, Boaz Patt-Shamir and Dror Rawitz.
Distributed Backup Placement in Networks

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale and Gustavo Posta.
Self-Stabilizing Repeated Balls-into-Bins

Ishai Menache and Mohit Singh.
Online Caching with Convex Costs

Kook Jin Ahn and Sudipto Guha.
Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints

Ryan Lewis and Dmitriy Morozov.
Parallel Computation of Persistent Homology using the Blowup Complex

Guy Even, Moti Medina and Boaz Patt-Shamir.
Better Deterministic Online Packet Routing on Grids

Michael Bender, Martin Farach-Colton, Sandor Fekete, Jeremy Fineman and Seth Gilbert.
Cost-Oblivious Reallocation for Scheduling and Planning

Merav Parter and David Peleg.
Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff

Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci and Eli Upfal.
Space and Time Efficient Parallel Graph Decomposition, Clustering and Diameter Approximation

Zhen Qiu, Cliff Stein and Yuan Zhong.
Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks

Harald Räcke and Richard Stotz.
Improved Approximation Algorithms for Balanced Partitioning Problems

Jacob Scott, Olga Holtz and Oded Schwartz.
Matrix Multiplication I/O-Complexity by Path Routing

Michael Axtmann, Peter Sanders, Timo Bingmann and Christian Schulz.
Practical Massively Parallel Sorting

Laurent Feuilloley and Pierre Fraigniaud.
Randomized Local Distributed Network Computing

Yan Gu, Julian Shun, Yihan Sun and Guy Blelloch.
Parallel Semisorting Revisited

Yujie Liu, Tingzhe Zhou and Michael Spear.
Transactional Acceleration of Concurrent Data Structures

I-Ting Lee and Tao Schardl.
Efficiently Detecting Determinacy Races in Cilk Programs That Use Reducer Hyperobjects

Dan Alistarh, William Leiserson, Alexander Matveev and Nir Shavit.
ThreadScan: Automatic, Scalable Memory Reclamation

Dimitar Dimitrov, Martin Vechev and Vivek Sarkar.
Race detection in two dimensions

Marek Klonowski and Dominik Pajak.
Electing a Leader in Wireless Networks Quickly Despite Jamming

Tao Schardl, Bradley Kuszmaul, I-Ting Lee, William Leiserson and Charles Leiserson.
The Cilkprof Scalability Profiler

Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu and Julian Shun.
Sorting with Asymmetric Read and Write Costs

Jeremy Fineman and Brendan Sheridan.
Scheduling Non-Unit Jobs to Minimize Calibrations