8 Duke CS Papers Accepted to SODA 2024

Duke Computer Science's Theory Group members are honored to have eight (8) papers accepted at the January 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA) conference, with six (6) of the Duke CS papers co-written by our graduate students. The premier international conference on algorithms research, SODA will be held in Alexandria, VA, USA, January 7-10, 2024.

SODA is cosponsored by the Society for Industrial and Applied Mathematics (SIAM) Activity Group on Discrete Mathematics and the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory. One of the three premier conferences in theoretical computer science, this symposium focuses on research topics related to design and analysis of efficient algorithms and data structures for discrete problems.

The Duke CS papers are:

• Fair price discrimination by Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, Kangning Wang
• Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D by Pankaj Agarwal, Esther Ezra, Micha Sharir
• Beyond the Quadratic Time Barrier for Network Unreliability by Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi
• Poly-logarithmic Competitiveness for the $k$-Taxi Problem by Anupam Gupta, Amit Kumar, Debmalya Panigrahi
• Fast and Accurate Approximations of the Optimal Transport in Semi-Continuous and Discrete Settings by Pankaj Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Keegan Yao
• Fast Approximation Algorithms for Piercing Boxes by Points by Pankaj Agarwal, Sariel Har-Peled, Rahul Raychaudhury, Stavros Sintos
• Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment by Pankaj Agarwal, Dan Halperin, Micha Sharir, Alex Steiger
• Bin Packing under Random-Order: Breaking the Barrier of 3/2 by Anish Hebbar, Arindam Khan, K. V. N. Sreenivas

Duke CS paper coauthors: