The Theoretical and Experimental Algorithmics Lab (TEALab) led by Professor Rezaul Chowdhury of Stony Brook’s Computer Science Department (and IACS Core Faculty) has received two "Outstanding Paper" awards in this year's ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21). SPAA is a top conference on theoretical aspects of parallel computing.

The authors of the two papers are current PhD students Aaron Gregory, Zafar Ahmad, and Yimin Zhu; former PhD students Rathish Das and Mohammad Mahdi Javanmard; and Professors Pramod Ganapathi and Rezaul Chowdhury. Rathish Das is currently a Postdoc at the University of Waterloo and Mohammad Mahdi Javanmard is a Research Scientist at Facebook.

The two papers receiving the awards are:

(1) "Fast Stencil Computations using Fast Fourier Transforms" (Ahmad, Chowdhury, Das, Ganapathi, Gregory, Zhu) [TALK VIDEO], and

(2) "Low-Span Parallel Algorithms for the Binary-Forking Model" (Ahmad, Chowdhury, Das, Ganapathi, Gregory, Javanmard) [TALK VIDEO].

The first paper is on stencil computations, where a stencil is a function used to update the value of a cell in a multidimensional spatial grid using values of nearby cells from prior timesteps, and a stencil computation applies a given stencil to the grid cells for many timesteps. Stencil computations have applications in diverse areas of applied sciences, engineering and finance.  The authors propose new methods to improve the speed of such computations by orders of magnitude. 

The second paper presents highly parallel algorithms for three fundamental problems in computer science: comparison-based sorting, matrix multiplication, and computation of Discrete Fourier Transforms (DFT). All algorithms are for the binary-forking model which, in contrast to the widely studied theoretical PRAM model, takes into account the time required to spawn and synchronize threads, and thus realistically captures the performance of parallel algorithms implemented using modern multithreaded programming languages on multicore machines.

Congratulations to the TEALab team on this well deserved recognition in SPAA'21 for their critical research.