The 32nd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA 2020
Virtual Conference Schedule

July 14, 2020

Tutorial Sessions

13:00 - 16:00 Research and Teaching with OpenCilk Dorothy Curtis, I-Ting Angelina Lee, Charles E. Leiserson, Tao B. Schardl Slack channel Go to Slack channel
16:00 - 17:30 Implementing Parallel Tree Structure in Shared-Memory Yihan Sun Slack channel Go to Slack channel

July 15, 2020

Best Paper Session :: Slack channel Go to Slack channel

9:00 - 9:05 Opening Remarks
9:05 - 9:30 A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence Lazar Milenkovic and Shay Solomon DOI paper
9:30 - 9:55 Parallel Planar Subgraph Isomorphism and Vertex Connectivity Lukas Gianinazzi and Torsten Hoefler DOI paper
9:55 - 10:20 Sublinear Algorithms in T-interval Dynamic Networks Irvan Jahja and Haifeng Yu DOI paper
10:20 - 10:45 Faster Deterministic All Pairs Shortest Paths in Congest Model Udit Agarwal and Vijaya Ramachandran DOI paper
10:45 - 11:10 Optimal Parallel Algorithms in the Binary-Forking Model Guy Blelloch, Jeremy Fineman, Yan Gu and Yihan Sun DOI paper

Virtual Session 1 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

11:30 - 11:40 Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking Zhixiang Gu, Jose Moreira, David Edelsohn and Ariful Azad DOI paper
11:40 - 11:50 Randomized Incremental Convex Hull is Highly Parallel Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun DOI paper
11:50 - 12:00 On the Hardness of Massively Parallel Computation Kai-Min Chung, Kuan-Yi Ho and Xiaorui Sun DOI paper
12:00 - 12:10 Brief Announcement: ParlayLib - A toolkit for parallel programming on shared-memory multicore machines Guy Blelloch, Daniel Anderson and Laxman Dhulipala DOI paper
12:10 - 12:20 Brief Announcement: Communication-Optimal Tilings for Projective Nested Loops with Arbitrary Bounds Grace Dinh and James Demmel DOI paper
12:20 - 12:30 Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation Problem Jannik Castenow, Peter Kling, Till Knollmann and Friedhelm Meyer Auf der Heide DOI paper

Virtual Session 2 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

13:00 - 13:10 Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis Michael Bender, Rezaul Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan Liu, Jayson Lynch and Helen Xu DOI paper
13:10 - 13:20 How to Manage High-Bandwidth Memory Automatically Rathish Das, Kunal Agrawal, Michael Bender, Jonathan Berry, Benjamin Moseley and Cynthia Phillips DOI paper
13:20 - 13:30 Brief Announcement: Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory Alek Westover and William Kuszmaul DOI paper
13:30 - 13:40 Brief Announcement: Green Paging and Parallel Paging Enoch Peserico and Michele Scquizzato DOI paper
13:40 - 13:50 Brief Announcement: Paging for Multicore Architectures: Lower Bounds and Separation of Paging Strategies Helen Xu and Shahin Kamali DOI paper
13:50 - 14:00 Brief Announcement: Balanced Partitioning of several Cache-Oblivious Algorithms Yuan Tang DOI paper

Virtual Session 3 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

14:10 - 14:20 The Append Memory Model: Why BlockDAGs Excel Blockchains Darya Melnyk and Roger Wattenhofer DOI paper
14:20 - 14:30 Fast Byzantine Agreement for Permissioned Distributed Ledgers Thomas Locher DOI paper
14:30 - 14:40 Brief Announcement: Cross-Chain Payment Protocols with Success Guarantees Rob van Glabbeek, Vincent Gramoli and Pierre Tholoniat DOI paper
14:40 - 14:50 Brief Announcement: A Closer Look at Quantum Distributed Consensus Wojciech Golab and Hao Tan DOI paper

Virtual Session 4 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

