| Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph P Manurangsi Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 151 | 2017 |
| From gap-eth to fpt-inapproximability: Clique, dominating set, and more P Chalermsook, M Cygan, G Kortsarz, B Laekhanukit, P Manurangsi, ... 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 101 | 2017 |
| A birthday repetition theorem and complexity of approximating dense CSPs P Manurangsi, P Raghavendra arXiv preprint arXiv:1607.02986, 2016 | 86 | 2016 |
| On the parameterized complexity of approximating dominating set CS Karthik, B Laekhanukit, P Manurangsi arXiv preprint arXiv 1711, 2017 | 81 | 2017 |
| Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis P Manurangsi 44th International Colloquium on Automata, Languages, and Programming (ICALP …, 2017 | 66* | 2017 |
| The price of fairness for indivisible goods X Bei, X Lu, P Manurangsi, W Suksompong Theory of Computing Systems 65, 1069-1093, 2021 | 47 | 2021 |
| Deep learning with label differential privacy B Ghazi, N Golowich, R Kumar, P Manurangsi, C Zhang Advances in neural information processing systems 34, 27131-27145, 2021 | 45 | 2021 |
| Large-scale differentially private BERT R Anil, B Ghazi, V Gupta, R Kumar, P Manurangsi arXiv preprint arXiv:2108.01624, 2021 | 45 | 2021 |
| Private aggregation from fewer anonymous messages B Ghazi, P Manurangsi, R Pagh, A Velingker Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference …, 2020 | 43 | 2020 |
| A survey on approximation in parameterized complexity: Hardness and algorithms AE Feldmann, E Lee, P Manurangsi Algorithms 13 (6), 146, 2020 | 41 | 2020 |
| Pure differentially private summation from anonymous messages B Ghazi, N Golowich, R Kumar, P Manurangsi, R Pagh, A Velingker arXiv preprint arXiv:2002.01919, 2020 | 41 | 2020 |
| Parameterized Intractability of Even Set and Shortest Vector Problem A Bhattacharyya, É Bonnet, L Egri, S Ghoshal, B Lin, P Manurangsi, ... Journal of the ACM (JACM) 68 (3), 1-40, 2021 | 39* | 2021 |
| Asymptotic existence of fair divisions for groups P Manurangsi, W Suksompong Mathematical Social Sciences 89, 100-108, 2017 | 38 | 2017 |
| The computational complexity of training relu (s) P Manurangsi, D Reichman arXiv preprint arXiv:1810.04207, 2018 | 36 | 2018 |
| Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead B Ghazi, R Kumar, P Manurangsi, R Pagh International Conference on Machine Learning, 3505-3514, 2020 | 31 | 2020 |
| On closest pair in euclidean metric: Monochromatic is as hard as bichromatic CS Karthik, P Manurangsi Combinatorica 40 (4), 539-573, 2020 | 29 | 2020 |
| A Note on Max -Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation P Manurangsi arXiv preprint arXiv:1810.03792, 2018 | 27 | 2018 |
| Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing … P Manurangsi Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 26 | 2020 |
| Differentially private clustering: Tight approximation ratios B Ghazi, R Kumar, P Manurangsi Advances in Neural Information Processing Systems 33, 4040-4054, 2020 | 25 | 2020 |
| Parameterized approximation algorithms for bidirected Steiner network problems R Chitnis, AE Feldmann, P Manurangsi ACM Transactions on Algorithms (TALG) 17 (2), 1-68, 2021 | 23 | 2021 |
Badih GhaziGoogleVerified email at google.com
