Suprovat Ghoshal
I am a joint postdoc at Northwestern University and TTIC, hosted by Konstantin and Yury Makarychev. Before this, I was a postdoc at U.Mich hosted by Euiwoong Lee. 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.
I am in the academic job market for positions starting Fall 2024.
Contact:
Email: suprovat.ghoshal@gmail.com
Selected Co-authored Articles:
See here for all publications.
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