I am an assistant professor at the Department of Computer Science at Indiana University.
Before this, I was a joint postdoc at Northwestern University and TTIC, and a postdoc at University of Michigan. I received my Ph.D. from the Indian Institute of Science, Bangalore, where I was advised by Arnab Bhattacharyya and Siddharth Barman.
Research Interests: I am primarily interested in the theory of approximation algorithms and hardness of approximation of discrete and continuous optimization problems. Broadly, I have been exploring the approximability of CSPs with global constraints and various related graph expansion problems. My interests also span topics in error correcting codes and computational learning theory.
Email: suprovat.ghoshal@gmail.com
See here for all publications.
Constraint Satisfaction Problems with Advice [arXiv]
Joint work with Konstantin Makarychev and Yury Makarychev.
SODA 2025
New Approximation Bounds for Small-Set Vertex Expansion [arXiv]
Joint work with Anand Louis.
SODA 2024
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs [arXiv].
Joint work with Euiwoong Lee.
FOCS 2023
A Characterization of Approximability for Biased CSPs [arXiv].
Joint work with Euiwoong Lee.
STOC 2022
Hardness of learning DNFs using Halfspaces [arXiv].
Joint work with Rishi Saket.
STOC 2021
Approximation Algorithms and Hardness for Strong Unique Games [arXiv].
Joint work with Anand Louis.
SODA 2021
Hardness of Learning Noisy Halfspaces using Polynomial Thresholds [Conference] [arXiv].
Joint work with Arnab Bhattacharyya and Rishi Saket.
COLT 2018