Papers

2025

1. Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

   Ran Duan, Jiayi Mao, Xiao Mao, and 2 more authors

   In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

   Abs

   We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.

2. Work-Efficient Parallel Counting via Sampling

   Hongyang Liu, Yitong Yin, and Yiyao Zhang

   2025

2023

1. Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set

   Arindam Khan, Aditya Lonkar, Saladi Rahul, and 2 more authors

   In 39th International Symposium on Computational Geometry (SoCG 2023), 2023

2022

1. Algorithms with predictions

   Michael Mitzenmacher, and Sergei Vassilvitskii

   Communications of the ACM, 2022
2. Machine learning advised ski rental problem with a discount

   Arghya Bhattacharya, and Rathish Das

   In International Conference and Workshops on Algorithms and Computation, 2022
3. Learning-augmented algorithms for online steiner tree

   Chenyang Xu, and Benjamin Moseley

   In Proceedings of the AAAI Conference on Artificial Intelligence, 2022
4. Proportionally fair online allocation of public goods with predictions

   Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, and 3 more authors

   arXiv preprint arXiv:2209.15305, 2022
5. Graph searching with predictions

   Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, and 1 more author

   arXiv preprint arXiv:2212.14220, 2022

2021

1. AWLCO: All-Window Length Co-Occurrence

   Joshua Sobel, Noah Bertram, Chen Ding, and 2 more authors

   In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), 2021

2020

1. The primal-dual method for learning augmented algorithms

   Etienne Bamas, Andreas Maggiori, and Ola Svensson

   Advances in Neural Information Processing Systems, 2020

2019

1. Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set

   Nabil H. Mustafa

   In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019
2. (Learned) Frequency Estimation Algorithms under Zipfian Distribution

   Anders Aamand, Piotr Indyk, and Ali Vakilian

   arXiv preprint arXiv:1908.05198, 2019

2018

1. Improving online algorithms via ML predictions

   Ravi Kumar, Manish Purohit, and Zoya Svitkina

   In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018

2017

1. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

   Michael Elkin, and Ofer Neiman

   2017

2013

1. A universal randomized packet scheduling algorithm

   Łukasz Jeż

   Algorithmica, 2013