Prathamesh Dharangutte

I am a fifth-year PhD candidate in Computer Science at Rutgers University. I am fortunate to be advised by Prof. Jie Gao and be a part of the Theory group.

My research interests lie (very) broadly in Theoretical Computer Science, Machine Learning, and Trustworthy AI.

Before joining Rutgers, I completed my Master’s in CS at NYU Tandon School of Engineering, during which I was lucky to have the opportunity of working with Prof. Christopher Musco. I obtained my Bachelor’s in Computer Engineering from PICT, Pune.

Apart from research, I enjoy video games and traveling. I also have a newfound fondness for hiking.

Publications

Author names appear in alphabetical order. Exceptions are marked with *.

Preprint

• The Price of Privacy For Approximating Max-CSP
  Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi, Akbar Rafiey, Phanu Vajanopath, Zongrui Zou.
  Preprint.
  

Conference Papers

• Packing Compact Subgraphs with Applications to Districting
  Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang and Fang-Yi Yu.
  Foundations of Responsible Computing (FORC 2026).
  

• Relative Error Fair Clustering in the Weak-Strong Oracle Model
  Vladimir Braverman, Prathamesh Dharangutte, Shaofeng Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang and Samson Zhou.
  International Conference on Machine Learning (ICML 2025).
  

• Hardness and Approximation Algorithms for Balanced Districting Problems
  Prathamesh Dharangutte, Jie Gao, Shang-En Huang and Fang-Yi Yu.
  Foundations of Responsible Computing (FORC 2025).
  

• Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
  Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai, Vihan Shah and Chen Wang.
  Conference on Artificial Intelligence and Statistics (AISTATS 2025).
  

• Differentially Private Range Queries with Correlated Input Perturbation
  Prathamesh Dharangutte, Jie Gao, Ruobin Gong and Guanyang Wang.
  Conference on Artificial Intelligence and Statistics (AISTATS 2025).
  Short version in Theory and Practice of Differential Privacy (TPDP 2024).
  

• Learning-augmented Maximum Independent Set
  Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah and Chen Wang.
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024).
  

• Metric Clustering and MST with Strong and Weak Distance Oracles
  MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram and Chen Wang.
  Conference on Learning Theory (COLT 2024).
  

• Integer Subspace Differential Privacy
  Prathamesh Dharangutte, Jie Gao, Ruobin Gong and Fang-Yi Yu.
  AAAI Conference on Artificial Intelligence (AAAI 2023).
  

• A Tight Analysis of Hutchinson’s Diagonal Estimator
  Prathamesh Dharangutte, Christopher Musco.
  SIAM Symposium on Simplicity in Algorithms (SOSA 2023).
  

• Dynamic trace estimation
  Prathamesh Dharangutte, Christopher Musco.
  Conference on Neural Information Processing Systems (NeurIPS) 2021.
  

• Graph Learning for Inverse Landscape Genetics
  Prathamesh Dharangutte, Christopher Musco.
  AAAI Conference on Artificial Intelligence (AAAI 2021).
  Short version in AI for Earth Sciences Workshop (NeurIPS 2020).
  

Workshop Papers

• HeartInsightify: Interpreting Longitudinal Heart Rate Data for Health Insights through Conformal Clustering*
  Prathamesh Dharangutte, Zongxing Xie, Jie Gao, Elinor Schoenfeld, Yindong Hua, and Fan Ye.
  International Workshop on Biomedical and Health Informatics (BHI 2023).
  

• An Energy-Based View of Graph Neural Networks*
  John Y. Shin and Prathamesh Dharangutte.
  Energy-Based Models Workshop (EBM-ICLR 2021).
  

Teaching

TA: Rutgers CS205 Intro to Discrete Structures I (Spring 2023)
TA: Rutgers CS461 Machine Learning Principles (Fall 2022)
TA: Rutgers CS210 Data Management for Data Science (Spring 2022)
TA: Rutgers CS501 Mathematical Foundations of Data Science (Fall 2021)
TA: NYU CS-UY 4563 Introduction to Machine Learning (Spring 2020)