15:00 - 15:10 Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures Dan Alistarh, Trevor Brown and Nandini Singhal DOI paper
15:10 - 15:20 Functional Faults Gali Sheffi and Erez Petrank DOI paper
15:20 - 15:30 Brief Announcement: Tracking in Order to Recover: Detectable Recovery of Lock-Free Data Structures Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler and Eleftherios Kosmas DOI paper
15:30 - 15:40 Brief Announcement: Benchmarking Recoverable Mutex Locks Jeffrey Xiao, Zheng Zhang and Wojciech Golab DOI paper
15:40 - 15:50 Brief Announcement: Investigating the Semantics of Futures in Transactional Memory Systems Jingna Zeng, Shady Issa, Seif Haridi, Luis Rodrigues and Paolo Romano DOI paper
15:50 - 16:00 Brief Announcement: Efficient Concurrent Range Queries in B+-trees using RCU-HTM Dimitrios Siakavaras, Panagiotis Billis, Konstantinos Nikas, Georgios Goumas and Nectarios Koziris DOI paper

Virtual Session 5 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

16:10 - 16:20 Contention Resolution with Message Deadlines Kunal Agrawal, Michael Bender, Jeremy Fineman, Seth Gilbert and Maxwell Young DOI paper
16:20 - 16:30 The Recoverable Consensus Hierarchy Wojciech Golab DOI paper
16:30 - 16:40 pTrans: A Scalable Algorithm for Reservation Guarantees in Distributed Systems Yuhan Peng and Peter Varman DOI paper
16:40 - 16:50 On the hardness of red-blue pebble games Pál András Papp and Roger Wattenhofer DOI paper
16:50 - 17:00 Almost Universal Anonymous Rendezvous in the Plane Sébastien Bouchard, Yoann Dieudonne, Andrzej Pelc and Franck Petit DOI paper
17:00 - 17:10 Non-Linear Ski Rental Boaz Patt-Shamir and Evyatar Yadai DOI paper
17:10 - 17:20 Spectral Lower Bounds on the I/O Complexity of Computation Graphs Saachi Jain and Matei Zaharia DOI paper

July 16, 2020

Virtual Session 6 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

9:00 - 9:10 Connected Components on a PRAM in Log Diameter Time Sixue Liu, Robert Tarjan and Peilin Zhong DOI paper
9:10 - 9:20 Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space Artur Czumaj, Peter Davies and Merav Parter DOI paper
9:20 - 9:30 Communication vs synchronisation in parallel string comparison Alexander Tiskin DOI paper
9:30 - 9:40 A Massively Parallel Algorithm for Minimum Weight Vertex Cover Mohsen Ghaffari, Ce Jin and Daan Nilis DOI paper
9:40 - 9:50 Brief Announcement: Communication-Efficient Weighted Reservoir Sampling from Fully Distributed Data Streams Lorenz Hübschle-Schneider and Peter Sanders DOI paper
9:50 - 10:00 Brief Announcement: Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths Nairen Cao, Jeremy Fineman and Katina Russell DOI paper
10:00 - 10:10 Brief Announcement: Efficient Distributed Algorithms for the K-Nearest Neighbors Problem Reza Fathi, Anisur Rahaman Molla and Gopal Pandurangan DOI paper
10:10 - 10:20 Brief Announcement: A local constant approximation factor algorithm for minimum dominating set of certain planar graphs Sharareh Alipour and Amir Jafari DOI paper
10:20 - 10:30 Brief Announcement: Provable neuromorphic advantages for constrained shortest paths James Bradley Aimone, Yang Ho, Ojas D. Parekh, Cynthia Phillips, Ali Pinar, William M. Severa and Yipu Wang DOI paper

Virtual Session 7 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

10:45 - 10:55 Deterministic Leader Election in Anonymous Radio Networks Avery Miller, Andrzej Pelc and Ram Narayan Yadav DOI paper
10:55 - 11:05 Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model Michael Feldmann, Ardalan Khazraei and Christian Scheideler DOI paper
11:05 - 11:15 Efficient Local Medium Access Paweł Garncarek, Tomasz Jurdziński and Dariusz Kowalski DOI paper
11:15 - 11:25 Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast Faith Ellen and Seth Gilbert DOI paper
11:25 - 11:35 Brief Announcement: Network Partitioning and Avoidable Contention Yishai Oltchik and Oded Schwartz DOI paper
11:35 - 11:45 Brief Announcement: A Queueing Network Based Distributed Laplacian Solver Iqra Altaf Gillani and Amitabha Bagchi DOI paper

