Follow
Suprovat Ghoshal
Suprovat Ghoshal
Postdoc at Northwestern University and TTI Chicago
Verified email at northwestern.edu - Homepage
Title
Cited by
Cited by
Year
Parameterized intractability of even set and shortest vector problem from gap-eth
A Bhattacharyya, S Ghoshal, P Manurangsi
arXiv preprint arXiv:1803.09717, 2018
282018
Ranking from stochastic pairwise preferences: Recovering Condorcet winners and tournament solution sets at the top
A Rajkumar, S Ghoshal, LH Lim, S Agarwal
International Conference on Machine Learning, 665-673, 2015
282015
Parameterized Intractability of Even Set and Shortest<? brk?> Vector Problem
A Bhattacharyya, É Bonnet, L Egri, S Ghoshal, KC S, B Lin, P Manurangsi, ...
Journal of the ACM (JACM) 68 (3), 1-40, 2021
242021
Tight approximation bounds for maximum multi-coverage
S Barman, O Fawzi, S Ghoshal, E Gürpınar
International Conference on Integer Programming and Combinatorial …, 2020
122020
Tight approximation bounds for maximum multi-coverage
S Barman, O Fawzi, S Ghoshal, E Gürpınar
Mathematical Programming 192 (1), 443-476, 2022
112022
Hardness of learning noisy halfspaces using polynomial thresholds
A Bhattacharyya, S Ghoshal, R Saket
Conference On Learning Theory, 876-917, 2018
112018
Exploiting correlation to achieve faster learning rates in low-rank preference bandits
A Saha, S Ghoshal
International Conference on Artificial Intelligence and Statistics, 456-482, 2022
102022
Testing sparsity over known and unknown bases
S Barman, A Bhattacharyya, S Ghoshal
International Conference on Machine Learning, 491-500, 2018
92018
On the hardness of learning sparse parities
A Bhattacharyya, A Gadekar, S Ghoshal, R Saket
arXiv preprint arXiv:1511.08270, 2015
92015
Combinatorial lower bounds for 3-query ldcs
A Bhattacharyya, LS Chandran, S Ghoshal
arXiv preprint arXiv:1911.10698, 2019
72019
A characterization of approximability for biased csps
E Lee, S Ghoshal
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022
62022
Approximation algorithms and hardness for strong unique games
S Ghoshal, A Louis
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
62021
Approximation algorithms for partially colorable graphs
S Ghoshal, A Louis, R Raychaudhury
arXiv preprint arXiv:1908.11631, 2019
42019
Hardness of learning DNFs using halfspaces
S Ghoshal, R Saket
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021
32021
The dictionary testing problem
S Barman, A Bhattacharyya, S Ghoshal
arXiv preprint arXiv:1608.01275 650, 2016
32016
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits
S Ghoshal, A Saha
arXiv preprint arXiv:2202.11795, 2022
22022
A Characterization of Approximability for Biased CSPs
S Ghoshal, E Lee
arXiv preprint arXiv:2201.04617, 2022
22022
On lifting integrality gaps to SSEH hardness for globally constrained csps
S Ghoshal, E Lee
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 26-36, 2023
12023
Approximating csps with outliers
S Ghoshal, A Louis
arXiv preprint arXiv:2205.11328, 2022
12022
The biased homogeneous r-lin problem
S Ghoshal
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2022
12022
The system can't perform the operation now. Try again later.
Articles 1–20