SPAA 2018 Conference Program

SPAA 2018 Program


SPAA 2018 Accepted Regular Papers

Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Parallel Write-Efficient Geometry Algorithms
Guy E. Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. The Parallel Persistent Memory Model
Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Helen Xu. Cache Adaptive Exploration
Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. Distributed Domination on Graph Classes of Bounded Expansion
Nikhil Devanur and Janardhan Kulkarni. A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems
Susanne Albers and Jens Quedenfeld. Optimal Algorithms for Right-Sizing Data Centers
Nicholas Harvey, Christopher Liaw, and Paul Liu. Greedy and Local Ratio Algorithms in the MapReduce Model
Erik D. Demaine and Quanquan C. Liu. Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers
Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank. BQ: A Lock-Free Queue with Batching
Björn Feldkord and Friedhelm Meyer Auf der Heide. Online Facility Location with Mobile Facilities
Wei Quan Lim, Seth Gilbert, and Kunal Agrawal. Parallel Working-Set Search Structures
Janne H. Korhonen and Jukka Suomela. Towards a complexity theory for the congested clique
Andreia Correia, Pascal Felber, and Pedro Ramalhete. Romulus: Efficient Algorithms for Persistent Transactional Memory
Barbara Geissmann and Lukas Gianinazzi. Minimum Cuts in Near-linear Work and Low Depth
Amir Gholami, Ariful Azad, Peter Jin, Kurt Keutzer, and Aydin Buluc. Integrated Model, Batch and Domain Parallelism in Training Neural Networks
Predrag Gruevski, William Hasenplaugh, David Lugato, and James Thomas. Laika: Efficient In-Place Scheduling for 3D Mesh Graph Computations
Shirel Attali, Merav Parter, David Peleg, and Shay Solomon. Wireless Expanders
Haim Kaplan and Shay Solomon. Dynamic Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
Harald Räcke, Roy Schwartz, and Richard Stotz. Trees for Vertex Cuts, Hypergraph Cuts and Minimum Hypergraph Bisection
Peter Robinson, Christian Scheideler, and Alexander Setzer. Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary
Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. The Inherent Cost of Remembering Consistently
Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and Impossibilities for Distributed Subgraph Detection
Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-preemptive Scheduling on Unrelated Machines with Rejections
Tsvi Kopelowitz, Ely Porat, and Yair Rosenmutter. Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
Guy Even, Moti Medina, and Dror Rawitz. Online Generalized Caching with Varying Weights and Costs
Simon Collet and Amos Korman. Intense Competition can Drive Selfish Explorers to Optimize Coverage
Dan Alistarh, Syed Kamran Haider, Raphael Kübler, and Giorgi Nadiradze. The Transactional Conflict Problem
Noga Alon, Yossi Azar, and Mark Berlin. The Price of Bounded Preemption
Panagiota Fatourou, Nikolaos D. Kallimanis, and Thomas Ropars. An Efficient Wait-free Resizable Hash Table
Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations
Ojas Parekh, Cynthia Phillips, Conrad D. James, and James Aimone. Constant Depth and Subcubic Size Threshold Circuits for Matrix Multiplication
Dan Alistarh, Trevor Brown, Justin Kopinsky, Giorgi Nadiradze, Jerry Li. Distributionally Linearizable Data Structures
Ori Rottenstreich, Yossi Kanizo, Haim Kaplan, and Jennifer Rexford. Accurate Traffic Splitting on Commodity Switches
Kjell Winblad, Kostis Sagonas, and Bengt Jonsson. Lock-free Contention Adapting Search Trees
Laxman Dhulipala, Guy Blelloch, and Julian Shun. Theoretically Efficient Parallel Graph Algorithms are Fast and Scalable
Grey Ballard, James Demmel, Laura Grigori, Mathias Jacquelin, and Nicholas Knight. A 3D Parallel Algorithm for QR Decomposition

SPAA 2018 Accepted Brief Announcements

Ellis Giles, Kshitij Doshi, and Peter Varman. Brief Announcement: Hardware Transactional Persistent Memory
Alvaro Velasquez and Sumit Kumar Jha. Brief Announcement: Parallel Transitive Closure Within 3D Crosspoint Memory
Tao B. Schardl, I-Ting Angelina Lee, and Charles E. Leiserson. Brief Announcement: Open Cilk
Saurabh Kumar and Samir Khuller. Brief Announcement: A greedy 2 approximation to the active time problem
Leonid Barenboim and Yaniv Tzur. Brief Announcement: Distributed Symmetry-Breaking with Improved Vertex-Averaged Complexity
Manuel Pöter and Jesper Larsson Träff. Brief Announcement: Stamp-it: A more Thread-efficient, Concurrent Memory Reclamation Scheme in the C++ Memory Model
Johannes Schaefer and Friedhelm Meyer Auf der Heide. Brief Announcement: Communication in Systems of Home Based Mobile Agents
Christina Kolb, Daniel Jung, Jannik Sundermeier, and Christian Scheideler. Brief Announcement: Competitive Routing in Hybrid Communication Networks
Marco Bressan, Enoch Peserico, and Luca Pretto. Brief Announcement: On Approximating PageRank Locally with Sublinear Query Complexity
Ink Chinavinijkul, Jacob Newcomb, Lingzhi Xi, and David Bunde. Brief Announcement: Coloring-based task mapping for Dragonfly systems
Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Brief Announcement: Approximation Algorithms for Preemptive Resource Allocation