University of Massachusetts Amherst | Computer Science Building, Office 234 (Zoom Link) | cmusco at cs dot umass dot edu

I am an Assistant Professor in UMass Amherst's Manning College of Information and Computer Sciences, where I am part of the Theory Group.

I study algorithms, working at the intersection of theoretical computer science, numerical linear algebra, optimization, and machine learning. My group's research is supported in part by an NSF CAREER Award, an Adobe Research Grant, and a Google Research Scholar Award.

I completed my Ph.D. in the Theory of Computation Group at MIT, advised by Nancy Lynch. Before MIT, I studied Computer Science and Applied Math at Yale and worked as a software developer at Redfin.

Here are my Google Scholar profile, CV, and GitHub.

**COMPSCI 514**: Algorithms for Data Science, Fall 2022. (Past editions: F21, F20, S20, F19.)

**COMPSCI 690RA**: Randomized Algorithms, Spring 2022.

**COMPSCI 891M**: Theory Seminar.

Sudhanshu Chanpuriya, Ph.D.

Archan Ray, Ph.D.

Rajarshi Bhattacharjee, Ph.D.

Weronika Nguyen, Ph.D.

Kyle Doney, Ph.D.

Raghavendra Addanki, Ph.D. (2019-2022). Now Research Scientist at Adobe Research.

Adam Lechowicz, Undergraduate (2021-2022). Now Ph.D. student at UMass Amherst.

Aarshvi Gajjar, Masters (2020-2021). Now Ph.D. student at NYU.

Hannah Lawrence, Summer Intern (2019). Now Ph.D. student at MIT.

**Local Edge Dynamics and Opinion Polarization**

Nikita Bhalla, Adam Lechowicz, and Cameron Musco

ACM International Conference on Web Search and Data Mining (WSDM) 2023.

**Toeplitz Low-Rank Approximation with Sublinear Query Complexity**

Michael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco, and Kshiteej Sheth.

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023.

**Near-Linear Sample Complexity for L _{p} Polynomial Regression**

Raphael Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou.

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023.

**Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs**

Sudhanshu Chanpuriya, Ryan A. Rossi, Sungchul Kim, Tong Yu, Jane
Hoffswell, Nedim Lipka, Shunan Guo, and Cameron Musco

**Kernel Interpolation with Sparse Grids**

Mohit Yadav, Daniel Sheldon, and Cameron Musco

Conference on Neural Information Processing Systems (NeurIPS) 2022.

**Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings**

Dongxu Zhang, Michael Boratko, Cameron Musco, and Andrew McCallum

Conference on Neural Information Processing Systems (NeurIPS) 2022.

**Sample Constrained Treatment Effect Estimation**

Raghavendra Addanki, David Arbour, Tung Mai, Cameron Musco, and Anup Rao

Conference on Neural Information Processing Systems (NeurIPS) 2022.

**Simplified Graph Convolution with Heterophily**

Sudhanshu Chanpuriya and Cameron Musco.

Conference on Neural Information Processing Systems (NeurIPS) 2022.

Code repository.

**Active Linear Regression for ℓ _{p} Norms and Beyond**

Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda

IEEE Symposium on Foundations of Computer Science (FOCS) 2022

**Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries**

Raghavendra Addanki, Andrew McGregor, and Cameron Musco

European Symposium on Algorithms (ESA) 2022.

**Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation**

Tyler Chen, Anne Greenbaum, Cameron Musco, and Christopher Musco

**Fast Regression for Structured Inputs**

Raphael Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou.

International Conference on Learning Representations (ICLR) 2022.

**Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings**

Sudhanshu Chanpuriya, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Zhao Song, and Cameron Musco

**Sublinear Time Eigenvalue Approximation via Random Sampling**

Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, and Archan Ray

Slides from my talk at
the Algorithms and Foundations for Data Science Workshop, NUS.

**Sublinear Time Approximation of Text Similarity Matrices**

