List of accepted papers for SPAA 2011: Regular papers: Thomas Locher Finding Heavy Distinct Hitters in Data Streams Victor Pankratius and Ali-Reza Adl-Tabatabai A Study of Transactional Memory vs. Locks in Practice Guy Even and Moti Medina Online Packet-Routing in Grids with Bounded Buffers James Aspnes and Faith Ellen Tight bounds for anonymous adopt-commit objects Grey Ballard, James Demmel, Olga Holtz and Oded Schwartz Graph Expansion and Communication Costs of Fast Matrix Multiplication Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Vahid Liaghat On a Local Protocol for Concurrent File Transfers Susanne Albers, Antonios Antoniadis and Gero Greiner On Multi-Processor Speed Scaling with Migration Michael Goodrich Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data Cyril Gavoille and Christian Sommer Sparse Spanners vs. Compact Routing Martin Hoefer, Thomas Kesselheim and Berthold Voecking Approximation Algorithms for Secondary Spectrum Auctions Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna and Giuseppe Persiano Convergence to Equilibrium of Logit Dynamics for Strategic Games Thomas Erlebach, Tom Grant and Frank Kammer Maximising Lifetime for Fault-Tolerant Target Coverage in Sensor Networks Patrick Briest and Christoph Raupach The Car Sharing Problem Bastian Degener, Barbara Kempkes, Tobias Langner, Friedhelm Meyer Auf Der Heide, Peter Pietrzyk, and Roger Wattenhofer Runtime analysis of a local, synchronous gathering algorithm for mobile robots Michael Sindelar, Ramesh Sitaraman and Prashant Shenoy Sharing-Aware Algorithms for Virtual Machine Colocation Martin Wimmer and Jesper Larsson Traff Work-stealing for mixed-mode parallelism by deterministic team-building Mohammadamin Fazli, Shayan Ehsani, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Morteza Saghafian, Saber Shokatfadaee and Mohammadali Safari On a Bounded Budget Network Creation Game Yossi Azar, Aviv Nisgav and Boaz Patt-Shamir Recommender Systems With Non-Binary Grades Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald and Christian Scheideler Stabilizing Consensus with the Power of Two Choices Umut Acar, Andrew Cotter, Benoit Hudson and Duru Turkoglu Parallelism in Dynamic Well-Spaced Point Sets Yuan Tang, Rezaul Chowdhury, Bradley Kuszmaul, Chi-Keung Luk and Charles Leiserson The Pochoir Stencil Compiler Peter Kling and Friedhelm Meyer Auf Der Heide Convergence of Local Communication Chain Strategies via Linear Transformations Panagiota Fatourou and Nikolaos Kallimanis A Highly-Efficient Wait-Free Universal Costruction Victoria Caparros Cabezas and Phillip Stanley-Marbell Parallelism and Data Movement Characterization of Contemporary Application Classes Hakan Sundell, Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas A Lock-Free Algorithm for Concurrent Bags Guy Blelloch, Jeremy Fineman, Phillip Gibbons and Harsha Vardhan Simhadri Scheduling Irregular Parallel Computations on Hierarchical Caches Torvald Riegel, Patrick Marlier, Martin Nowack, Pascal Felber and Christof Fetzer Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations Sebastian Kniesburges, Christian Scheideler and Andreas Koutsopoulos Re-Chord: A self-stabilizing Chord overlay network Silvio Lattanzi, Benjamin Moseley, Siddharth Suri and Sergei Vassilvitskii Filtering: A Method for Solving Graph Problems in MapReduce Benjamin Moseley, Anirban Dasgupta, Ravi Kumar and Tamas Sarlos On Scheduling in Map-Reduce and Flow-Shops Guy Blelloch, Anupam Gupta, Ioannis Koutis, Gary Miller, Richard Peng and Kanat Tangwongsan Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs Edya Ladan-Mozes, I-Ting Lee and Dmitriy Vyukov Location-Based Memory Barriers Guy Blelloch, Richard Peng and Kanat Tangwongsan Linear-Work Greedy Parallel Approximation Algorithms for Set Covering and Variants Dave Dice, Virendra Marathe and Nir Shavit Flat-Combining NUMA Locks Mark C. Jeffrey and J. Gregory Steffan Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation Brief announcements: Lei Li, Tianshi Chen, Yunji Chen, Ling Li and Cheng Qian Program Regularization in Verifying Memory Consistency Francesco Versaci and Keshav Pingali Processor Allocation for Optimistic Parallelization Tyler Crain, Damien Imbs and Michel Raynal Read invisibility, virtual world consistency and permissiveness are compatible Michael Goodrich and Michael Mitzenmacher Parallel and External-Memory Multimaps H B Acharya and Mohamed Gouda RedRem: A Parallel Redundancy Remover Grey Ballard, Andrew Gearhart and James Demmel Communication Bounds for Heterogeneous Architectures Vincent Gramoli and Rachid Guerraoui Transaction Polymorphism Guillaume Aupy, Anne Benoit, Fanny Dufosse and Yves Robert Reclaiming the energy of a schedule: models and algorithms Bernadette Charron-Bost, Matthias Fugger, Jennifer L. Welch and Josef Widder Full Reversal Routing as a Linear Dynamical System Youngjoon Jo and Milind Kulkarni Locality-enhancing loop transformations for parallel tree traversal algorithms Alejandro Lopez-Ortiz and Alejandro Salinger Paging for Multicore Processors Mieszko Lis, Keun Sup Shim, Myong Hyon Cho, Christopher Fletcher, Omer Khan and Srinivas Devadas A Computation Migration Architecture for Distributed Shared Memory Without Directories David Dice A Partitioned Ticket Lock David Dice and Oleksandr Otenko MultiLane : a concurrent blocking multiset George Caragea and Uzi Vishkin Better Speedups for Parallel Max-Flow