SPAA 2011 Program: ------------------ Friday, June 3 7:00-9:00 pm Welcome Reception, Miro's Lounge at the Crowne Plaza, 282 Almaden Blvd Saturday, June 4 8:30-10:10 Session 1 (Parallel Algorithms) Chair: Rajmohan Rajaraman Grey Ballard, James Demmel, Olga Holtz and Oded Schwartz Graph Expansion and Communication Costs of Fast Matrix Multiplication 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 Guy Blelloch, Richard Peng and Kanat Tangwongsan Linear-Work Greedy Parallel Approximate Set Cover and Variants Umut Acar, Andrew Cotter, Benoît Hudson and Duru Türkoglu Parallelism in Dynamic Well-Spaced Point Sets 10:10-10:40 Coffee Break 10:40-12:20 Session 2 (Transactional Memory and Locks) Chair: Victor Luchangco Victor Pankratius and Ali-Reza Adl-Tabatabai A Study of Transactional Memory vs. Locks in Practice Torvald Riegel, Patrick Marlier, Martin Nowack, Pascal Felber and Christof Fetzer Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations Dave Dice, Virendra Marathe and Nir Shavit Flat-Combining NUMA Locks Edya Ladan-Mozes, I-Ting Lee and Dmitriy Vyukov Location-Based Memory Barriers 12:20-01:50 Lunch 01:50-3:30 Session 3 (Parallel Computing) Chair: Geppino Pucci Silvio Lattanzi, Benjamin Moseley, Siddharth Suri and Sergei Vassilvitskii Filtering: A Method for Solving Graph Problems in MapReduce Victoria Caparros Cabezas and Phillip Stanley-Marbell Parallelism and Data Movement Characterization of Contemporary Application Classes Martin Wimmer and Jesper Larsson Träff Work-Stealing for Mixed-Mode Parallelism by Deterministic Team-building Yuan Tang, Rezaul Chowdhury, Bradley Kuszmaul, Chi-Keung Luk and Charles Leiserson The Pochoir Stencil Compiler 3:30-4:00 Coffee Break 4:00-4:40 Session 4 (Brief Announcements I) Chair: Gopal Pandurangan Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch and Josef Widder Brief Announcement: Full Reversal Routing as a Linear Dynamical System George Caragea and Uzi Vishkin Brief Announcement: Better Speedups for Parallel Max-Flow Guillaume Aupy, Anne Benoit, Fanny Dufossé and Yves Robert Brief Announcement: Reclaiming the Energy of a Schedule, Models and Algorithms Alejandro López-Ortiz and Alejandro Salinger Brief Announcement: Paging for Multicore Processors 4:45-6:00 Session 5 A Panel Discussion on Teaching Parallelism Sunday, June 5 8:30-10:10 Session 6 (Coordination Algorithms) Chair: Jennifer Welch Bastian Degener, Barbara Kempkes, Tobias Langner, Friedhelm Meyer Auf Der Heide, Peter Pietrzyk, and Roger Wattenhofer A Tight Runtime Bound for Synchronous Gathering of Autonomous Robots with Limited Visibility Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald and Christian Scheideler Stabilizing Consensus with the Power of Two Choices Peter Kling and Friedhelm Meyer Auf Der Heide Convergence of Local Communication Chain Strategies via Linear Transformations Patrick Briest and Christoph Raupach The Car Sharing Problem 10:10-10:40 Coffee Break 10:40-12:20 Session 7 (Games and Approximation Algorithms) Chair: Rohit Khandekar Martin Hoefer, Thomas Kesselheim and Berthold Voecking Approximation Algorithms for Secondary Spectrum Auctions Thomas Erlebach, Tom Grant and Frank Kammer Maximising Lifetime for Fault-Tolerant Target Coverage in Sensor Networks Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna and Giuseppe Persiano Convergence to Equilibrium of Logit Dynamics for Strategic Games Mohammadamin Fazli, Shayan Ehsani, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Morteza Saghafian, Saber Shokatfadaee and Mohammadali Safari On a Bounded Budget Network Creation Game 12:20-01:50 Lunch 1:50-3:30 Session 8 (Network and P2P Algorithms) Chair: Pierre Fraignaiud Guy Even and Moti Medina Online Packet-Routing in Grids with Bounded Buffers Cyril Gavoille and Christian Sommer Sparse Spanners vs. Compact Routing Sebastian Kniesburges, Christian Scheideler and Andreas Koutsopoulos Re-Chord: A Self-Stabilizing Chord Overlay Network Yossi Azar, Aviv Nisgav and Boaz Patt-Shamir Recommender Systems With Non-Binary Grades 3:30-4:00 Coffee Break 4:00-5:10 Session 9 (Brief Announcements II) Chair: Geppino Pucci Mieszko Lis, Keun Sup Shim, Myong Hyon Cho, Christopher Fletcher, Omer Khan and Srinivas Devadas Brief Announcement: Distributed Shared Memory based on Computation Migration Grey Ballard, Andrew Gearhart and James Demmel Brief Announcement: Communication Bounds for Heterogeneous Architectures Michael Goodrich and Michael Mitzenmacher Brief Announcement: Large-Scale Multimaps Francesco Versaci and Keshav Pingali Brief Announcement: Processor Allocation for Optimistic Parallelization of Irregular Programs Youngjoon Jo and Milind Kulkarni Brief Announcement: Locality-Enhancing Loop Transformations for Tree Traversal Algorithms Lei Li, Tianshi Chen, Yunji Chen, Ling Li and Cheng Qian Brief Announcement: Program Regularization in Verifying Memory Consistency H B Acharya and Mohamed Gouda Brief Announcement: RedRem: A Parallel Redundancy Remover 6:00-7:15 FCRC Plenary Talk 2010 ACM Turing Award Lecture Leslie G. Valiant, Harvard University 7:30-10:00 Banquet and Business Meeting Monday, June 6 8:30-10:10 Session 10 (Scheduling and Network Communication) Chair: Rajmohan Rajaraman 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 Benjamin Moseley, Anirban Dasgupta, Ravi Kumar and Tamas Sarlos On Scheduling in Map-Reduce and Flow-Shops Thomas Locher Finding Heavy Distinct Hitters in Data Streams 10:10-10:40 Coffee Break 10:40-11:20 Session 11 (Brief Announcements III) Chair: Jennifer Welch David Dice Brief Announcement: A Partitioned Ticket Lock Vincent Gramoli and Rachid Guerraoui Brief Announcement: Transaction Polymorphism David Dice and Oleksandr Otenko Brief Announcement: MultiLane - A Concurrent Blocking Multiset Tyler Crain, Damien Imbs and Michel Raynal Brief Announcement: Read Invisibility, Virtual World Consistency and Permissiveness are Compatible 11:30-12:30 FCRC Plenary Talk David A. Ferruci, IBM IBM's Watson/DeepQA 12:30-2:00 Lunch 02:00-3:40 Session 12 (Concurrency Control) Chair: Marcos K. Aguilera James Aspnes and Faith Ellen Tight Bounds for Anonymous Adopt-Commit Objects Panagiota Fatourou and Nikolaos Kallimanis A Highly-Efficient Wait-Free Universal Construction Håkan Sundell, Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas A Lock-Free Algorithm for Concurrent Bags Mark C. Jeffrey and J. Gregory Steffan Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation 3:40-4:00 Break 4:00-5:15 Session 13 (Cache Hierarchies and Memory Sharing) Chair: Susanne Albers Guy Blelloch, Jeremy Fineman, Phillip Gibbons and Harsha Vardhan Simhadri Scheduling Irregular Parallel Computations on Hierarchical Caches Michael Sindelar, Ramesh Sitaraman and Prashant Shenoy Sharing-Aware Algorithms for Virtual Machine Colocation Michael Goodrich Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data