Nairen Cao（曹乃仁）

Exciting News: NYC Student Theory Day Returns!

The NYC Student Theory Day will be held on May 2 at NYU Tandon. Join us for a day filled with exciting theory talks featuring acclaimed speakers from top institutions.

Registration Details:

• Attendance is free of charge.
• Please register by the indicated deadline to secure your spot.

For more details and to register, visit our main page.

We look forward to seeing you there!

Teaching

CS-GY 6033: Design and Analysis of Algorithms I ( Fall 2024 )

Selecated Sample Publications

Full List of Publications, Google Scholar Page, DBLP Page

Min-Max Correlation Clustering via Neighborhood Similarity. Nairen Cao, Steven Roche, Hsin-Hao Su arXiv [ Paper ] Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering. Nairen Cao, Shi Li, Jia Ye ICALP 2025 [ Paper ] Solving the Correlation Cluster LP in Sublinear Time. Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang STOC 2025 [ Paper ] Understanding the Cluster LP for Correlation Clustering. Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman , Lukas Vogl STOC 2024 [ Paper ] Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds. Nairen Cao, Shang-En Huang, Hsin-Hao Su SODA 2024 [ Paper ] Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. Vikrant Ashvinkumar , Aaron Bernstein , Nairen Cao, Christoph Grunau , Bernhard Haeupler , Yonggang Jiang , Danupon Nanongkai , Hsin-Hao Su ESA 2024 [ Paper ] Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence. Nairen Cao, Shang-En Huang, Hsin-Hao Su SPAA 2023, Outstanding Paper Award [ Paper ][ Slides ] Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth. Nairen Cao, Jeremy T. Fineman SODA 2023 Parallel Shortest Paths with Negative Edge Weights. Nairen Cao, Jeremy T. Fineman, Katina Russell SPAA 2022, Outstanding Paper Award [ Paper ] Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths. Nairen Cao, Jeremy T. Fineman, Katina Russell SPAA 2020 [ Paper ] Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths. Nairen Cao, Jeremy T. Fineman, Katina Russell STOC 2020 [ Paper ] I/O-Efficient algorithms for topological sort and related problems. Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang SODA 2019 [ Paper ]