Program 2021

ACM Proceedings available HERE (or

Day 1 (Tues, Jul 6):

9:30- 9:45 Introduction

A1: 9:50-11:00 – Distributed (7) (session chair: Rajmohan Rajaraman)

  • Keren Censor-Hillel, Victor Kolobov and Gregory Schwartzman. Finding Subgraphs in Highly Dynamic Networks (Video)
  • Keren Censor-Hillel, Dean Leitersdorf and Volodymyr Polosukhin. On Sparsity Awareness in Distributed Computations (Video)
  • Barun GorainAvery Miller and Andrzej Pelc. Four Shades of Deterministic Leader Election in Anonymous Networks (Video)
  • Yi-Jun Chang, Ran Duan and Shunhua Jiang. Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election (Video)
  • Dariusz Kowalski and Miguel A. Mosteiro. Supervised Consensus in Anonymous Dynamic Networks (Video)
  • Brief Announcement: Adam Gancorz, Tomasz Jurdzinski, Mateusz Lewko and Andrzej Pelc. Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels (Video)
  • Brief Announcement: Andrew Berns. Network Scaffolding for Efficient Stabilization of the Chord Overlay Network (Video)

A2: 11:20-12:20 Distributed + Shared Memory (6) (session chair: Gopal Pandurangan)

  • Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela and Jara Uitto. Efficient Load-Balancing through Distributed Token Dropping (Video)
  • Seth Gilbert, Uri Meir, Ami Paz and Gregory Schwartzman. On the Complexity of Load Balancing in Dynamic Networks (Video)
  • Yannic Maus. Distributed Graph Coloring Made Easy (Video)
  • Vijaya Ramachandran and Elaine Shi. Data Oblivious Algorithms for Multicores (Video)
  • Brief Announcement:  David Gureya, João Barreto and Vladimir Vlassov. BALM: QoS-Aware Memory Bandwidth Partitioning for Multi-Socket Cloud Nodes (Video)
  • Brief Announcement:  Diego Cepeda and Wojciech Golab. PHPRX: An Efficient Hash Table for Persistent Memory (Video)

A3: 13:00-14:00 Shared Memory (6) (session chair: Vahab Mirrokni)

  • Hongbo Kang, Phillip B. Gibbons, Guy E. Blelloch, Laxman Dhulipala, Yan Gu and Charles McGuffey. The Processing-in-Memory Model (Video)
  • Daniel AndersonGuy Blelloch, Anubhav Baweja and Umut Acar. Efficient Parallel Self-adjusting Computation (Video)
  • Gal Sela and Erez Petrank. Durable Queues: The Second Amendment (Video)
  • Dave Dice and Alex Kogan. Hemlock : Compact and Scalable Mutual Exclusion (Video)
  • Nikita Koval, Alexander Fedorov and Dan Alistarh. A Scalable Concurrent Algorithm for Dynamic Connectivity (Video)
  • Brief Announcement:  Gali Sheffi, Maurice Herlihy and Erez Petrank. VBR: Version Based Reclamation (Video)

14:30-16:00 Panel 

“Architecture-Friendly Algorithms versus Algorithm-Friendly Architectures”Panelists: Guy Blelloch (Carnegie Mellon University), Bill Dally (NVIDIA), Margaret Martonosi (Princeton University), Uzi Vishkin (University of Maryland), Kathy Yelick (University of California, Berkeley), moderator: Vijaya Ramachandran

Day 2 (Wed, Jul 7) 

B1: 9:30-10:20 Race-detection / Data Structure (5) (session chair: Panagiota Fatourou)

  • Yifan Xu, Kunal Agrawal and I-Ting Angelina Lee. Efficient Parallel Determinacy Race Detection for Structured Futures (Video)
  • Grzegorz Kwasniewski, Tal Ben-Nun, Lukas Gianinazzi, Alexandru Calotoiu, Timo Schneider, Alexandros Nikolaos Ziogas, Maciej Besta and Torsten Hoefler. Pebbles, Graphs, and a Pinch of Combinatorics: Towards Tight I/O Lower Bounds for Statically Analyzable Programs (Video)
  • Brief Announcement:  Yifan Xu, Anchengcheng Zhou, Grace Yin, Kunal Agrawal, I-Ting Angelina Lee and Tao B. Schardl. Efficient Access History for Race Detection (Video)
  • Brief Announcement: Sakib Chowdhury and Wojciech Golab. A Scalable Recoverable Skip List for Persistent Memory (Video)
  • Brief Announcement: Yaodong Sheng, Ahmed Hassan and Michael Spear. Semantic Conflict Detection for Transactional Data Structure Libraries (Video)

B2: 11:00-12:20 Best Paper Semifinalists (session chair: Yossi Azar)

  • Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory and Yimin Zhu. Fast Stencil Computations using Fast Fourier Transforms (Video)
  • Susanne Albers and Jens Quedenfeld. Algorithms for Right-Sizing Heterogeneous Data Centers (Video)
  • Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem and Manish Purohit. Non-Clairvoyant Scheduling with Predictions (Video)
  • Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory and Mohammad Javanmard. Low-Span Parallel Algorithms for the Binary-Forking Model (Video)

B3: 13:00-13:30 Best Paper (session chair: Yossi Azar)

13:30-14:30 Business meeting  

Day 3 (Thu, Jul 8) 

C1: 9:30-10:40 ALG (7) (session chair: Friedhelm Meyer auf der Heide)

  • Nikhil Bansal, Seffi Naor and Ohad Talmon. Efficient Online Weighted Multi-Level Paging (Video)
  • Aleksander Figiel, Leon Kellerhals, Rolf Niedermeier, Matthias RostStefan Schmid and Philipp Zschoche. Optimal Virtual Network Embeddings for Tree Topologies (Video)
  • Michael Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Nirjhar Mukherjee, Don Porter, Guido Tagliavini, Janet Vorobyeva and Evan West. Paging and the Address Translation Problem (Video)
  • Janardhan Kulkarni, Stefan Schmid and Pawel Schmidt. Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters (Video)
  • Mozhengfu Liu and Xueyan Tang. Analysis of Busy-Time Scheduling on Heterogeneous Machines (Video)
  • Konstantinos Dogeas, Evripidis Bampis, Fanny Pascual, Giorgio Lucarelli and Alexander Kononov. Speed scaling with explorable uncertainty (Video)
  • Brief Announcement: Nathan Beckmann, Phillip B. Gibbons and Charles McGuffey. Block-Granularity-Aware Caching (Video)

C2: 11:00-12:00 Algorithms/Practical-Algorithms (6) (session chair: Julian Shun)

  • Wilhelm Friedemann, Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, Anna Melnichenko, Jannik Peters, Daniel Stephan and Michael Vaichenker. Efficiency and Stability in Euclidean Network Design (Video)
  • Xiaojun Dong, Yan Gu, Yihan Sun and Yunming Zhang. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths (Video)
  • James Aimone, Yang Ho, Ojas Parekh, Cynthia Phillips, Ali Pinar, William Severa and Yipu Wang. Provable Advantages for Graph Algorithms in Spiking Neural Networks (Video)
  • Brief Announcement: Subhash Bhagat and Anisur Rahaman Molla. Min-Max Gathering of Oblivious Robots (Video)
  • Brief Announcement:Rui Li, Yufan Xu, Aravind Sukumaran-Rajam, Atanas Rountev and P Sadayappan. Efficient distributed algorithms for Convolutional Neural Networks (Video)
  • Brief Announcement: Evgeniy Feder, Ichha Rathod, Punit Shyamsukha, Robert Sama, Vitaly Aksenov, Iosif Salem and Stefan Schmid. Toward Self-Adjusting Networks for the Matching Model (Video)

C3: 12:40-13:40 MPC/PRAM (6) (session chair: Yan Gu)

  • Mohammadtaghi HajiaghayiHamed SalehSaeed Seddighin and Xiaorui Sun. String Matching with Wildcards in the Massively Parallel Computation Model (Video)
  • Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrović and Yasamin Nazari. Massively Parallel Algorithms for Distance Approximation and Spanners (Video)
  • Michael Elkin and Shaked Matar. Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work (Video)
  • Lukas Gianinazzi, Maciej Besta, Yannick Schaffner and Torsten Hoefler. Parallel Algorithms for Finding Large Cliques in Sparse Graphs (Video)
  • Andrés López-Martínez, Sagnik Mukhopadhyay and Danupon Nanongkai. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs (Video)
  • Brief Announcement: Ramtin Afshar, Michael T. Goodrich, Pedro Matias and Martha C. Osegueda. Parallel Network Mapping Algorithms (Video)