Archan Ray, Nicholas Monath, Andrew McCallum, and Cameron Musco

AAAI Conference on Artificial Intelligence (AAAI) 2022.

**Error Bounds for Lanczos-Based Matrix Function Approximation**

Tyler Chen, Anne Greenbaum, Cameron Musco, and Christopher Musco

SIAM Journal on Matrix Analysis and Applications (SIMAX) 2022.

**On the Power of Edge Independent Graph Models**

Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis

Conference on Neural Information Processing Systems (NeurIPS) 2021.

**Coresets for Classification - Simplified and Strengthened**

Tung Mai, Cameron Musco, and Anup B. Rao

Conference on Neural Information Processing Systems (NeurIPS) 2021.

**DeepWalking Backwards: From Embeddings Back to Graphs**

Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis

International Conference on Machine Learning (ICML) 2021.

Code repository.

**Faster Kernel Matrix Algebra via Density Estimation**

Arturs Backurs, Piotr Indyk, Cameron Musco, and Tal Wagner

International Conference on Machine Learning (ICML) 2021.

**Faster Kernel Interpolation for Gaussian Processes**

Mohit Yadav, Daniel Sheldon, and Cameron Musco

Artificial Intelligence and Statistics (AISTATS) 2021. **Oral Presentation.**

**Intervention Efficient Algorithms for Approximate Learning of Causal Graphs**

Raghavendra Addanki, Andrew McGregor, and Cameron Musco

Algorithmic Learning Theory (ALT) 2021.

Video of Raghav's talk at ALT.

**Subspace Embeddings Under Nonlinear Transformations**

Aarshvi Gajjar and Cameron Musco

Algorithmic Learning Theory (ALT) 2021.

Video of Aarshvi's talk at ALT.

**Estimation of Shortest Path Covariance Matrices**

Raj Kumar Maity and Cameron Musco

**Simple Heuristics Yield Provable Algorithms for Masked
Low-Rank Approximation**

Cameron Musco, Christopher Musco, and David P. Woodruff

Innovations in Theoretical Computer Science (ITCS) 2021.

Slides from my talks at ITA/UMass. Video of my talk at ITCS.

**Hutch++: Optimal Stochastic Trace Estimation
**

Raphael Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff

SIAM Symposium on Simplicity in Algorithms (SOSA) 2021.

Video of my E-NLA Seminar talk. Corresponding slides. Code repository.

**Fourier Sparse Leverage Scores and Approximate Kernel Learning
**

Tamás Erdélyi, Cameron Musco, and Christopher Musco

Conference on Neural Information Processing Systems (NeurIPS) 2020. **Spotlight Presentation.**

Code repository.

**Node Embeddings and Exact Low-Rank Representations of Complex Networks**

Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis

Conference on Neural Information Processing Systems (NeurIPS) 2020.

Code repository containing LPCA exact factorization code.

**Spiking Neural Networks Through the Lens of Streaming Algorithms**

Yael Hitron, Cameron Musco, and Merav Parter

International Symposium on Distributed Computing (DISC) 2020.

**Near Optimal Linear Algebra in the Online and Sliding Window Models**

Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou

IEEE Symposium on Foundations of Computer Science (FOCS) 2020.

**Efficient Intervention Design for Causal Discovery with Latents**

Raghavendra Addanki, Shiva Prasad Kasiviswanathan, Andrew McGregor, and Cameron Musco

International Conference on Machine Learning (ICML) 2020.

**InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity**

Sudhanshu Chanpuriya and Cameron Musco

Knowledge Discovery and Data Mining (KDD) 2020.

Code repository.

**Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers**

Hannah Lawrence, Jerry Li, Cameron Musco, and Christopher Musco

International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2020.

Video of Hannah's (remote) talk at ICASSP.

**Importance Sampling via Local Sensitivity**

Anant Raj, Cameron Musco, and Lester Mackey

