SPAA 2013 Conference Program


Contents:


List of Accepted Papers

Regular papers:

Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii and Andrea Vattani.
Fast Greedy Algorithms in MapReduce and Streaming

Piotr Skowron and Krzysztof Rzadca.
Non-monetary fair scheduling --- cooperative game theory approach

John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson and Eli Upfal.
Storage and Search in Dynamic Peer-to-Peer Networks

Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce, Lata Narayanan, Jarda Opatrny and Sunil Shende.
Expected Sum and Maximum of Displacement of Random Sensors for Coverage of a Domain

Chaodong Zheng and Seth Gilbert.
SybilCast: Broadcast on the Open Airwaves

Peter Sanders, Jochen Speck and Raoul Steffen.
Work-Efficient Matrix Inversion in Polylogarithmic Time

I-Ting Lee, Charles Leiserson, Tao Schardl, Jim Sukha and Zhunping Zhang.
On-the-Fly Pipeline Parallelism

Richard Yoo, Christopher Hughes, Changkyu Kim, Yen-Kuang Chen and Christos Kozyrakis.
Locality-Aware Task Management for Unstructured Parallelism: A Quantitative Limit Study

Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc, Russell Martin and Oscar Morales Ponce.
Optimal Patrolling of Fragmented Boundaries

Reuven Bar-Yehuda, Michael Beder and Dror Rawitz.
A Constant Factor Approximation Algorithm for the Storage Allocation Problem

Hoda Akbari and Petra Berenbrink.
Parallel Rotor Walks on Finite Graphs and Applications in Discrete Load Balancing

Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee and Jianqiao Zhu.
Nonclairvoyant Sleep Management and Flow-time Scheduling on Multiple Processors

Gary Miller and Richard Peng.
Parallel Graph Decompositions Using Random Shifts

Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy Fineman and Seth Gilbert.
Reallocation Problems in Scheduling

Dave Dice, Yossi Lev and Mark Moir.
Scalable Statistics Counters

Peter Kling and Peter Pietrzyk.
Profitable Scheduling on Multiple Speed-Scalable Processors

Anastasia Braginsky, Alex Kogan and Erez Petrank.
Drop the Anchor: Lightweight Memory Management for Non-Blocking Data Structures

Bernd Kawald and Pascal Lenzner.
On Dynamics in Selfish Network Creation

Martina Eikel and Christian Scheideler.
IRIS: A Robust Information System Against Insider DoS-Attacks

Brendan Lucier, Ishai Menache, Seffi Naor and Jonathan Yaniv.
Efficient Online Scheduling for Deadline-Sensitive Jobs

Alex Matveev and Nir Shavit.
Reduced Hardware Transactions: A New Approach to Hybrid Transactional Memory

Julian Shun, Guy Blelloch, Jeremy Fineman and Phillip Gibbons.
Reducing Contention Through Priority Updates

Thomas Janson and Christian Schindelhauer.
Broadcasting in Logarithmic Time for Ad Hoc Network Nodes on a Line using MIMO

Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald and Alexandre Stauffer.
Balls-into-Bins with Nearly Optimal Load Distribution

Danny Dolev, Matthias Függer, Christoph Lenzen, Martin Perner and Ulrich Schmid.
HEX: Scaling Honeycombs is Easier than Scaling Clock Trees

Michael A. Bender, David P. Bunde, Vitus J. Leung, Samuel Mccauley and Cynthia A. Phillips.
Efficient Scheduling to Minimize Calibrations

Yehuda Afek, Anat Bremler-Barr and Liron Schiff.
Recursive Design of Hardware Priority Queues

Yossi Azar, Naama Ben-Aroya, Nikhil Devanur and Navendu Jain.
Cloud Scheduling with Setup Cost

Grey Ballard, Aydin Buluc, James Demmel, Laura Grigori, Benjamin Lipshitz, Oded Schwartz and Sivan Toledo.
Communication Optimal Parallel Multiplication of Sparse Random Matrices

Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman and Scott Roche.
Coalescing-Branching Random Walks on Graphs

Grey Ballard, James Demmel, Benjamin Lipshitz, Oded Schwartz and Sivan Toledo.
Communication Efficient Gaussian Elimination with Partial Pivoting using a Shape Morphing Data Layout

Brief announcements:

Rajesh Chitnis, Mohammadtaghi Hajiaghayi, Jonathan Katz and Koyel Mukherjee.
A Game-Theoretic Model Motivated by the DARPA Network Challenge

Sungjin Im and Benjamin Moseley.
Online Batch Scheduling for Flow Objectives

Amotz Bar-Noy, Ben Baumer and Dror Rawitz.
Set It and Forget It: Approximating the Set Once Strip Cover Problem

Martin Hoefer and Thomas Kesselheim.
Universally Truthful Secondary Spectrum Auctions

James Edwards and Uzi Vishkin.
Truly Parallel Burrows-Wheeler Compression and Decompression

Stephan Diestelhorst, Martin Nowack, Michael Spear and Christof Fetzer.
Between All and Nothing --- Versatile Aborts in Hardware Transactional Memory

Konrad Siek and Pawel T. Wojciechowski.
Towards a Fully-Articulated Pessimistic Distributed Transactional Memory

Magnus M. Halldorsson.
Locality in Wireless Scheduling