Rajarshi Bhattacharjee
I am a fifth year PhD student in the Manning College of Information and Computer Sciences at University of Massachusetts Amherst.
I'm a student in the Theoretical Computer Science group. I'm advised by Prof. Cameron Musco.
I have a masters' degree in Computer Science from Indian Statistical Institute and a bachelors degree in mechanical engineering from Jadavpur University, India.
You can check out my resume here.
Email : rbhattacharj AT umass.edu
Google Scholar, CV
Research Interests
I am broadly interested in randomized algorithms and machine learning. Specifically, I work on designing efficient (with sublinear time/space/regret) algorithms in the following domains:
- Randomized Algorithms for linear algebraic tasks like spectrum estimation.
- Online learning, specifically, online caching and resource allocation problems.
- Algorithmic fairness and differential privacy preserving algorithms.
Recently, some of the problems I've been working on include algorithms which estimate the spectrum of matrix with a small number of matrix vector multiplications and online algorithms for fair resource allocation. I'm also working on algorithms for fast tensor vector products with applications to fast and memory efficient computation of the attention layer of transformers using techniques from randomized linear algebra as a part of my internship at Adobe Research.
Some selected publications and preprints are given below.
Publications
- Improved Spectral Density Estimation via Explicit and Implicit Deflation.
Rajarshi Bhattacharjee, Rajesh Jayaram, Cameron Musco, Christopher Musco, Archan Ray.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025
[arXiv]
- Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra.
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff.
Innovations in Theoretical Computer Science ITCS 2024
[arXiv]
- No-regret Algorithms for Fair Resource Allocation.
Abhishek Sinha, Ativ Joshi, Rajarshi Bhattacharjee, Cameron Musco, Mohammad Hajiesmaili.
Conference on Neural Information Processing Systems NeuRIPS 2023
[arXiv]
- Sublinear Time Eigenvalue Approximation via Random Sampling
Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco and Archan Ray.
International Colloquium on Automata, Languages, and Programming ICALP 2023
Extended version in Algorithmica
[arXiv]
- Fundamental Limits on the Regret of Online Network-Caching
Rajarshi Bhattacharjee, Subhankar Banerjee and Abhishek Sinha
ACM SIGMETRICS 2020
Also published in Proceedings of the ACM on the Measurement and Analysis of Computing Systems (POMACS)
[PDF,
proceedings]
- Optimizing the Age-of-Information for Mobile Users in Adversarial and Stochastic Environments.
Rajarshi Bhattacharjee, Subhankar Banerjee and Abhishek Sinha
IEEE Transactions on Information Theory .
[arXiv]
- Fundamental limits of age-of-information in stationary and non-stationary environments.
Subhankar Banerjee, Rajarshi Bhattacharjee and Abhishek Sinha
2020 IEEE International Symposium on Information Theory ISIT 2020
[arXiv, proceedings]
- Competitive algorithms for minimizing the maximum age-of-information
Rajarshi Bhattacharjee and Abhishek Sinha
Workshop on MAthematical performance Modeling and Analysis (MAMA) at ACM SIGMETRICS 2020
[PDF, proceedings]]
- Online Algorithms for Multiclass Classification Using Partial Labels
Rajarshi Bhattacharjee and Naresh Manwani
Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining 2020 (PAKDD 2020)
[arXiv, proceedings]]