Suprovat Ghoshal

43 papers A* 11A 5B 1Journal 25Unranked 1

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