-
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
with Nick Fischer and Ce Jin
In 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
-
More Asymmetry Yields Faster Matrix Multiplication
with Josh Alman, Ran Duan, Virginia Vassilevska Williams, Zixuan Xu and Renfei Zhou
In 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
-
All-Hops Shortest Paths
with Virginia Vassilevska Williams, Zoe Xi and Uri Zwick
In 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
-
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
with Barna Saha, Virginia Vassilevska Williams and Christopher Ye
In 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
-
New Separations and Reductions for Directed Hopsets and Preservers
with Gary Hoppenworth and Zixuan Xu
In 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
to appear
-
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
with Ce Jin
In 56th ACM Symposium on Theory of Computing (STOC 2024)
Invited to SICOMP special issue
Danny Lewin Best Student Paper Award
-
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
with Mina Dalirrooyfard, Surya Mathialagan and Virginia Vassilevska Williams
In 56th ACM Symposium on Theory of Computing (STOC 2024)
-
Simpler and Higher Lower Bounds for Shortcut Sets
with Virginia Vassilevska Williams and Zixuan Xu
In 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
-
New Bounds for Matrix Multiplication: from Alpha to Omega
with Virginia Vassilevska Williams, Zixuan Xu and Renfei Zhou
In 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
-
Simpler Reductions from Exact Triangle
with Timothy M. Chan
In 2024 SIAM Symposium on Simplicity in Algorithms (SOSA 2024)
-
Faster Algorithms for Text-to-Pattern Hamming Distances
with Timothy M. Chan, Ce Jin and Virginia Vassilevska Williams
In 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023)
-
Optimal Bounds for Noisy Sorting
with Yuzhou Gu
In 55th ACM Symposium on Theory of Computing (STOC 2023)
-
Removing Additive Structure in 3SUM-Based Reductions
with Ce Jin
In 55th ACM Symposium on Theory of Computing (STOC 2023)
Invited to SICOMP special issue
-
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
with Timothy M. Chan, and Virginia Vassilevska Williams
In 55th ACM Symposium on Theory of Computing (STOC 2023)
-
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
with Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan and Jelani Nelson
In 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
-
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
with Virginia Vassilevska Williams, and Eyob Woldeghebriel
In 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
-
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
with Krzysztof Sornat, and Virginia Vassilevska Williams
In 31st International Joint Conference on Artificial Intelligence (IJCAI 2022)
-
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
with Surya Mathialagan, and Virginia Vassilevska Williams
In 49th International Colloquium on Automata, Languages and Programming (ICALP 2022)
-
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
with Timothy M. Chan, and Virginia Vassilevska Williams
In 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
-
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
with Ce Jin
In 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
-
Fine-Grained Complexity and Algorithms for the Schulze Voting Method
with Krzysztof Sornat, and Virginia Vassilevska Williams
In 22nd ACM Conference on Economics and Computation (EC 2021)
-
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
with Timothy M. Chan, and Virginia Vassilevska Williams
In 48th International Colloquium on Automata, Languages and Programming (ICALP 2021)
-
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
with Yuzhou Gu, Adam Polak, and Virginia Vassilevska Williams
In 48th International Colloquium on Automata, Languages and Programming (ICALP 2021)
-
Monochromatic Triangles, Triangle Listing and APSP
with Virginia Vassilevska Williams
In 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020)
-
Faster Dynamic Range Mode
with Bryce Sandlund
In 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
-
Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
with Virginia Vassilevska Williams
In 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
-
Approximation Algorithms for Min-Distance Problems
with Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, and Yuancheng Yu
In 46th International Colloquium on Automata, Languages and Programming (ICALP 2019)
-
Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures
with Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, and Yuancheng Yu
In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
-
Parameterizing the Hardness of Binary Search Tree Access Sequences by Inversion Counts
with Meng He and Richard Peng
In 16th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2018)