370 Jay St., Brooklyn, NY • Office 1105 • Zoom Room • cmusco [at] nyu.edu • CV • GitHub • Google Scholar
I am an Assistant Professor of Computer Science and Engineering at New York University's Tandon School of Engineering. My students and I are part of the Algorithms and Foundations Group, as well as the VIDA Research Center. Our research is funded by the Dept. of Energy and the National Science Foundation, including by a 2021 NSF CAREER Award.
My work is on the computational foundations of machine learning and data science. I study efficient methods for understanding large datasets, combining ideas from theoretical computer science with tools from computational and applied mathematics.
I was previously a Research Instructor at Princeton. I completed my PhD in computer science at MIT, where I was fortunate to be advised by Jon Kelner. Before MIT I was an engineer at Redfin and I studied Applied Math and Computer Science at Yale.
We are running NYU's in-person CS Theory Seminar at Courant this semester. You can also sign up for the Tandon Algorithms and Foundations email list to receive announcements about upcoming talks.
Spring 2023, 2022: NYU CS-GY 6923, Machine Learning
Fall 2022, 2021, 2020, 2019: NYU CS-GY 6763, Algorithmic Machine Learning and Data Science
Spring 2020: NYU CS-UY 4563, Introduction to Machine Learning
Fall 2018: Princeton COS 521 , Advanced Algorithm Design
Other: I am a judge and problem writer for the SIAM/MathWorks M3 Challenge, a math modeling competition for high schoolers (which I participated in as a student). I am happy to chat with students, coaches, or others about inspiring the next generation of applied mathematicians.
Raphael A. Meyer, Ph.D., 2019 - present.
Apoorv Singh, Ph.D., 2020 - present.
R. Teal Witter (with Prof. Lisa Hellerstein), Ph.D., 2020 - present.
Aarshvi Gajjar (with Prof. Chinmay Hegde), Ph.D. 2021 - present.
Majid Daliri, Ph.D., 2022 - present.
Tyler Chen, Courant Instructor 2022 - present.
Noah Amsel (primary advisor is Prof. Joan Bruna), Ph.D., 2022 - present.
David Persson, Visiting Research Scholar, 2023 - present.
List of previous students and postdocs
If you are interested in working with me on research, I would encourage you to apply to NYU Tandon's PhD program in Computer Science. I will be taking new students in 2023 (December 2022 application). You should have a strong mathematical background, including in probability and linear algebra.
If you are currently an undergraduate or masters student at NYU, the best way to start a collaboration, or to obtain a TA position for one of my classes, is to first complete my fall graduate class, CS-GY 6763.
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation Preprint.
Near-Optimality Guarantees for Approximating Rational Matrix Functions by the Lanczos Method Preprint.
Dimensionality Reduction for General KDE Mode Finding International Conference on Machine Learning (ICML 2023).
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
Symposium on Principles of Database Systems (PODS 2023).
Low-memory Krylov subspace methods for optimal rational matrix function approximation SIAM Journal on Matrix Analysis and Applications (SIMAX 2023).
Active Learning for Single Neuron Models with Lipschitz Non-Linearities
International Conference on Artificial Intelligence and Statistics (AISTATS 2023).
Preliminary version at NeurIPS 2022 Workshop on The Symbiosis of Deep Learning and Differential Equations II (DLDE 2022).
Near-Linear Sample Complexity for Lp Polynomial Regression ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).
A Tight Analysis of Hutchinson's Diagonal Estimator SIAM Symposium on Simplicity in Algorithms (SOSA 2023).
Active Linear Regression for lp Norms and Beyond IEEE Symposium on Foundations of Computer Science (FOCS 2022).
How to Quantify Polarization in Models of Opinion Dynamics International Workshop on Mining and Learning with Graphs at KDD (MLG 2022).
Chemically-informed data-driven optimization (ChIDDO): Leveraging physical models and Bayesian learning to accelerate chemical research Reaction Chemistry & Engineering 2022.
Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data IEEE/Eurographics EuroVis 2022.
Sublinear Time Spectral Density Estimation ACM Symposium on Theory of Computing (STOC 2022). Slides: 50 Minutes.
A Sketch-based Index for Correlated Dataset Search International Conference on Data Engineering (ICDE 2022).
Fast Regression for Structured Inputs International Conference on Learning Representations (ICLR 2022).
Error bounds for Lanczos-based Matrix Function Approximation SIAM Journal on Matrix Analysis and Applications (SIMAX 2022).
Fast and Near-Optimal Diagonal Preconditioning Preprint.
Dynamic Trace Estimation Advances in Information Processing Systems (NeurIPS 2021).
Finding an Approximate Mode of a Kernel Density Estimate European Symposium on Algorithms (ESA 2021).
Correlation Sketches for Approximate Join-Correlation Queries ACM Special Interest Group on Management of Data Conference. (SIGMOD 2021).
Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand ACM Special Interest Group on Management of Data Conference. (SIGMOD 2021).
Graph Learning for Inverse Landscape Genetics AAAI Conference on Artificial Intelligence (AAAI 2021). Short version in NeurIPS 2020 AI for Earth Sciences workshop.
Simple Heuristics Yield Provable Algorithms for Masked Low Rank Approximation Innovations in Theoretical Computer Science (ITCS 2021).
Hutch++: Optimal Stochastic Trace Estimation SIAM Symposium on Simplicity in Algorithms (SOSA 2021). Slides: 50 Minutes. MATLAB Code.
The Statistical Cost of Robust Kernel Hyperparameter Turning Advances in Information Processing Systems (NeurIPS 2020).
Fourier Sparse Leverage Scores and Approximate Kernel Learning Advances in Information Processing Systems (NeurIPS 2020). Invited for spotlight presentation.
Near Optimal Linear Algebra in the Online and Sliding Window Models IEEE Symposium on Foundations of Computer Science (FOCS 2020).
Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2020).
Sample Efficient Toeplitz Covariance Estimation ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). Slides: 50 Minutes.
Fast and Space Efficient Spectral Sparsification in Dynamic Streams ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
Analyzing the Impact of Filter Bubbles on Social Network Polarization ACM International Web Search and Data Mining Conference (WSDM 2020). Preliminary version in KDD 2019 workshop.
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms ACM Symposium on Theory of Computing (STOC 2019). Slides: 60 Minutes. Video: 30 Minutes.
Inferring networks from random walk-based node similarities Advances in Information Processing Systems (NeurIPS 2018). MATLAB Code.
Eigenvector Computation and Community Detection in Asynchronous Gossip Models International Colloquium on Automata, Languages, and Programming (ICALP 2018).
Minimizing Polarization and Disagreement in Social Networks The Web Conference (WWW 2018). MATLAB Code, requires CVX library for convex optimization.
Stability of the Lanczos Method for Matrix Function Approximation ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). Slides: 60 Minutes. Sample code for the version of Lanczos analyzed: lanczos.m
Recursive Sampling for the Nyström Method Advances in Information Processing Systems (NeurIPS 2017). Poster. MATLAB Code, including accelerated version of the algorithm.
Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees International Conference on Machine Learning (ICML 2017). Slides: 60 Minutes. Video: 80 minutes
Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). Slides: 60 Minutes.
Determining Tournament Payout Structures for Daily Fantasy Sports SIAM Algorithm Engineering and Experiments (ALENEX 2017). Invited to special issue of ACM Journal of Experimental Algorithmics for ALENEX. Slides: 20 Minutes.
Principal Component Projection Without Principal Component Analysis International Conference on Machine Learning (ICML 2016). Slides: 15 Minutes. MATLAB Code for standard algorithm and faster Krylov method analyzed in our recent paper.
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition Advances in Information Processing Systems (NeurIPS 2015). Invited for full oral presentation. Slides: 20 Minutes. MATLAB Code.
Dimensionality Reduction for k-Means Clustering and Low-Rank Approximation
ACM Symposium on Theory of Computing (STOC 2015).
Slides: 60 Minutes.
We posted a note titled Projection-Cost-Preserving Sketches: Proof Strategies and Constructions which presents simplified proofs of the results in this paper and our 2017 work.
Principled Sampling for Anomaly Detection Network and Distributed System Security Symposium (NDSS 2015). Slides: 20 Minutes.
Uniform Sampling for Matrix Approximation Innovations in Theoretical Computer Science (ITCS 2015).
Single Pass Spectral Sparsification in Dynamic Streams IEEE Symposium on Foundations of Computer Science (FOCS 2014). Invited to special issue of SIAM Journal on Computing for FOCS, appeared 2017. Slides: 60 Minutes.
Prototype code for some of the algorithms I work on is available through my GitHub page. Let me know if you have any questions about these implementations.
Atsushi Shimizu, M.S., 2022 - 2023.
Danrong Li, M.S., 2022 - 2023 (next stop: Ph.D. student at Penn State).
Xinyu Luo, M.S., 2020 - 2022 (next stop: Ph.D. student at Purdue).
Aline Bessa, Postdoc, 2021 (next stop: KNIME).
Indu Ramesh, M.S., 2020 - 2021 (next stop: Ph.D. student at NYU).
Mengxi Wu, M.S., 2020 - 2021 (next stop: Ph.D. student at USC).
Prathamesh Dharangutte, M.S., 2019 - 2021 (next stop: Ph.D. student at Rutgers).