Suprovat Ghoshal

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 39

Top Topics

Approximation Algorithms

Agnostic Learning

Low Rank Approximation

Constraint Satisfaction

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
Constraint Satisfaction Problems with Advice. CoRR (2024)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. SODA (2024)
Suprovat Ghoshal, Anand Louis
New Approximation Bounds for Small-Set Vertex Expansion. SODA (2024)
Suprovat Ghoshal, Euiwoong Lee
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. CoRR (2023)
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang
-Low Rank Approximation: Solving Dense CSPs over Reals. CoRR (2023)
Suprovat Ghoshal, Anand Louis
New Approximation Bounds for Small-Set Vertex Expansion. CoRR (2023)
Suprovat Ghoshal, Euiwoong Lee
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. FOCS (2023)
Suprovat Ghoshal, Aadirupa Saha
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits. CoRR (2022)
Suprovat Ghoshal, Anand Louis
Approximating CSPs with Outliers. APPROX/RANDOM (2022)
Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpinar
Tight approximation bounds for maximum multi-coverage. Math. Program. 192 (1) (2022)
Suprovat Ghoshal
The Biased Homogeneous r-Lin Problem. APPROX/RANDOM (2022)
Suprovat Ghoshal, Anand Louis
Approximating CSPs with Outliers. CoRR (2022)
Suprovat Ghoshal, Euiwoong Lee
A Characterization of Approximability for Biased CSPs. CoRR (2022)
Euiwoong Lee, Suprovat Ghoshal
A characterization of approximability for biased CSPs. STOC (2022)
Aadirupa Saha, Suprovat Ghoshal
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits. AISTATS (2022)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM 68 (3) (2021)
Suprovat Ghoshal, Anand Louis
Approximation Algorithms and Hardness for Strong Unique Games. SODA (2021)
Suprovat Ghoshal, Rishi Saket
Hardness of learning DNFs using halfspaces. STOC (2021)
Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal
Combinatorial Lower Bounds for 3-Query LDCs. ITCS (2020)
Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpinar
Tight Approximation Bounds for Maximum Multi-coverage. IPCO (2020)
Suprovat Ghoshal, Anand Louis
Approximation Algorithms and Hardness for Strong Unique Games. CoRR (2020)
Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpinar
Tight Approximation Bounds for Maximum Multi-Coverage. CoRR (2019)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Suprovat Ghoshal, Rishi Saket
Hardness of Learning DNFs using Halfspaces. Electron. Colloquium Comput. Complex. 26 (2019)
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Approximation Algorithms for Partially Colorable Graphs. APPROX-RANDOM (2019)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR (2019)
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka
Average Bias and Polynomial Sources. Electron. Colloquium Comput. Complex. 26 (2019)
Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal
Combinatorial lower bounds for 3-query LDCs. CoRR (2019)
Suprovat Ghoshal, Rishi Saket
Hardness of Learning DNFs using Halfspaces. CoRR (2019)
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Approximation Algorithms for Partially Colorable Graphs. CoRR (2019)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. ICALP (2018)
Siddharth Barman, Arnab Bhattacharyya, Suprovat Ghoshal
Testing Sparsity over Known and Unknown Bases. ICML (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. CoRR (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. Electron. Colloquium Comput. Complex. 25 (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of Learning Noisy Halfspaces using Polynomial Thresholds. COLT (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of learning noisy halfspaces using polynomial thresholds. CoRR (2017)
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
Hardness of learning noisy halfspaces using polynomial thresholds. Electron. Colloquium Comput. Complex. 24 (2017)
Siddharth Barman, Arnab Bhattacharyya, Suprovat Ghoshal
The Dictionary Testing Problem. CoRR (2016)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the Hardness of Learning Sparse Parities. ESA (2016)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the hardness of learning sparse parities. Electron. Colloquium Comput. Complex. 22 (2015)
Arun Rajkumar, Suprovat Ghoshal, Lek-Heng Lim, Shivani Agarwal
Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top. ICML (2015)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket
On the hardness of learning sparse parities. CoRR (2015)