Follow
Pasin Manurangsi
Title
Cited by
Cited by
Year
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
1352017
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
942017
A birthday repetition theorem and complexity of approximating dense CSPs
P Manurangsi, P Raghavendra
arXiv preprint arXiv:1607.02986, 2016
802016
On the parameterized complexity of approximating dominating set
CS Karthik, B Laekhanukit, P Manurangsi
STOC 2018-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of†…, 2018
642018
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
60*2017
Asymptotic existence of fair divisions for groups
P Manurangsi, W Suksompong
Mathematical Social Sciences 89, 100-108, 2017
402017
The price of fairness for indivisible goods
X Bei, X Lu, P Manurangsi, W Suksompong
Theory of Computing Systems 65 (7), 1069-1093, 2021
372021
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
37*2021
Private aggregation from fewer anonymous messages
B Ghazi, P Manurangsi, R Pagh, A Velingker
Annual International Conference on the Theory and Applications of†…, 2020
372020
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
342020
The computational complexity of training relu (s)
P Manurangsi, D Reichman
arXiv preprint arXiv:1810.04207, 2018
332018
A survey on approximation in parameterized complexity: Hardness and algorithms
AE Feldmann, CS Karthik, E Lee, P Manurangsi
Algorithms 13 (6), 146, 2020
302020
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
272021
On closest pair in euclidean metric: Monochromatic is as hard as bichromatic
CS Karthik, P Manurangsi
Combinatorica 40 (4), 539-573, 2020
262020
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
232020
ETH-hardness of approximating 2-CSPs and Directed Steiner Network
I Dinur, P Manurangsi
arXiv preprint arXiv:1805.03867, 2018
232018
An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
H Angelidakis, Y Makarychev, P Manurangsi
International Conference on Integer Programming and Combinatorial†…, 2017
232017
Parameterized approximation algorithms for bidirected Steiner network problems
R Chitnis, AE Feldmann, P Manurangsi
ACM Transactions on Algorithms (TALG) 17 (2), 1-68, 2021
222021
A Note on Max -Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
P Manurangsi
arXiv preprint arXiv:1810.03792, 2018
222018
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
212020
The system can't perform the operation now. Try again later.
Articles 1–20