Apoorv Vikram Singh
Ph.D. Candidate
Computer Science
I am a fifth year Ph.D. candidate at the department of Computer Science at the NYU Tandon School of Engineering. I am a part of the Algorithms and Foundations Group, where I am being advised by Dr Chris Musco.
Before joining NYU, I was a visiting researcher at the MODAL team in INRIA Lille where I worked with Dr Hemant Tyagi and Dr Mihai Cucuringu (Univ of Oxford). Before that I was a Project Associate in the Dept. of Computer Science and Automation, Indian Institute of Science, where I worked with Dr Anand Louis and Dr Amit Deshpande (Microsoft Research, India). I obtained my undergraduate degree from IIIT Bangalore.
Research Interests: My research interests lie at the intersection of theoretical computer science and statistical machine learning, with a focus on theoretical foundations of big data. Currently, I am working on sublinear time graph problems and clustering problems. I am also interested in probabilistic combinatorics, Sum of Squares Hierarchy, and Discrepancy Theory (see Reading Group).
Publications
- Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond
Cameron Musco, Christopher Musco, Lucas Rosenblatt, Apoorv Vikram Singh
Abstract accepted at TPDP 2024 [ArXiv] [Slides] - Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
COLT 2024 [ArXiv] [Slides] - Moments, Random Walks, and Limits for Spectrum Approximation
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
COLT 2023 [ArXiv] [Slides] - Regularized Spectral Methods for Clustering Signed Networks
Mihai Cucuringu, Apoorv Vikram Singh, Déborah Sulem, Hemant Tyagi
JMLR 2021 [ArXiv] - Approximation Algorithms for Cost-Balanced Clustering
Amit Deshpande, Anand Louis, Deval Patel, Apoorv Vikram Singh
Preprint 2019 [Link] - On Euclidean $k$-Means Clustering with $\alpha$-Center Proximity
Amit Deshpande, Anand Louis, Apoorv Vikram Singh
AISTATS 2019 [ArXiv] [Slides]
News
- Gave a talk on moments, random walks, and limits for spectrum approximation at the Stanford CS Theory Lunch Seminar, and at Brown CS Theory Seminar (video).
- Gave a talk on our work on Chebyshev moment matching at the NYC Graduate Student TCS Day.
- Attended the Sublinear Graph Simplification Workshop at the Simons Institute.
- Attended STOC 2024 (Vancouver, Canada) and COLT 2024 (Edmonton, Canada).
- Attended the Sketching and Algorithm Design at the Simons Institute.
- Attended STOC 2023 (Orlando, Florida, USA) and COLT 2023 (Bangalore, Karnataka, India).
- June 11, 2023: Attended the Workshop on Modern Techniques in Graph Algorithms organized by DIMACS, Rutgers.
- June 26, 2022: Attended the Swedish Summer School on Theoretical Computer Science organized by KTH.
- Attended the summer school on New tools for optimal mixing of Markov chains: Spectral independence and entropy decay at UCSB.