Follow
Danupon Nanongkai
Title
Cited by
Cited by
Year
Distributed verification and hardness of distributed approximation
A Das Sarma, S Holzer, L Kor, A Korman, D Nanongkai, G Pandurangan, ...
SIAM Journal on Computing, 2012
3662012
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
M Henzinger, S Krinninger, D Nanongkai, T Saranurak
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
3342015
Distributed approximation algorithms for weighted shortest paths
D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
1892014
Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
S Bhattacharya, M Henzinger, D Nanongkai, C Tsourakakis
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
1612015
Regret-minimizing representative databases
D Nanongkai, AD Sarma, A Lall, RJ Lipton, J Xu
Proceedings of the VLDB Endowment 3 (1-2), 1114-1124, 2010
1412010
Dynamic minimum spanning forest with subpolynomial worst-case update time
D Nanongkai, T Saranurak, C Wulff-Nilsen
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
1312017
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
M Henzinger, S Krinninger, D Nanongkai
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
1312016
A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
J Chuzhoy, Y Gao, J Li, D Nanongkai, R Peng, T Saranurak
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
1182020
Bipartite matching in nearly-linear time on moderately dense graphs
J van den Brand, YT Lee, D Nanongkai, R Peng, T Saranurak, A Sidford, ...
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
1142020
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
D Nanongkai, T Saranurak
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
1142017
New deterministic approximation algorithms for fully dynamic matching
S Bhattacharya, M Henzinger, D Nanongkai
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
1132016
Distributed Computation of Large-scale Graph Problems
H Klauck, D Nanongkai, PR Gopal Pandurangan
ACM-SIAM Symposium on Discrete Algorithms, 391-410, 2015
1122015
Decremental single-source shortest paths on undirected graphs in near-linear total update time
M Henzinger, S Krinninger, D Nanongkai
Journal of the ACM (JACM) 65 (6), 1-40, 2018
1082018
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
1002017
Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
M Henzinger, S Krinninger, D Nanongkai
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on …, 2013
982013
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
S Bhattacharya, M Henzinger, D Nanongkai
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017
872017
Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds
J van den Brand, D Nanongkai, T Saranurak
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019
802019
Dynamic algorithms for graph coloring
S Bhattacharya, D Chakrabarty, M Henzinger, D Nanongkai
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete …, 2018
792018
Distributed random walks
A Das Sarma, D Nanongkai, G Pandurangan, P Tetali
Journal of the ACM (JACM) 60 (1), 2, 2013
762013
A faster distributed single-source shortest paths algorithm
S Forster, D Nanongkai
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018
742018
The system can't perform the operation now. Try again later.
Articles 1–20