Suprovat Ghoshal

According to our database, Suprovat Ghoshal authored at least 22 papers between 2015 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Constraint Satisfaction Problems with Advice.

Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

New Approximation Bounds for Small-Set Vertex Expansion.

Suprovat Ghoshal, Anand Louis

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

A PTAS for <i>ℓ</i>₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

A PTAS for 𝓁₀-Low Rank Approximation: Solving Dense CSPs over Reals.

Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang

CoRR, 2023

On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.

Suprovat Ghoshal, Euiwoong Lee

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

A characterization of approximability for biased CSPs.

Euiwoong Lee, Suprovat Ghoshal

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Approximating CSPs with Outliers.

Suprovat Ghoshal, Anand Louis

Proceedings of the Approximation, 2022

The Biased Homogeneous r-Lin Problem.

Suprovat Ghoshal

Proceedings of the Approximation, 2022

Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits.

Aadirupa Saha, Suprovat Ghoshal

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Hardness of learning DNFs using halfspaces.

Suprovat Ghoshal, Rishi Saket

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Approximation Algorithms and Hardness for Strong Unique Games.

Suprovat Ghoshal, Anand Louis

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Tight Approximation Bounds for Maximum Multi-coverage.

Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpinar

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Combinatorial Lower Bounds for 3-Query LDCs.

Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Average Bias and Polynomial Sources.

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

Electron. Colloquium Comput. Complex., 2019

Parameterized Intractability of Even Set and Shortest Vector Problem.

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

Electron. Colloquium Comput. Complex., 2019

Approximation Algorithms for Partially Colorable Graphs.

Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury

Proceedings of the Approximation, 2019

2018

Testing Sparsity over Known and Unknown Bases.

Siddharth Barman, Arnab Bhattacharyya, Suprovat Ghoshal

Proceedings of the 35th International Conference on Machine Learning, 2018

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Hardness of Learning Noisy Halfspaces using Polynomial Thresholds.

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

Proceedings of the Conference On Learning Theory, 2018

2016

The Dictionary Testing Problem.

Siddharth Barman, Arnab Bhattacharyya, Suprovat Ghoshal

CoRR, 2016

On the Hardness of Learning Sparse Parities.

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top.

Arun Rajkumar, Suprovat Ghoshal, Lek-Heng Lim, Shivani Agarwal

Proceedings of the 32nd International Conference on Machine Learning, 2015