Madhusudhan Reddy Pittu

madhusudhan.p@nyu.edu

New York, NY

I have been a Postdoctoral Associate at the Courant Institute of Mathematical Sciences, New York University, since September 2025, where I work with Anupam Gupta.

I received my Ph.D. in Computer Science from Carnegie Mellon University in the Algorithms, Combinatorics, and Optimization (ACO) program, advised by Anupam Gupta and, during my final year, David P. Woodruff. Prior to that, I earned my B.Tech. in Computer Science from the Indian Institute of Technology (IIT) Kharagpur.

My research interests lie broadly in Theoretical Computer Science, with a focus on Approximation Algorithms, Online Algorithms, Combinatorics, and Optimization. I am particularly interested in problems with a geometric flavor.

Selected distinctions

Bronze Medal representing India at the 57th International Mathematical Olympiad, 2016
Infosys Award for excellent performance in International Olympiads, 2016
IITKGP Foundation-USA International Internship Award, 2020
Best Solution Award at the IMO training camp, 2015
Erdős number: 2

selected publications

STOC

Combinatorial Optimization using Comparison Oracles

Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, and 7 more authors

In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

STOC 2026, pp. 1995-2006.

DOI arXiv Bib HTML

@inproceedings{pittu2026comparison,
  title = {Combinatorial Optimization using Comparison Oracles},
  author = {Cohen-Addad, Vincent and d'Orsi, Tommaso and Gupta, Anupam and Guruganesh, Guru and Lee, Euiwoong and Paes Leme, Renato and Panigrahi, Debmalya and Pittu, Madhusudhan Reddy and Schneider, Jon and Woodruff, David P.},
  booktitle = {Proceedings of the 58th Annual ACM Symposium on Theory of Computing},
  year = {2026},
  pages = {1995--2006},
  doi = {10.1145/3798129.3800904},
  note = {STOC 2026, pp. 1995-2006.},
}

ICALP

Guessing Efficiently for Constrained Subspace Approximation

Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, and 2 more authors

In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), 2025

LIPIcs 334, Article 29, pp. 29:1-29:20.

DOI arXiv Bib HTML

@inproceedings{pittu2025subspace,
  title = {Guessing Efficiently for Constrained Subspace Approximation},
  author = {Bhaskara, Aditya and Mahabadi, Sepideh and Pittu, Madhusudhan Reddy and Vakilian, Ali and Woodruff, David P.},
  booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  year = {2025},
  volume = {334},
  pages = {29:1--29:20},
  doi = {10.4230/LIPIcs.ICALP.2025.29},
  note = {LIPIcs 334, Article 29, pp. 29:1-29:20.},
}

SODA

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu, and 1 more author

In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024

SODA 2024, pp. 1307-1327. The full journal version appears separately above.

DOI arXiv Bib HTML

@inproceedings{pittu2024nsw,
  title = {Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs},
  author = {Brown, Adam and Laddha, Aditi and Pittu, Madhusudhan Reddy and Singh, Mohit},
  booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year = {2024},
  pages = {1307--1327},
  doi = {10.1137/1.9781611977912.52},
  note = {SODA 2024, pp. 1307-1327. The full journal version appears separately above.},
}

FOCS

The Price of Explainability for Clustering

Anupam Gupta, Madhusudhan Reddy Pittu, Ola Svensson, and 1 more author

In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023

FOCS 2023, pp. 1131-1148.

DOI arXiv Bib HTML

@inproceedings{pittu2023explainability,
  title = {The Price of Explainability for Clustering},
  author = {Gupta, Anupam and Pittu, Madhusudhan Reddy and Svensson, Ola and Yuan, Rachel},
  booktitle = {2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)},
  year = {2023},
  pages = {1131--1148},
  doi = {10.1109/FOCS57990.2023.00067},
  note = {FOCS 2023, pp. 1131-1148.},
}

FOCS

Determinant Maximization via Matroid Intersection Algorithms

Adam Brown, Aditi Laddha, Madhusudhan Pittu, and 2 more authors

In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022

FOCS 2022, pp. 255-266.

DOI arXiv Bib HTML

@inproceedings{pittu2022detmax,
  title = {Determinant Maximization via Matroid Intersection Algorithms},
  author = {Brown, Adam and Laddha, Aditi and Pittu, Madhusudhan and Singh, Mohit and Tetali, Prasad},
  booktitle = {2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)},
  year = {2022},
  pages = {255--266},
  doi = {10.1109/FOCS54457.2022.00031},
  note = {FOCS 2022, pp. 255-266.},
}

SODA

A 3-Approximation Algorithm for Maximum Independent Set of Rectangles

Waldo Gálvez, Arindam Khan, Mathieu Mari, and 3 more authors

In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022

SODA 2022, pp. 894-905. The arXiv link is pinned to version 2, which matches this title.

DOI arXiv Bib HTML

@inproceedings{pittu2022misr3,
  title = {A 3-Approximation Algorithm for Maximum Independent Set of Rectangles},
  author = {G\'{a}lvez, Waldo and Khan, Arindam and Mari, Mathieu and M\"{o}mke, Tobias and Pittu, Madhusudhan Reddy and Wiese, Andreas},
  booktitle = {Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  year = {2022},
  pages = {894--905},
  doi = {10.1137/1.9781611977073.38},
  note = {SODA 2022, pp. 894-905. The arXiv link is pinned to version 2, which matches this title.},
}