Awards of the ACM Symposium on Parallelism in Algorithms and Architectures

Starting from 2007, the SPAA conference has been awarding annual Best Paper Award. In addition, starting in 2016, the SPAA conference has started awarding Outstanding Paper Award or Best Paper Finalists. The paper selection is done by the program committee. Past awards are:

  • 2021
    • Best Paper:
      • Daniel Anderson and Guy Blelloch. Parallel Minimum Cuts in O(m log^2(n)) Work and Low Depth
    • Best Paper Finalists:
      • Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory and Yimin Zhu. Fast Stencil Computations using Fast Fourier Transforms
      • Susanne Albers and Jens Quedenfeld. Algorithms for Right-Sizing Heterogeneous Data Centers
      • Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem and Manish Purohit. Non-Clairvoyant Scheduling with Predictions
      • Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory and Mohammad Javanmard. Low-Depth Parallel Algorithms for the Binary-Forking Model
  • 2020
    • Best Paper:
      • Irvan Jahja and Haifeng Yu. Sublinear Algorithms in T-interval Dynamic Networks
    • Best Paper Finalists:
      • Guy Blelloch, Jeremy Fineman, Yan Gu and Yihan Sun. Optimal Parallel Algorithms in the Binary-Forking Model 
      • Lazar Milenkovic and Shay Solomon. A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence 
      • Lukas Gianinazzi and Torsten Hoefler. Parallel Planar Subgraph Isomorphism and Vertex Connectivity 
      • Udit Agarwal and Vijaya Ramachandran. Faster Deterministic All Pairs Shortest Paths in Congest Model
  • 2019
    • Best Paper:
      • Faith Ellen, Barun Gorain, Avery Miller and Andrej Pelc. Constant-Length Labeling Schemes for Deterministic Radio Broadcast 
  • 2018
    • Best Papers:
      • Barbara Geissmann and Lukas Gianinazzi. Parallel Minimum Cuts in Near-linear Work and Low Depth 
      • Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Theoretically Efficient Parallel Graph Algorithms Can be Fast and Scalable 
  • 2017
    • Best Papers:
      • Sepehr Assadi and Sanjeev Khanna. Randomized Composable Coresets for Matching and Vertex Cover 
      • Sudipto Guha, Yi Li and Qin Zhang. Distributed Partial Clustering 
  • 2016
    • Best Paper:
      • Tim Roughgarden, Sergei Vassilvitskii and Joshua Wang. On Lower Bounds for Modern Parallel Computation 
    • Outstanding Papers:
      • Mingmou Liu, Xiaoyin Pan and Yitong Yin. Randomized Approximate Nearest Neighbor Search with Limited Adaptivity 
      • Madhukar Korupolu and Rajmohan Rajaraman. Robust and Probabilistic Failure-Aware Placement 
      • Deli Zhang and Damian Dechev. Lock-free Transactions without Aborts for Linked Data Structures 
  • 2015
    • Best Paper:
      • Yossi Azar, Nikhil Devanur, Zhiyi Huang and Debmalya Panigrahi. Speed Scaling in the Non-clairvoyant Model 
  • 2014
    • Best Paper:
      • Justin Thaler, Michael Mitzenmacher, and Jiayang Jiang. Parallel Peeling Algorithms
  • 2013
    • Best Papers:
      • Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii and Andrea Vattani. Fast Greedy Algorithms in MapReduce and Streaming 
      • Martina Eikel and Christian Scheideler. IRIS: A Robust Information System Against Insider DoS-Attacks
  • 2012
    • Best Paper:
      • I-Ting Lee, Aamir Shafi, and Charles Leiserson. Memory-Mapping Support for Reducer Hyperobjects
  • 2011: 
    • Best Paper:
      • Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. Graph Expansion and Communication Costs of Fast Matrix Multiplication
  • 2010: 
    • Best Paper:
      • Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi and Tom Leighton. Basic Network Creation Games
  • 2009: 
    • Best Paper:
      • Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin. Reducers and Other Cilk++ Hyperobjects
  • 2008: 
    • Best Paper:
      • Zvika Guz, Idit Keidar, Avinoam Kolodny and Uri C. Weiser. Utilizing Shared Data in Chip Multiprocessors with the Nahalal Architecture
  • 2007: 
    • Best Papers:
      • Pierre Fraigniaud, Cyril Gavoille, Emmanuelle Lebhar, Zvi Lotker and Adrian Kosowski. Universal Augmentation Schemes for Network Navigability: Overcoming the √n-Barrier 
      • Fabian Kuhn, Thomas Locher and Roger Wattenhofer. Tight Bounds for Distributed Selection