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
173 2017 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
160 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
151 * 2020 Large-scale differentially private BERT R Anil, B Ghazi, V Gupta, R Kumar, P Manurangsi
arXiv preprint arXiv:2108.01624, 2021
138 2021 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
135 * 2017 A birthday repetition theorem and complexity of approximating dense CSPs P Manurangsi, P Raghavendra
arXiv preprint arXiv:1607.02986, 2016
117 2016 On the parameterized complexity of approximating dominating set CS Karthik, B Laekhanukit, P Manurangsi
50th Annual ACM Symposium on Theory of Computing, 1283-1296, 2018
109 2018 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
90 * 2017 Tight hardness results for training depth-2 ReLU networks S Goel, A Klivans, P Manurangsi, D Reichman
arXiv preprint arXiv:2011.13550, 2020
88 * 2020 The price of fairness for indivisible goods X Bei, X Lu, P Manurangsi, W Suksompong
Theory of Computing Systems 65, 1069-1093, 2021
84 2021 A survey on approximation in parameterized complexity: Hardness and algorithms AE Feldmann, E Lee, P Manurangsi
Algorithms 13 (6), 146, 2020
81 2020 Private robust estimation by stabilizing convex relaxations P Kothari, P Manurangsi, A Velingker
Conference on Learning Theory, 723-777, 2022
61 2022 Differentially private clustering: Tight approximation ratios B Ghazi, R Kumar, P Manurangsi
Advances in Neural Information Processing Systems 33, 4040-4054, 2020
57 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
54 * 2021 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
50 2020 User-level differentially private learning via correlated sampling B Ghazi, R Kumar, P Manurangsi
Advances in Neural Information Processing Systems 34, 20172-20184, 2021
48 2021 A Note on Max P Manurangsi
arXiv preprint arXiv:1810.03792, 2018
47 2018 Asymptotic existence of fair divisions for groups P Manurangsi, W Suksompong
Mathematical Social Sciences 89, 100-108, 2017
47 2017 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
46 2020 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
45 2020 
Badih GhaziGoogleE-mail confirmado em google.com