By David Woodruff
The 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA24) took place in Alexandria, Va., from January 7-10. The meeting—which is sponsored annually by the SIAM Activity Group on Discrete Mathematics and the ACM Special Interest Group on Algorithms and Computation Theory—was co-located with the SIAM Symposium on Algorithm Engineering and Experiments and the SIAM Symposium on Simplicity in Algorithms (SOSA24). The robust SODA24 program featured invited plenary talks from Shafi Goldwasser (University of California, Berkeley), Raghu Meka (University of California, Los Angeles), János Pach (Alfréd Rényi Institute of Mathematics), and Dana Randall (Georgia Institute of Technology). Goldwasser spoke about building trust through the use of cryptography in the machine learning pipeline, while Meka discussed his breakthrough work on arithmetic progressions and applications to Boolean matrix multiplication and number-on-forehead communication complexity. Pach delivered an engaging talk about the transformation of one configuration to another via a sequence of moves of a given type, with applications to areas such as motion planning. Finally, Randall used tools from randomized algorithms and statistical physics to track the distributed collective behavior of groups like particle systems, ant colonies, and robot swarms.
Along with the invited lectures and a myriad of contributed presentations, SODA24 also acknowledged the recipients of several prizes and featured corresponding talks by prizewinners. This year, two collaborations were honored with the Best Paper Award. Moses Charikar (Stanford University), Prasanna Ramakrishnan (Stanford), Kangning Wang (Stanford), and Hongxun Wu (Berkeley) received an accolade for their paper titled “Breaking the Metric Voting Distortion Barrier,” which introduced a new randomized voting rule that obtains the first distortion guarantee and breaks the longstanding 3-approximation for this problem. Ramakrishnan’s associated talk offered a nice background of previous voting rules and desirable criteria, and utilized randomization to yield a very clever combination of the two that resulted in an improved rule. The other Best Paper Award went to Monika Henzinger (Institute of Science and Technology Austria), Jason Li (Berkeley), Satish Rao (Berkeley), and Di Wang (Google) for their paper on “Deterministic Near-linear Time Minimum Cut in Weighted Graphs.” Li’s subsequent address was a real tour de force that proposed new structural theorems for existing sparse clusterings to preserve minimum cuts in weighted graphs with some error. Li also mentioned multiple application areas that could benefit from this technique, including distributed and dynamic algorithms.
The meeting spotlighted two Best Student Paper Awards as well. Louis Golowich (Berkeley) received one of the prizes for his paper on “New Explicit Constant-degree Lossless Expanders.” During his talk, Golowich provided a beautiful explicit construction that combined a spectral expander and constant size expander. The other Best Student Paper Award went to Shuyi Yan (University of Copenhagen) for his paper titled “Edge-weighted Online Stochastic Matching: Beating \(1-\frac{1}{e}\).” As Yan explained during his virtual lecture, the paper introduced the first online algorithm for edge-weighted stochastic matching; using a careful balancing that is dictated by a linear program during preprocessing, the algorithm overcame the \(1-\frac{1}{e}\) barrier.
In addition to the SODA24 awardees, another prizewinner was recognized as part of SOSA24. Greg Bodwin (University of Michigan) accepted a Best Paper Award for his paper on “An Alternate Proof of Near-optimal Light Spanners.” Bodwin spoke more about this work during a contributed presentation.
SODA24 featured a total of 190 contributed presentations that addressed a wide variety of topics, including—but certainly not limited to—algorithmic game theory, data structures, parameterized complexity, matrix problems, privacy and cryptography, codes and combinatorics, quantum applications, machine learning, and optimization. We would like to thank all of the speakers and their collaborators for the wonderful presentations, excellent results, and interesting discussions. SODA25 will take place next January in New Orleans, La. — we hope to see you there!
|
David Woodruff is a professor in the School of Computer Science at Carnegie Mellon University. He has a broad interest in algorithms and has worked on data stream upper and lower bounds, dimensionality reduction, machine learning, numerical linear algebra, and sparse recovery.
|