January 2025
DIMACS/IAS postdoctoral associate Shashank Srivastava received both the Best Paper Award and the Best Student Paper Award at the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), held January 12–15, 2025, in New Orleans, Louisiana. The awards were for the paper “Improved List Size for Folded Reed–Solomon Codes.”
The folded Reed–Solomon codes considered in Srivastava’s paper are a type of error-correcting code, meaning that they are designed to recover messages after parts of those messages become corrupted. When corruption is severe, however, there can be ambiguity that prevents uniquely determining the original message. List decoding is a relaxed notion of decoding that outputs a list of candidate solutions, one of which is correct. By producing a small list of potential candidates instead of attempting a single solution, much higher error rates can be handled. Using novel techniques described as being clean and elegant, Srivastava's new work provides an exponential improvement in the list size for folded Reed–Solomon codes, making a significant move towards achieving the best possible list size.
SODA focuses on topics related to the design and analysis of efficient algorithms and data structures for discrete problems and is widely considered to be one of the top academic conferences for algorithms research. This year, it received a total of 655 manuscript submissions and accepted roughly 30 percent for presentation. SODA’s reviewing process is overseen by a program committee made up of experts in various areas of CS theory. Each year, the program committee is responsible for selecting the papers accepted for presentation and choosing those honored as best papers. This year’s program committee voted to recognize two articles with the Best Paper Award and two with the Best Student Paper Award. Srivastava's paper was one of the two in each category.
Shashank Srivastava is a 2024 graduate of Toyota Technological Institute of Chicago with a Ph.D. in computer science. He joined DIMACS in September 2024 as a joint postdoc between DIMACS and the Institute for Advanced Study, where he will spend the upcoming academic year. The results included in the paper were also presented as part of his dissertation.