Monday, July 11th
09:00 – 10:30 (Monticello) Tutorial: ParlayLib: Fast and Scalable Parallelism for Everyone
10:30 – 12:00 (Monticello) Tutorial: Recent Progress in Practical State-Machine Replication Systems: Geo-Replication, Randomization, RDMA
in parallel with
09:00 – 12:00 (Bedford) Tutorial: Fast Fourier and Gauss Transforms as Fundamental Components of Fast Stencil Computations
12:00 – 14:00 (Mount Vernon) Lunch Break
14:00 – 18:00 (Bedford) Workshop on Large-Scale Parallel Graph Processing
18:30 – 20:30 (Grange/Library) Welcome Reception
Tuesday, July 12th (lunch in Mount Vernon, all other events in Ballroom North)
08:45 – 08:50 Opening Remarks
Session 1: Distributed Computing on Graphs, Tim Kaler
08:50 – 09:13 Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
09:13 – 09:36 Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
09:36 – 09:59 Adaptive Massively Parallel Algorithms for Cut Problems
09:59 – 10:22 Massively Parallel Algorithms for b-Matching
10:22 – 10:45 Average Awake Complexity of MIS and Matching
10:45 – 10:52 Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics
10:52 – 11:20 AM Coffee Break
Keynote Talk I, Chair: I-Ting Angelina Lee
11:20 – 12:20 Keynote Talk: Large Scale Parallel Sparse Matrix Streaming Graph/Network Analysis
by Jeremy Kepner, MIT Lincoln Laboratory Supercomputing Center
12:20 – 13:50 Lunch Break
Session 2: Distributed Algorithms, Chair: Guy Blelloch
13:50 – 14:13 Preparing for Disaster: Leveraging Precomputation to Efficiently Repair Graph Structures Upon Failures
14:13 – 14:36 The Energy Complexity of Las Vegas Leader Election
14:36 – 14:59 A Fully-Distributed Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables
14:59 – 15:06 Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion
15:06 – 15:13 Brief Announcement: Composable dynamic secure emulation
15:13 – 15:40 PM Coffee Break
Session 3: Networks and Communications, Chair: Phillip B. Gibbons
15:40 – 16:03 Robust and Optimal Contention Resolution without Collision Detection
16:03 – 16:26 Contention Resolution for Coded Radio Networks
16:26 – 16:49 Achieving Sublinear Complexity under Constant T in T-interval Dynamic Networks
16:49 – 16:56 Brief Announcement: Fast(er) Construction of Round-optimal n-Block Broadcast Schedules
Session 4: Cache and Memory, Chair: Yan Gu
17:00 – 17:23 Automatic HBM Management: Models and Algorithms
17:23 – 17:46 Competitive Algorithms for Block-Aware Caching
17:46 – 17:53 Brief Announcement: Spatial Locality and Granularity Change in Caching
18:00 – 19:00 Business Meeting
Wednesday, July 13th (lunch in Mount Vernon, all other events in Ballroom North)
Session 5: Best Paper Session, Chair: Tao B. Schardl
09:00 – 09:23 Parallel Shortest Paths with Negative Edge Weights
09:23 – 09:46 Parallel Batch-Dynamic Algorithms for k-Core Decomposition and Related Graph Problems
09:46 – 10:09 Online Parallel Paging with Optimal Makespan
10:09 – 10:32 PREP-UC: A Practical Replicated Persistent Universal Construction
10:32 – 11:00 AM Coffee Break
Keynote Talk II, Chair: I-Ting Angelina Lee
11:00 – 12:00 Keynote Talk: Algorithm Improvement: How Fast Has It Been and How Much Farther Can It Go?
by Neil Thompson, Massachusetts Institute of Technology
12:00 – 13:30 Lunch Break
Session 6: Parallel Algorithms and Data Structures, Chair: Laxman Dhulipala
13:30 – 13:53 Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering
13:53 – 14:16 Scalable Fine-Grained Parallel Cycle Enumeration Algorithms
14:16 – 14:39 Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
14:39 – 15:02 Parallel Cover Trees and their Applications
15:02 – 15:09 Brief Announcement: A Parallel (Δ,Γ)-Stepping Algorithm for the Constrained Shortest Path Problem
15:09 – 15:16 Brief Announcement: Faster Stencil Computations using Gaussian Approximations
15:16 – 15:45 PM Coffee Break
Session 7: Concurrency and Synchronization, Chair: Julian Shun
15:45 – 16:08 NUMA-Aware Recoverable Mutex Lock
16:08 – 16:31 wCQ: A Fast Wait-Free Queue with Bounded Memory Usage
16:31 – 16:54 HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures
16:54 – 17:17 Performance Analysis and Modelling of Concurrent Multi-access Data Structures
Session 8: Scheduling, Chair: Kunal Agrawal
17:20 – 17:43 The k-Server with Preferences Problem
17:43 – 18:06 Permutation Predictions for Non-Clairvoyant Scheduling
18:06 – 18:29 Balancing Flow Time and Energy Consumption
18:29 – 18:36 Brief Announcement: Nested Active-Time Scheduling
18:36 – 18:43 Brief Announcement: Towards a More Robust Algorithm for Flow Time Scheduling with Predictions
Thursday, July 14 (all events in Ballroom North)
Session 9: More Scheduling, Chair: Rathish Das
09:00 – 09:23 Balanced Allocations in Batches: Simplified and Generalized
09:23 – 09:46 Approximate Dynamic Balanced Graph Partitioning
09:46 – 10:09 Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too
10:09 – 10:16 Brief Announcement: Tight Bounds for Repeated Balls-into-Bins
10:16 – 10:45 AM Coffee Break
Session 10: Matrix-Based Algorithms and I/O Bounds, Chair: Rezaul A. Chowdhury
10:45 – 11:08 I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels
11:08 – 11:31 Sparse matrix multiplication in the low-bandwidth model
11:31 – 11:38 Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds
11:38 – 11:45 Brief Announcement: On the I/O complexity for Hybrid Integer Multiplication Algorithms in the Sequential and Parallel Distributed Memory Model
The list of accepted papers is available now!
- Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient
by Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun - Parallel Cover Trees and their Applications
by Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang - Parallel Shortest Paths with Negative Edge Weights
by Nairen Cao, Jeremy T. Fineman, and Katina Russell - I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels
by Olivier Beaumont, Lionel Eyraud-Dubois, Julien Langou and Mathieu Vérité - HybriDS: Cache-Conscious Concurrent Data Structures for Near-Memory Processing Architectures
by Jiwon Choe, Andrew Crotty, Tali Moreshet, Maurice Herlihy, and R. Iris Bahar - The k-Server with Preferences Problem
by Jannik, Castenow, Björn Feldkord, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer auf der Heide - Approximate Dynamic Balanced Graph Partitioning
by Harald Räcke, Stefan Schmid, and Ruslan Zabrodin - Preparing for Disaster: Leveraging Precomputation to Efficiently Repair Graph Structures Upon Failures
by Calvin Newport, Nitin Vaidya, and Alex Weaver - Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
by Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň - Average Awake Complexity of MIS and Matching
by Mohsen Ghaffari and Julian Portmann - Competitive Algorithms for Block-Aware Caching
by Christian Coester, Roie Levin, Ohad Talmon, and Joseph (Seffi) Naor - PREP-UC: A Practical Replicated Persistent Universal Construction
by Guy Coccimiglio, Trevor Brown, and Srivatsan Ravi - Parallel Batch-Dynamic Algorithms for $k$-Core Decomposition and Related Graph Problems
by Quanquan C. Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun - Robust and Optimal Contention Resolution without Collision Detection
by Yonggang Jiang and Chaodong Zheng - Automatic HBM Management: Models and Algorithms
by Daniel DeLayo, Kenny Zhang, Michael Bender, Cynthia Phillips, Kunal Agrawal, Benjamin Moseley, Rathish Das, and Jonathan Berry - Achieving Sublinear Complexity under Constant T in T-interval Dynamic Networks
by Ruomu Hou, Irvan Jahja, Yucheng Sun, Jiyan Wu, and Haifeng Yu - A Fast Wait-Free Queue with Bounded Memory Usage
by Ruslan Nikolaev and Binoy Ravindran - Contention Resolution for Coded Radio Networks
by Michael Bender, Seth Gilbert, Fabian Kuhn, John Kuszmaul, and Muriel Medard - Non-Clairvoyant Scheduling with Predictions Revisited
by Alexander Lindermayr and Nicole Megow - Sparse matrix multiplication in the low-bandwidth model
by Chetan Gupta, Juho Hirvonen, Janne H. Korhonen, Jan Studený, and Jukka Suomela - Adaptive Massively Parallel Algorithms for Cut Problems
by MohammadTaghi Hajiaghayi, Marina Knittel, Jan Olkowski, and Hamed Saleh - Online Parallel Paging with Optimal Makespan
by Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato - Performance Analysis and Modelling of Concurrent Multi-access Data Structures
by Adones Rukundo, Aras Atalar, and Philippas Tsigas - Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too
by John Kuszmaul - Balancing Flow Time and Energy Consumption
by Sami Davies, Samir Khuller, Shirley Zhang, and Sami Davies - Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering
by Tom Tseng, Laxman Dhulipala, and Julian Shun - Scalable Fine-Grained Parallel Cycle Enumeration Algorithms
by Jovan Blanuša, Paolo Ienne, and Kubilay Atasu - The Energy Complexity of Las Vegas Leader Election
by Yi-Jun Chang and Shunhua Jiang - A Fully-Distributed Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables
by John Augustine, Soumyottam Chatterjee, and Gopal Pandurangan - Massively Parallel Algorithms for $b$-Matching
by Mohsen Ghaffari, Christoph Grunau, Slobodan Mitrović - Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
by Taisuke Izumi, Naoki Kitamura, Takamasa Naruse, and Gregory Schwartzmany - Balanced Allocations in Batches: Simplified and Generalized
by Dimitrios Los and Thomas Sauerwald - NUMA-Aware Recoverable Mutex Lock
by Ahmed Fahmy and Wojciech Golab
- Brief Announcement: Towards a More Robust Algorithm for Flow Time Scheduling with Predictions, by Tianming Zhao, Chunhao Li, Wei Li, and Albert Zomaya
- Brief Announcement: A Parallel $(\Delta,\Gamma)$-Stepping Algorithm for the Constrained Shortest Path Problem, by Tayebeh Bahreini, Nathan Fisher, and Daniel Grosu
- Brief Announcement: The (Limited) Power of Multiple Identies: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion, by Thorsten Götte and Christian Scheideler
- Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling Metrics, by Hadi Khodabandeh and David Eppstein
- Brief Announcement: Nested Active-Time Scheduling, by Nairen Cao, Jeremy T. Fineman, Shi Li, Julian Mestre, Katina Russell, and William Umboh
- Brief Announcement: On the I/O complexity for Hybrid Integer Multiplication Algorithms in the Sequential and Parallel Distributed Memory Model, by Lorenzo De Stefani
- Brief Announcement: Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds, by Hussam Al Daas, Grey Ballard, Laura Grigori, Suraj Kumar, and Kathryn Rouse
- Brief Announcement: Faster Stencil Computations using Gaussian Approximations, by Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Yimin Zhu
- Brief Announcement: Spatial Locality and Granularity Change in Caching, by Nathan Beckmann, Phillip B. Gibbons, and Charles McGuffey
- Brief Announcement: Fast(er) Construction of Round-optimal $n$-Block Broadcast Schedules, by Jesper Larsson Träff
- Brief Announcement: Tight Bounds for Repeated Balls-into-Bins, by Dimitrios Los and Thomas Sauerwald
- Brief Announcement: Composable dynamic secure emulation, by Pierre Civit and Maria Potop-Butucaru