International Conference on Artificial Intelligence and Statistics (AISTATS) 2020.

**Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks**

Yael Hitron, Nancy Lynch, Cameron Musco, and Merav Parter

Innovations in Theoretical Computer Science (ITCS) 2020.

**Sample Efficient Toeplitz Covariance Estimation**

Yonina Eldar, Jerry Li, Cameron Musco, and Christopher Musco

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

Slides from my talk at Cornell. Video from my talk at DIMACS.

**Fast and Space Efficient Spectral Sparsification in Dynamic Streams**

Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

Slides from my talk at Cornell.

**Toward a Characterization of Loss Functions for Distribution Learning**

Nika Haghtalab, Cameron Musco, and Bo Waggoner

Conference on Neural Information Processing Systems (NeurIPS) 2019.

**Learning to Prune: Speeding up Repeated Computations**

Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik

Conference on Learning Theory (COLT) 2019.

**A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms**

Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh

ACM Symposium on Theory of Computing (STOC) 2019.

Slides and video from Chris's talk at Simons.

**Learning Networks from Random Walk-Based Node Similarities**

Jeremy G. Hoskins, Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis

Conference on Neural Information Processing Systems (NeurIPS) 2018.

Code repository.

**Minimizing Polarization and Disagreement in Social Networks**

Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis

The Web Conference (WWW) 2018.

Code repository.

**Eigenvector Computation and Community Detection in Asynchronous Gossip Models**

Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco

International Colloquium on Automata, Languages, and Programming (ICALP) 2018.

**Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness**

Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff

Innovations in Theoretical Computer Science (ITCS) 2018.

Slides from my talk at ITCS.

**Stability of the Lanczos Method for Matrix Function Approximation**

Cameron Musco, Christopher Musco, and Aaron Sidford

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018.

Code repository for matrix function approximation (see `lanczos.m`

).

**Recursive Sampling for the Nyström Method**

Cameron Musco and Christopher Musco

Conference on Neural Information Processing Systems (NeurIPS) 2017.

Code repository. Slides and video from my talk at Simon's discussing this line of work.

**Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?**

Cameron Musco and David P. Woodruff

Conference on Neural Information Processing Systems (NeurIPS) 2017.

**Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices**

Cameron Musco and David P. Woodruff

IEEE Symposium on Foundations of Computer Science (FOCS) 2017.

Slides and video from my talk at FOCS. Extended slides slides for hour long talk.

**Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees**

Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker and Amir Zandieh

International Conference on Machine Learning (ICML) 2017.

Slides and video from my talk at ICML. Chris's extended slides for an hour long talk.

**Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling**

Michael B. Cohen, Cameron Musco, and Christopher Musco

ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.

Slides from my talk at SODA. Chris's extended slides from his talk at University of Utah.

**Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks**

Nancy Lynch, Cameron Musco, and Merav Parter

International Symposium on Distributed Computing (DISC) 2017.

**Spiking Neural Networks: An Algorithmic Perspective **

Nancy Lynch, Cameron Musco, and Merav Parter

Presentation at Workshop on Biological Distributed Algorithms (BDA) 2017.

Slides from my talk at BDA.

**New Perspectives on Algorithmic Robustness Inspired by Ant Colony House-Hunting**

Tsvetomira Radeva, Cameron Musco, and Nancy Lynch

Presentation at Workshop on Biological Distributed Algorithms (BDA) 2017.

**Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks**

Nancy Lynch, Cameron Musco, and Merav Parter

Innovations in Theoretical Computer Science (ITCS) 2017.

** Ant-Inspired Density Estimation via Random Walks**

Cameron Musco, Hsin-Hao Su, and Nancy Lynch

Proceedings of the National Academy of Sciences (PNAS) 2017.

Full paper also available on arXiv. An extended abstract initially appeared in PODC 2016.

**Online Row Sampling**

Michael B. Cohen, Cameron Musco, and Jakub Pachocki

