Publications — Nairen Cao

Publications

← Home · Google Scholar · DBLP

2026

Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices.

Qian Xie, Yueli He, Nairen Cao

ICML 2026 Workshop on Decision-Making from Offline Datasets to Online Adaptation: Black-Box Optimization to Reinforcement Learning (DEMO), Spotlight

Paper
Static to Dynamic Correlation Clustering.

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang

ICALP 2026

Paper
Bounding the Fragmentation of B-Trees Subject to Batched Insertions.

Michael A. Bender, Aaron Bernstein, Nairen Cao, Alexander Conway, Martín Farach-Colton, Hanna Komlós, Yarin Shechter, Nicole Wein

PODS 2026

Paper Slides

2025

Min-Max Correlation Clustering via Neighborhood Similarity.

Nairen Cao, Steven Roche, Hsin-Hao Su

ESA 2025

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

2024

Understanding the Cluster LP for Correlation Clustering.

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman , Lukas Vogl

STOC 2024

Paper
Self-supervised Representation Learning on Electronic Health Records with Graph Kernel Infomax.

Hao-Ren Yao, Nairen Cao, Katina Russell, Der-Chen Chang , Ophir Frieder , Jeremy T. Fineman

ACM Transactions on Computing for Healthcare (HEALTH) 2024

Paper
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds.

Nairen Cao, Shang-En Huang, Hsin-Hao Su

SODA 2024

Paper Slides
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

2023

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

Paper

2022

Nested Active-Time Scheduling.

Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, Seeun William Umboh

ISAAC 2022

Paper Slides
Parallel Shortest Paths with Negative Edge Weights.

Nairen Cao, Jeremy T. Fineman, Katina Russell

SPAA 2022, Outstanding Paper Award

Paper
Brief Announcement: Nested Active-Time Scheduling.

Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, Seeun William Umboh

SPAA 2022

Paper

2021

Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm.

Nairen Cao, Jeremy T. Fineman, Katina Russell

PODC 2021

Paper Slides

2020

Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths.

Nairen Cao, Jeremy T. Fineman, Katina Russell

STOC 2020

Paper
Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths.

Nairen Cao, Jeremy T. Fineman, Katina Russell

SPAA 2020

Paper
Toward RSA-OAEP without Random Oracles.

Nairen Cao, Adam O'Neill and Mohammad Zaheri

Public Key Cryptography (PKC) 2020

Paper

2019

I/O-Efficient algorithms for topological sort and related problems.

Nairen Cao, Jeremy T. Fineman, Katina Russell, Eugene Yang

SODA 2019

Paper

2016

LRCRYPT: Leakage-Resilient Cryptographic System (Design and Implementation).

Xiaoqi Yu, Nairen Cao, Gongxian Zeng, Ruoqing Zhang, Siu-Ming Yiu

WISA 2016

Paper

Dissertation

Single-source Shortest Paths for Digraphs. PhD thesis. July, 2022.
Advisor: Jeremy T. Fineman
Defense Committe: Der-Chen Chang, Jeremy T. Fineman, Ophir Frieder, Justin Thaler.