Publications
Authors of most papers are listed in alphabetical order, following the convention in mathematics and theoretical computer science. See also my Google Scholar profile.
Preprints
- Efficient Swap Multicalibration of Elicitable Properties [arXiv]
Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan
2025 - Making and Evaluating Calibrated Forecasts. [arXiv]
Yuxuan Lu*, Yifan Wu*, Jason Hartline, Lunjia Hu (* = equal contribution)
2025 - A Perfectly Truthful Calibration Measure. [arXiv]
Jason Hartline, Lunjia Hu, Yifan Wu
2025
Survey
- Calibration through the Lens of Indistinguishability. [arxiv]
Parikshit Gopalan, Lunjia Hu
ACM SIGecom Exchanges 23.1, July 2025
Conference Papers
- Inducing Efficient and Equitable Professional Networks through Link Recommendations. [arXiv]
Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, Juan Perdomo
FORC 2026 - How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension. [arXiv]
Cynthia Dwork, Lunjia Hu, Han Shao
NeurIPS 2025 - Generalized and Unified Equivalences between Hardness and Pseudoentropy. [arXiv]
Lunjia Hu, Salil Vadhan
TCC 2025
Outstanding Paper Award - Omnipredicting Single-Index Models with Multi-Index Models. [arXiv]
Lunjia Hu, Kevin Tian, Chutong Yang
STOC 2025 - Testing Calibration in Nearly-Linear Time. [arXiv]
Lunjia Hu, Arun Jambulapati, Kevin Tian, Chutong Yang
NeurIPS 2024 - Calibration Error for Decision Making. [arXiv]
Lunjia Hu, Yifan Wu
FOCS 2024 (published under the old title “Predict to Minimize Swap Regret for All Payoff-Bounded Tasks”) - On Computationally Efficient Multi-Class Calibration. [arXiv]
Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum
COLT 2024 - Multigroup Robustness. [arXiv]
Lunjia Hu, Charlotte Peale, Judy Hanwen Shen
ICML 2024 - Loss Minimization Yields Multicalibration for Large Neural Networks. [arXiv] [video]
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran
ITCS 2024 - When Does Optimizing a Proper Loss Yield Calibration? [arXiv]
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran
NeurIPS 2023 (Spotlight) - Simple, Scalable and Effective Clustering via One-Dimensional Projections. [arXiv]
Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
NeurIPS 2023 - Generative Models of Huge Objects. [arXiv]
Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold
CCC 2023 - Omnipredictors for Constrained Optimization. [arXiv] [talk at the Simons Institute]
Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, Chutong Yang
ICML 2023 - A Unifying Theory of Distance from Calibration. [arXiv] [video]
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran
STOC 2023 - Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. [arXiv] [video] [Charlotte’s talk at the Simons Institute]
Lunjia Hu, Charlotte Peale
ITCS 2023
Best Student Paper Award - Loss Minimization through the Lens of Outcome Indistinguishability. [arXiv] [video by Michael]
Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder
ITCS 2023 - Subspace Recovery from Heterogeneous Data with Non-isotropic Noise. [arXiv]
John Duchi, Vitaly Feldman, Lunjia Hu, Kunal Talwar
NeurIPS 2022 - Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability. [arXiv]
Lunjia Hu, Charlotte Peale, Omer Reingold
ALT 2022
E. M. Gold Best Student Paper Award - An Improved Local Search Algorithm for k-Median. [arXiv]
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic
SODA 2022 - Near-Optimal Explainable k-Means for All Dimensions. [arXiv] [talk at the IDEAL Workshop]
Moses Charikar, Lunjia Hu
SODA 2022 - Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers. [arXiv]
Lunjia Hu, Omer Reingold
AISTATS 2021 - Approximation Algorithms for Orthogonal Non-negative Matrix Factorization. [arXiv]
Moses Charikar, Lunjia Hu
AISTATS 2021 - The Power of Many Samples in Query Complexity. [conference version] [arXiv]
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan
ICALP 2020 - Towards Understanding Learning Representations: To What Extent Do Different Neural Networks Learn the Same Representation. [conference version] [arXiv] [spotlight talk]
Liwei Wang, Lunjia Hu, Jiayuan Gu, Zhiqiang Hu, Yue Wu, Kun He, John Hopcroft
NeurIPS 2018 (Spotlight) - Active Tolerant Testing. [conference version] [arXiv] [conference talk]
Avrim Blum, Lunjia Hu
COLT 2018 - Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes. [conference version] [arXiv]
Lunjia Hu, Ruihan Wu, Tianhong Li, Liwei Wang
COLT 2017 - Capacitated Center Problems with Two-Sided Bounds and Outliers. [conference version] [arXiv]
Hu Ding, Lunjia Hu, Lingxiao Huang, Jian Li
WADS 2017
Lunjia Hu 