Christopher Musco
Institute Associate Professor
Studies algorithmic foundations of machine learning and data science, including randomized numerical linear algebra, sketching and active learning.
Christopher Musco's lab at NYU works on data management & big data. 41 papers since 2023, 28 at top venues, mostly SODA and NeurIPS. 3 PhD students. 17 alumni, most often to Uber. Applications close .
At a glance
- papers, 2023–2026
- 11/ year
- at T1 venues
- 68%
- PhD students
- 3
- MS students
- 0
- alumni listed
- 17
Papers by yearfrom the lab homepage, 2023–2026
- 12 papers2026 · T1 6 · collecting
- 10 papers2025 · T1 8
- 10 papers2024 · T1 9
- 9 papers2023 · T1 5
T1 venuesOtherVenues: SODA, NeurIPS, COLT, ICLR, AAAI
Research focuspaper titles that use each topic's words
- randomized2 papers
- Data management & big data0 papers
- numerical linear0 papers
- linear algebra0 papers
- studies algorithmic0 papers
Paper list
From the lab homepage.
202612 papers
- VecDBAlmost Navigable Graphs (opens in a new tab)
- SOSAAn Exact Algorithm for the Unanimous Vote Problem (opens in a new tab)
- SODA (T1)Does Block Size Matter in Randomized Block Krylov Low-rank Approximation? (opens in a new tab)
- SODA (T1)Efficiently Constructing Sparse Navigable Graphs (opens in a new tab)
- SIMAXFixed-Sparsity Matrix Approximation from Matrix-Vector Products (opens in a new tab)
- TMLR (T1)Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values (opens in a new tab)
- ESANearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products (opens in a new tab)
- ICLR (T1)PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression (opens in a new tab)
- SIMAXQuasi-Optimal Hierarchically Semi-Separable Matrix Approximation (opens in a new tab)
- COLT (T1)Query Efficient Structured Matrix Learning (opens in a new tab)
- LAARandomized Block-Krylov Subspace Methods for Low-rank Approximation of Matrix Functions (opens in a new tab)
- ICLR (T1)The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm (opens in a new tab)
202510 papers
- SIMAXAlgorithm-agnostic Low-rank Approximation of Operator Monotone Matrix Functions (opens in a new tab)
- ISITCoupling without Communication and Drafter-Invariant Speculative Decoding (opens in a new tab)
- NeurIPS (T1)Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (opens in a new tab)
- SODA (T1)Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning (opens in a new tab)
- SODA (T1)Improved Spectral Density Estimation via Explicit and Implicit Deflation (opens in a new tab)
- ICLR (T1)Matrix Product Sketching via Coordinated Sampling (opens in a new tab)
- SODA (T1)Near-Optimal Hierarchical Matrix Approximation from Matrix-Vector Products (opens in a new tab)
- ICLR (T1)Provably Accurate Shapley Value Estimation via Leverage Score Sampling (opens in a new tab)
- NeurIPS (T1)Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (opens in a new tab)
- COLT (T1)Sharper Bounds for Chebyshev Moment Matching, with Applications (opens in a new tab)
202410 papers
- AAAI (T1)A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy (opens in a new tab)
- COLT (T1)Agnostic Active Learning of Single Index Models with Linear Sample Complexity (opens in a new tab)
- NeurIPS (T1)Benchmarking Estimators for Natural Experiments: A Novel Dataset and a Doubly Robust Algorithm (opens in a new tab)
- COLT (T1)Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (opens in a new tab)
- ICLR (T1)Improved Active Learning via Dependent Leverage Score Sampling (opens in a new tab)
- NeurIPS (T1)Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (opens in a new tab)
- NeurIPS (T1)Near-Optimal Approximation of Matrix Functions by the Lanczos Method (opens in a new tab)
- SODA (T1)On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation (opens in a new tab)
- VLDB (T1)Sampling Methods for Inner Product Sketching (opens in a new tab)
- SOSASimple Analysis of Priority Sampling (opens in a new tab)
20239 papers
- SOSAA Tight Analysis of Hutchinson's Diagonal Estimator (opens in a new tab)
- AISTATS (T1)Active Learning for Single Neuron Models with Lipschitz Non-Linearities (opens in a new tab)
- ICML (T1)Dimensionality Reduction for General KDE Mode Finding (opens in a new tab)
- ESAEfficient Block Approximate Matrix Multiplication (opens in a new tab)
- SIMAXLow-memory Krylov subspace methods for optimal rational matrix function approximation (opens in a new tab)
- COLT (T1)Moments, Random Walks, and Limits for Spectrum Approximation (opens in a new tab)
- SODA (T1)Near-Linear Sample Complexity for Lp Polynomial Regression (opens in a new tab)
- NeurIPS (T1)Structured Semidefinite Programming for Recovering Structured Preconditioners (opens in a new tab)
- PODSWeighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation (opens in a new tab)
Where alumni went17 listed, 13% to industry
Industry 2Academia 13
Most often to
- Uber
Also to
- NYU
- Claremont McKenna College
- Max Planck Institute
Apply to NYUFall 2027
Computer Science PhD (Courant / Tandon)
- Round
- Single round (December)
- Opens
- —
- GRE
- See program page
- English
- See program page
- Fee
- See program page
Not yet confirmed for this intake.
Similar labsnearest by research summary
- USUMD
Heng Huang
- Learning theory & optimization
- DETUM
Reinhard Heckel
- Signal processing & information theory
- USCMU
Zachary C. Lipton
- Trustworthy & safe ML
- USGeorgia Tech
Kai Wang
- Reasoning & neuro-symbolic AI
- CNSJTU
Ruidan Su
0 T1 - USNYU
Julia Kempe
- Trustworthy & safe ML
Your notes
Save this lab to keep notes.
Data
Checked against the lab homepage.
- Collected
- Verified
- Papers
- The lab homepage
- Members
- Lab homepage
- Alumni
- Lab homepage
Tiers are venue classifications, not lab rankings.
NYUcloses