☰

Danupon Nanongkai, Ph.D. - Publications

Affiliations: 
2011 Georgia Institute of Technology, Atlanta, GA 
Area:
Computer Science, Applied Mathematics
Tree Info Similar researchers PubMed Report error

32 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2022 Nanongkai D, Scquizzato M. Equivalence classes and conditional hardness in massively parallel computations. Distributed Computing. 35: 165-183. PMID 35300185 DOI: 10.1007/s00446-021-00418-2  0.333
2019 Bansal N, Chalermsook P, Laekhanukit B, Nanongkai D, Nederlof J. New Tools and Connections for Exponential-Time Approximation. Algorithmica. 81: 3993-4009. PMID 31496549 DOI: 10.1007/S00453-018-0512-8  0.449
2016 Bhattacharya S, Henzinger M, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching Proceedings of the Annual Acm Symposium On Theory of Computing. 19: 398-411. DOI: 10.1145/2897518.2897568  0.352
2016 Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths Proceedings of the Annual Acm Symposium On Theory of Computing. 19: 489-498. DOI: 10.1137/16M1097808  0.393
2015 Bhattacharya S, Henzinger M, Nanongkai D, Tsourakakis CE. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 173-182. DOI: 10.1145/2746539.2746592  0.36
2015 Klauck H, Nanongkai D, Pandurangan G, Robinson P. Distributed computation of large-scale graph problems Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 2015: 391-410.  0.346
2014 Henzinger M, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 146-155. DOI: 10.1145/3218657  0.395
2014 Nanongkai D. Brief announcement: Almost-tight approximation distributed algorithm for minimum cut Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 382-384. DOI: 10.1145/2611462.2611511  0.354
2014 Elkin M, Klauck H, Nanongkai D, Pandurangan G. Can quantum communication speed up distributed computation? Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 166-175. DOI: 10.1145/2611462.2611488  0.317
2014 Fakcharoenphol J, Laekhanukit B, Nanongkai D. Faster algorithms for semi-matching problems Acm Transactions On Algorithms. 10. DOI: 10.1145/2601071  0.391
2014 Henzinger M, Krinninger S, Nanongkai D. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs Proceedings of the Annual Acm Symposium On Theory of Computing. 674-683. DOI: 10.1145/2591796.2591869  0.318
2014 Nanongkai D. Distributed approximation algorithms for weighted shortest paths Proceedings of the Annual Acm Symposium On Theory of Computing. 565-573. DOI: 10.1145/2591796.2591850  0.357
2014 Nanongkai D, Su HH. Almost-tight distributed minimum cut algorithms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8784: 439-453.  0.378
2014 Kutten S, Nanongkai D, Pandurangan G, Robinson P. Distributed symmetry breaking in hypergraphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8784: 469-483.  0.402
2013 Das Sarma A, Gajewar AS, Lipton RJ, Nanongkai D. An approximate restatement of the Four-Color Theorem Journal of Graph Algorithms and Applications. 17: 567-573. DOI: 10.7155/Jgaa.00304  0.61
2013 Henzinger M, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7966: 607-619. DOI: 10.1145/3146550  0.477
2013 Das Sarma A, Nanongkai D, Pandurangan G, Tetali P. Distributed random walks Journal of the Acm. 60. DOI: 10.1145/2432622.2432624  0.654
2013 Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 538-547. DOI: 10.1137/140957299  0.397
2013 Chalermsook P, Laekhanukit B, Nanongkai D. Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 370-379. DOI: 10.1109/FOCS.2013.47  0.313
2013 Nanongkai D. Simple FPTAS for the subset-sums ratio problem Information Processing Letters. 113: 750-753. DOI: 10.1016/J.Ipl.2013.07.009  0.351
2013 Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. Polynomial-Time Algorithms for Energy Games with Special Weight Structures Algorithmica. 70: 457-492. DOI: 10.1007/S00453-013-9843-7  0.42
2012 Nanongkai D, Lall A, Das Sarma A, Makino K. Interactive regret minimization Proceedings of the Acm Sigmod International Conference On Management of Data. 109-120. DOI: 10.1145/2213836.2213850  0.542
2012 Sarma AD, Holzer S, Kor L, Korman A, Nanongkai D, Pandurangan G, Peleg D, Wattenhofer R. Distributed verification and hardness of distributed approximation Siam Journal On Computing. 41: 1235-1265. DOI: 10.1137/11085178X  0.379
2012 Das Sarma A, Lall A, Nanongkai D, Trehan A. Dense subgraphs on dynamic networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7611: 151-165. DOI: 10.1007/978-3-642-33651-5_11  0.572
2012 Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7501: 301-312. DOI: 10.1007/978-3-642-33090-2_27  0.328
2011 Nanongkai D, Das Sarma A, Pandurangan G. A tight unconditional lower bound on distributed randomwalk computation Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 257-266. DOI: 10.1145/1993806.1993853  0.637
2011 Das Sarma A, Lall A, Nanongkai D, Lipton RJ, Xu J. Representative skylines using threshold-based preference distributions Proceedings - International Conference On Data Engineering. 387-398. DOI: 10.1109/ICDE.2011.5767873  0.561
2011 Das Sarma A, Lipton RJ, Nanongkai D. Best-order streaming model Theoretical Computer Science. 412: 2544-2555. DOI: 10.1016/j.tcs.2010.10.046  0.618
2010 Sarma AD, Nanongkai D, Pandurangan G, Tetali P. Efficient distributed random walks with applications Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 201-210. DOI: 10.1145/1835698.1835745  0.4
2009 Sarma AD, Nanongkai D, Pandurangan G. Fast distributed random walks Proceedings of the Annual Acm Symposium On Principles of Distributed Computing. 161-170. DOI: 10.1145/1582716.1582745  0.406
2009 Sarma AD, Lipton RJ, Nanongkai D. Best-order streaming model Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5532: 178-191. DOI: 10.1016/J.Tcs.2010.10.046  0.421
2004 Chalermsook P, Fakcharoenphol J, Nanongkai D. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 821-822.  0.335
Show low-probability matches.