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
2572012
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
1592015
Distributed approximation algorithms for weighted shortest paths
D Nanongkai
Proceedings of the forty-sixth annual ACM symposium on Theory of computing …, 2014
1292014
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
922015
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
852010
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
722019
Distributed Computation of Large-scale Graph Problems
H Klauck, D Nanongkai, PR Gopal Pandurangan
ACM-SIAM Symposium on Discrete Algorithms, 391-410, 2015
71*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
632014
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
622013
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
562016
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
552017
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
532011
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
522017
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
512013
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
512009
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
502014
Distributed random walks
A Das Sarma, D Nanongkai, G Pandurangan, P Tetali
Journal of the ACM (JACM) 60 (1), 2, 2013
502013
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
492013
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
492011
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
472017
The system can't perform the operation now. Try again later.
Articles 1–20