International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2016.

**Appeared in special issue of Theory of Computing.**

**Principal Component Projection Without Principal Component Analysis**

Roy Frostig, Cameron Musco, Christopher Musco, and Aaron Sidford

International Conference on Machine Learning (ICML) 2016.

Code repository. Chris's slides from his talk at ICML.

**Faster Eigenvector Computation via Shift-and-Invert Preconditioning**

Daniel Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford

International Conference on Machine Learning (ICML) 2016.

**Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition**

Cameron Musco and Christopher Musco

Conference on Neural Information Processing Systems (NeurIPS) 2015. **Oral Presentation**.

Slides and video from my talk at NeurIPS. Code repository.

** Dimensionality Reduction for k-Means Clustering and Low Rank Approximation**

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu

ACM Symposium on Theory of Computing (STOC) 2015.

Slides from my talk at MIT's Algorithms and Complexity Seminar.

My Master's Thesis containing empirical evaluation along with a guide to implementation. A note containing simplified proofs for common projection-cost-preserving sketches.

**Uniform Sampling for Matrix Approximation**

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford

Innovations in Theoretical Computer Science (ITCS) 2015.

Slides from my talk at MIT's Algorithms and Complexity Seminar.

** Distributed House-Hunting in Ant Colonies**

Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch

ACM Symposium on Principles of Distributed Computing (PODC) 2015.

**Single Pass Spectral Sparsification in Dynamic Streams**

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco and Aaron Sidford

IEEE Symposium on Foundations of Computer Science (FOCS) 2014.

**Appeared in special issue of SIAM Journal on Computing (SICOMP).**

Chris's Slides from his talks at FOCS and the Harvard TOC Seminar.

Here are a few writeups, notes, and talks.

Projection-cost-preserving sketch note, containing simplified proofs for common projection-cost-preserving sketching techniques, following the work in our STOC 2015 and SODA 2017 papers.

VC dimension in (neural) circuit complexity, outline of a talk on the basics of VC dimension and how it can be used to give circuit size lower bounds for certain functions.

Fast Low-Rank Approximation and PCA Beyond Sketching, slides for a talk I gave at Mining Massive Datasets (MMDS 2016) on new techniques for large scale low-rank approximation. Corresponding video.

Chebyshev Polynomials in TCS and Algorithm Design, outline of a talk I gave at the MIT Theory student retreat on the many applications of Chebyshev polynomials to upper and lower bounds in Theoretical Computer Science.

Applications of Linear Sketching to Distributed Computing, slides for a talk I gave at our Theory of Distributed Systems seminar. High level overview of linear sketching, my work on k-means clustering and spectral sparsification, and applications to distributed data analysis.

Linear Regression and Pseudoinverse Cheatsheet, since there are a lot of ways to explain the pseudoinverse.

Big-O and Asymptotic Notation Cheatsheet, just in case.

I've worked on a lot of projects, some more serious than others.

I built this Rap Collaboration Graph, which gives a visualization of musical collaborations in hip hop. Unfortunately, colors are only rendering in Safari right now, it looks fuzzy on retina displays, and the data is about a year (7 years...) out of date. But I promise I'll get to it.

I had a lot of fun helping build the first version of One Button Wenzel, a site that sold buffalo chicken sandwiches. It evolved into Crunchbutton, then devolved back into One Button Wenzel. Here is a screenshot of the original site in all its glory.

In college I also had a lot of fun working on Yale's Formula Hydrid Racecar Team.

I love to ski, and a long time ago, my brother Chris and I used to build custom skis. Our first pair had maple/poplar cores, varnished wood sidewalls, and flex comparable to a pair of 2x4s. Our second pair has more precisely shaped pine cores, an improved top sheet, and a much smoother flex. The tips delaminated once, but we riveted them together and still ski on them today! Here's an old forum post on SkiBuilders.com with more pictures of our setup.