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
2402012
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
1382015
Distributed approximation algorithms for weighted shortest paths
D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
1242014
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
862015
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
812010
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
M Henzinger, S Krinninger, D Nanongkai
SIAM Journal on Computing, STOC16-98-STOC16-137, 2019
662019
Distributed Computation of Large-scale Graph Problems
H Klauck, D Nanongkai, PR Gopal Pandurangan
ACM-SIAM Symposium on Discrete Algorithms, 391-410, 2015
66*2015
Decremental single-source shortest paths on undirected graphs in near-linear total update time
M Henzinger, S Krinninger, D Nanongkai
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 146-155, 2014
582014
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
562013
Representative skylines using threshold-based preference distributions
A Das Sarma, A Lall, D Nanongkai, RJ Lipton, J Xu
Data Engineering (ICDE), 2011 IEEE 27th International Conference on, 387-398, 2011
522011
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
502016
Randomized multi-pass streaming skyline algorithms
A Das Sarma, A Lall, D Nanongkai, J Xu
Proceedings of the VLDB Endowment 2 (1), 85-96, 2009
502009
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
M Henzinger, S Krinninger, D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
482014
Distributed random walks
A Das Sarma, D Nanongkai, G Pandurangan, P Tetali
Journal of the ACM (JACM) 60 (1), 2, 2013
482013
Graph products revisited: Tight approximation hardness of induced matching, poset dimension and more
P Chalermsook, B Laekhanukit, D Nanongkai
Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete …, 2013
482013
Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses
P Chalermsook, B Laekhanukit, D Nanongkai
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 370-379, 2013
472013
A tight unconditional lower bound on distributed randomwalk computation
D Nanongkai, A Das Sarma, G Pandurangan
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of …, 2011
462011
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
412017
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
412017
Fast distributed random walks
A Das Sarma, D Nanongkai, G Pandurangan
Proceedings of the 28th ACM symposium on Principles of distributed computing …, 2009
412009
The system can't perform the operation now. Try again later.
Articles 1–20