Papers Accepted to SPAA 2026

In each category below, the papers appear in increasing order of their submission IDs (which are not shown here).

Clicking on an author’s name will often, though not always, lead to a page containing information about the author, usually the author’s homepage if one exists.

Regular (Full) Papers

  1. A Practical Parallel Algorithm for Expander Decompositions
  2. Efficient Parallel (Δ+1)-Edge-Coloring
  3. Parallel Metric Skiplists and Nearest Neighbor Search
    • Xiangyun Ding (University of California, Riverside)
    • Rohin Garg (Massachusetts Institute of Technology)
    • Yan Gu (University of California, Riverside)
    • Yihan Sun (University of California, Riverside)

  4. Faster EPTAS for Scheduling on Uniform Machines
  5. Lossless Robustification of Packet Scheduling Algorithms
  6. Reducing Off-Chip Prefetch Request Latency of LLC hardware prefetchers via Neural Prediction
  7. Cell-Probe Lower Bounds for Data Structures in CRCW PRAM
  8. Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs
  9. Near-Optimal Parallel Approximate Counting via Sampling
  10. Non-Uniform Content-Oblivious Leader Election on Oriented Asynchronous Rings
  11. Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
  12. Tight Latency Guarantees for Weighted Caching with Delayed Hits
  13. PaHiS: A Hierarchical Synchronous Parallel Model for Irregular Workloads
  14. uSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts
  15. Near-Optimal Bounds for Adversarial Wake-up in Distributed Networks
  16. Non-Clairvoyant Scheduling for Processing-in-Memory
  17. Parallel Spectral Graph Sparsification via Low Diameter Decompositions
  18. Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity
  19. Deterministic Distance Approximation in MPC via Improved Hitting Sets
  20. Design Tradeoffs in Backend Organization in Out-Of-Order RISC-V Processors.
  21. The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically
  22. Towards Reliable Broadcast with Optimal Communication and Round Complexity
  23. Fast Concurrent Primitives Despite Contention
  24. Universal Deterministic Symmetry Breaking Between Anonymous Agents in Networks
    • Bibhuti Das (Université du Québec en Outaouais, Canada)
    • Andrzej Pelc (Université du Québec en Outaouais, Canada)

  25. Scheduler Augmentation: A Lightweight, Customizable, Low-Cost Profiling Technique for Fork-Join Parallel Programs
  26. Exponential Energy Savings in Local Distributed Graph Algorithms
  27. Fast and Theoretically Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
  28. A Scalable Persistent Key-Value Store with Atomic Batches and Snapshots
  29. Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
  30. CleanANN: Efficient and Robust Full Dynamism in Graph-based Approximate Nearest Neighbor Search
  31. Big Atomics: Direct and Non-Blocking Algorithms
  32. Minimizing Total Flow Time in the Online Active-Time Scheduling model
  33. Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices
  34. Online Span Minimization of Flexible Uniform Jobs
  35. The Scheduling Complexity of Pipeline Parallelism
  36. Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
  37. Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
  38. Composable Core-Sets for Fair Diversity Maximization

Brief Announcements

  1. Brief Announcement: Direction-incentivized spectral partitioning for acyclic graphs
  2. Brief Announcement: Scheduling Problems with Constrained Rejections
  3. Brief Announcement: Asynchronous Dispersion with Optimal Time Complexity
  4. Brief Announcement: An improved lower bound for local failover routing on directed networks
  5. Brief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication
  6. Brief Announcement: QPID: A Scalable, Strict Concurrent Priority Queue
  7. Brief Announcement: An I/O-Efficient Parallel FFT for Heterogeneous Architectures via a Single Global Exchange
    • Shina Guo (College of Computer Science and Artificial Intelligence, Fudan University)
    • Weiguo Gao (School of Mathematics, School of Data Science, Fudan University)
    • Yuan Tang (Fudan University)

  8. Brief Announcement: Recyclable Optimistic-Traversal Data Structures
  9. Brief Announcement: Byzantine Generals with Stuttering Madness
    • Bo Pan (Sorbonne Université, CNRS, LIP6, Paris, France)
    • Maria Potop-Butucaru (Sorbonne Université, CNRS, Laboratoire d’Informatique de Paris 6, LIP6, Paris, France)

  10. Brief Announcement: PRESERVE: Prefetching Model Weights and KV-Cache in Distributed LLM Serving
  11. Brief Announcement: Tiered-Memory Algorithms
  12. Brief Announcement: Energy-Time Trajectories: A Tool to Understand Complex Parallel Efficiency
  13. Brief Announcement: Discrete Incremental Voting – New Bounds for General Graphs and Expanders