Business Meeting

12:00 - 13:00 Business Meeting

Virtual Session 8 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

13:00 - 13:10 Brief Announcement: Sparse Tensor Transpositions Suzanne Mueller, Peter Ahrens, Stephen Chou, Fredrik Kjolstad and Saman Amarasinghe DOI paper
13:10 - 13:20 Brief Announcement: Communication Lower Bounds of Convolutions in CNNs Xiaoyang Zhang, Junmin Xiao and Guangming Tan DOI paper
13:20 - 13:30 Brief Announcement: On the Limits of Parallelizing Convolutional Neural Networks on GPUs Behnam Pourghassemi, Chenghao Zhang, Joo Hwan Lee and Aparna Chandramowlishwaran DOI paper
13:30 - 13:40 Brief Announcement: A Computational Model for Tensor Core Units Rezaul Chowdhury, Francesco Silvestri and Flavio Vella DOI paper

Virtual Session 9 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

13:55 - 14:05 Commitment and slack for online load maximization Samin Jamalabadi, Chris Schwiegelshohn and Uwe Schwiegelshohn DOI paper
14:05 - 14:15 Predicate Detection to Solve Combinatorial Optimization Problems Vijay Garg DOI paper
14:15 - 14:25 Optimal Resource Allocation for Elastic and Inelastic Jobs Benjamin Berg, Mor Harchol, Justin Whitehouse, Weina Wang and Benjamin Moseley DOI paper
14:25 - 14:35 Scheduling Flows on a Switch to Optimize Response Times Hamidreza Jahanjou, Rajmohan Rajaraman and David Stalfa DOI paper
14:35 - 14:55 The Online Multi-Commodity Facility Location Problem Jannik Castenow, Björn Feldkord, Till Knollmann, Manuel Malatyali and Friedhelm Meyer Auf der Heide DOI paper

Virtual Session 10 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

15:00 - 15:10 Unconditional lower bounds for Adaptive Massively Parallel Computation Moses Charikar, Weiyun Ma and Li-Yang Tan DOI paper
15:10 - 15:20 Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model Daniel Anderson, Guy Blelloch and Kanat Tangwongsan DOI paper
15:20 - 15:30 Simple Local Computation Algorithms for the General Lovasz Local Lemma Dimitris Achlioptas, Themis Gouleakis and Fotis Iliopoulos DOI paper
15:30 - 15:40 Brief Announcement: Lockfree Persistent Homology Dmitriy Morozov and Arnur Nigmetov DOI paper
15:40 - 15:50 Brief Announcement: Reconstructing Trees in Parallel Ramtin Afshar, Michael Goodrich, Pedro Matias and Martha Osegueda DOI paper
15:50 - 16:00 Brief Announcement: How fast can you update your MST? (Dynamic algorithms for cluster computing) Lawrence Li and Seth Gilbert DOI paper

Virtual Session 11 :: Slack channel Go to Slack channel :: Youtube Playlist Go to Youtube Playlist

16:15 - 16:25 Approximation Algorithms for Scheduling with Class Constraints Klaus Jansen, Alexandra Lassota and Marten Maack DOI paper
16:25 - 16:35 Priority Scheduling for Interactive Applications Kyle Singer, Noah Goldstein, Stefan Muller, Kunal Agrawal, I-Ting Lee and Umut Acar DOI paper
16:35 - 16:45 Parallel Load Balancing on Constrained Client-Server Topologies Andrea Clementi, Emanuele Natale and Isabella Ziccardi DOI paper
16:45 - 16:55 Self-Stabilizing Task Allocation In Spite of Noise Anna Dornhaus, Nancy Lynch, Frederik Mallmann-Trenn, Dominik Pajak and Tsvetomira Radeva DOI paper

Back to main page.