Prathamesh Dharangutte

I am a postdoc at the University of Copenhagen in the Foundations of Responsible Machine Learning group, working with Amartya Sanyal.

My research interests lie (very) broadly at the intersection of Theoretical Computer Science and Trustworthy AI. I am also interested in algorithmic aspects of modern machine learning.

Before joining UCPH, I was fortunate to be advised by Jie Gao during my PhD at Rutgers University and by Christopher Musco during my MS at New York University. Even before, I obtained my Bachelor’s from PICT, Pune.

Publications

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

Preprint

• Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time
  Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie and Samson Zhou.
  Preprint.
  

• Almost-tight Bounds for Learning-augmented Maximum Independent Set
  Vladimir Braverman, Prathamesh Dharangutte, Daniel Reichman and Chen Wang.
  Preprint.
  

• The Price of Privacy For Approximating Max-CSP
  Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi, Akbar Rafiey, Phanu Vajanopath and 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)