The 32nd ACM Symposium on Parallelism in Algorithms and Architectures - SPAA 2020
Virtual Conference Schedule
- Attending the virtual edition of SPAA 2020 is free of charge. Please register here. The registration will be pending for approval upon verification of your information.
- After registration, you will receive the link to the Zoom meeting, the Slack channel, and the Gather chat room.
- SPAA 2020 Youtube Channel: https://www.youtube.com/channel/UCSE54kS_0NDo6Xjpr2Bn7EA
- All time in EDT (GMT-4), where the conference was originally located. Convert time zones: CET: +6h, CDT: -1h, PDT: -3h.
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 |
16:00 - 17:30 |
Implementing Parallel Tree Structure in Shared-Memory |
Yihan Sun |
Slack channel |
July 15, 2020
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 |
|
9:30 - 9:55 |
Parallel Planar Subgraph Isomorphism and Vertex Connectivity |
Lukas Gianinazzi and Torsten Hoefler |
|
9:55 - 10:20 |
Sublinear Algorithms in T-interval Dynamic Networks |
Irvan Jahja and Haifeng Yu |
|
10:20 - 10:45 |
Faster Deterministic All Pairs Shortest Paths in Congest Model |
Udit Agarwal and Vijaya Ramachandran |
|
10:45 - 11:10 |
Optimal Parallel Algorithms in the Binary-Forking Model |
Guy Blelloch, Jeremy Fineman, Yan Gu and Yihan Sun |
|
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 |
|
11:40 - 11:50 |
Randomized Incremental Convex Hull is Highly Parallel |
Guy Blelloch, Yan Gu, Julian Shun and Yihan Sun |
|
11:50 - 12:00 |
On the Hardness of Massively Parallel Computation |
Kai-Min Chung, Kuan-Yi Ho and Xiaorui Sun |
|
12:00 - 12:10 |
Brief Announcement: ParlayLib - A toolkit for parallel programming on shared-memory multicore machines |
Guy Blelloch, Daniel Anderson and Laxman Dhulipala |
|
12:10 - 12:20 |
Brief Announcement: Communication-Optimal Tilings for Projective Nested Loops with Arbitrary Bounds |
Grace Dinh and James Demmel |
|
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 |
|
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 |
|
13:10 - 13:20 |
How to Manage High-Bandwidth Memory Automatically |
Rathish Das, Kunal Agrawal, Michael Bender, Jonathan Berry, Benjamin Moseley and Cynthia Phillips |
|
13:20 - 13:30 |
Brief Announcement: Cache-Efficient Parallel-Partition Algorithms using Exclusive-Read-and-Write Memory |
Alek Westover and William Kuszmaul |
|
13:30 - 13:40 |
Brief Announcement: Green Paging and Parallel Paging |
Enoch Peserico and Michele Scquizzato |
|
13:40 - 13:50 |
Brief Announcement: Paging for Multicore Architectures: Lower Bounds and Separation of Paging Strategies |
Helen Xu and Shahin Kamali |
|
13:50 - 14:00 |
Brief Announcement: Balanced Partitioning of several Cache-Oblivious Algorithms |
Yuan Tang |
|
14:10 - 14:20 |
The Append Memory Model: Why BlockDAGs Excel Blockchains |
Darya Melnyk and Roger Wattenhofer |
|
14:20 - 14:30 |
Fast Byzantine Agreement for Permissioned Distributed Ledgers |
Thomas Locher |
|
14:30 - 14:40 |
Brief Announcement: Cross-Chain Payment Protocols with Success Guarantees |
Rob van Glabbeek, Vincent Gramoli and Pierre Tholoniat |
|
14:40 - 14:50 |
Brief Announcement: A Closer Look at Quantum Distributed Consensus |
Wojciech Golab and Hao Tan |
|
15:00 - 15:10 |
Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures |
Dan Alistarh, Trevor Brown and Nandini Singhal |
|
15:10 - 15:20 |
Functional Faults |
Gali Sheffi and Erez Petrank |
|
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 |
|
15:30 - 15:40 |
Brief Announcement: Benchmarking Recoverable Mutex Locks |
Jeffrey Xiao, Zheng Zhang and Wojciech Golab |
|
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 |
|
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 |
|
16:10 - 16:20 |
Contention Resolution with Message Deadlines |
Kunal Agrawal, Michael Bender, Jeremy Fineman, Seth Gilbert and Maxwell Young |
|
16:20 - 16:30 |
The Recoverable Consensus Hierarchy |
Wojciech Golab |
|
16:30 - 16:40 |
pTrans: A Scalable Algorithm for Reservation Guarantees in Distributed Systems |
Yuhan Peng and Peter Varman |
|
16:40 - 16:50 |
On the hardness of red-blue pebble games |
Pál András Papp and Roger Wattenhofer |
|
16:50 - 17:00 |
Almost Universal Anonymous Rendezvous in the Plane |
Sébastien Bouchard, Yoann Dieudonne, Andrzej Pelc and Franck Petit |
|
17:00 - 17:10 |
Non-Linear Ski Rental |
Boaz Patt-Shamir and Evyatar Yadai |
|
17:10 - 17:20 |
Spectral Lower Bounds on the I/O Complexity of Computation Graphs |
Saachi Jain and Matei Zaharia |
|
July 16, 2020
9:00 - 9:10 |
Connected Components on a PRAM in Log Diameter Time |
Sixue Liu, Robert Tarjan and Peilin Zhong |
|
9:10 - 9:20 |
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space |
Artur Czumaj, Peter Davies and Merav Parter |
|
9:20 - 9:30 |
Communication vs synchronisation in parallel string comparison |
Alexander Tiskin |
|
9:30 - 9:40 |
A Massively Parallel Algorithm for Minimum Weight Vertex Cover |
Mohsen Ghaffari, Ce Jin and Daan Nilis |
|
9:40 - 9:50 |
Brief Announcement: Communication-Efficient Weighted Reservoir Sampling from Fully Distributed Data Streams |
Lorenz Hübschle-Schneider and Peter Sanders |
|
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 |
|
10:00 - 10:10 |
Brief Announcement: Efficient Distributed Algorithms for the K-Nearest Neighbors Problem |
Reza Fathi, Anisur Rahaman Molla and Gopal Pandurangan |
|
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 |
|
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 |
|
10:45 - 10:55 |
Deterministic Leader Election in Anonymous Radio Networks |
Avery Miller, Andrzej Pelc and Ram Narayan Yadav |
|
10:55 - 11:05 |
Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model |
Michael Feldmann, Ardalan Khazraei and Christian Scheideler |
|
11:05 - 11:15 |
Efficient Local Medium Access |
Paweł Garncarek, Tomasz Jurdziński and Dariusz Kowalski |
|
11:15 - 11:25 |
Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast |
Faith Ellen and Seth Gilbert |
|
11:25 - 11:35 |
Brief Announcement: Network Partitioning and Avoidable Contention |
Yishai Oltchik and Oded Schwartz |
|
11:35 - 11:45 |
Brief Announcement: A Queueing Network Based Distributed Laplacian Solver |
Iqra Altaf Gillani and Amitabha Bagchi |
|
Business Meeting
12:00 - 13:00 |
Business Meeting |
13:00 - 13:10 |
Brief Announcement: Sparse Tensor Transpositions |
Suzanne Mueller, Peter Ahrens, Stephen Chou, Fredrik Kjolstad and Saman Amarasinghe |
|
13:10 - 13:20 |
Brief Announcement: Communication Lower Bounds of Convolutions in CNNs |
Xiaoyang Zhang, Junmin Xiao and Guangming Tan |
|
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 |
|
13:30 - 13:40 |
Brief Announcement: A Computational Model for Tensor Core Units |
Rezaul Chowdhury, Francesco Silvestri and Flavio Vella |
|
13:55 - 14:05 |
Commitment and slack for online load maximization |
Samin Jamalabadi, Chris Schwiegelshohn and Uwe Schwiegelshohn |
|
14:05 - 14:15 |
Predicate Detection to Solve Combinatorial Optimization Problems |
Vijay Garg |
|
14:15 - 14:25 |
Optimal Resource Allocation for Elastic and Inelastic Jobs |
Benjamin Berg, Mor Harchol, Justin Whitehouse, Weina Wang and Benjamin Moseley |
|
14:25 - 14:35 |
Scheduling Flows on a Switch to Optimize Response Times |
Hamidreza Jahanjou, Rajmohan Rajaraman and David Stalfa |
|
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 |
|
15:00 - 15:10 |
Unconditional lower bounds for Adaptive Massively Parallel Computation |
Moses Charikar, Weiyun Ma and Li-Yang Tan |
|
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 |
|
15:20 - 15:30 |
Simple Local Computation Algorithms for the General Lovasz Local Lemma |
Dimitris Achlioptas, Themis Gouleakis and Fotis Iliopoulos |
|
15:30 - 15:40 |
Brief Announcement: Lockfree Persistent Homology |
Dmitriy Morozov and Arnur Nigmetov |
|
15:40 - 15:50 |
Brief Announcement: Reconstructing Trees in Parallel |
Ramtin Afshar, Michael Goodrich, Pedro Matias and Martha Osegueda |
|
15:50 - 16:00 |
Brief Announcement: How fast can you update your MST? (Dynamic algorithms for cluster computing) |
Lawrence Li and Seth Gilbert |
|
16:15 - 16:25 |
Approximation Algorithms for Scheduling with Class Constraints |
Klaus Jansen, Alexandra Lassota and Marten Maack |
|
16:25 - 16:35 |
Priority Scheduling for Interactive Applications |
Kyle Singer, Noah Goldstein, Stefan Muller, Kunal Agrawal, I-Ting Lee and Umut Acar |
|
16:35 - 16:45 |
Parallel Load Balancing on Constrained Client-Server Topologies |
Andrea Clementi, Emanuele Natale and Isabella Ziccardi |
|
16:45 - 16:55 |
Self-Stabilizing Task Allocation In Spite of Noise |
Anna Dornhaus, Nancy Lynch, Frederik Mallmann-Trenn, Dominik Pajak and Tsvetomira Radeva |
|
Back to main page.