| 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 | 355 | 2015 |
| Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances J Van Den Brand, YT Lee, YP Liu, T Saranurak, A Sidford, Z Song, ... Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 152 | 2021 |
| 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 | 140 | 2017 |
| 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 | 128 | 2020 |
| 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 | 125 | 2020 |
| 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 | 123 | 2017 |
| Expander decomposition and pruning: Faster, stronger, and simpler T Saranurak, D Wang Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019 | 115 | 2019 |
| 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 | 85 | 2019 |
| The expander hierarchy and its applications to dynamic graph algorithms G Goranci, H Räcke, T Saranurak, Z Tan Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021 | 80 | 2021 |
| Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing A Bernstein, MP Gutenberg, T Saranurak 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020 | 71 | 2020 |
| Deterministic decremental sssp and approximate min-cost flow in almost-linear time A Bernstein, MP Gutenberg, T Saranurak 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022 | 65 | 2022 |
| Fully-dynamic graph sparsifiers against an adaptive adversary A Bernstein, J Brand, MP Gutenberg, D Nanongkai, T Saranurak, ... arXiv preprint arXiv:2004.08432, 2020 | 57 | 2020 |
| Improved distributed expander decomposition and nearly optimal triangle enumeration YJ Chang, T Saranurak Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing …, 2019 | 55 | 2019 |
| Fast dynamic cuts, distances and effective resistances via vertex sparsifiers L Chen, G Goranci, M Henzinger, R Peng, T Saranurak 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020 | 54 | 2020 |
| Vertex connectivity in poly-logarithmic max-flows J Li, D Nanongkai, D Panigrahi, T Saranurak, S Yingchareonthawornchai Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021 | 50 | 2021 |
| Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms S Forster, D Nanongkai, L Yang, T Saranurak, S Yingchareonthawornchai Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 50 | 2020 |
| Sensitive distance and reachability oracles for large batch updates J van den Brand, T Saranurak 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019 | 50 | 2019 |
| Distributed Exact Weighted All-Pairs Shortest Paths in Ġ (n^{5/4}) Rounds CC Huang, D Nanongkai, T Saranurak 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 46 | 2017 |
| Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds A Beimel, H Kaplan, Y Mansour, K Nissim, T Saranurak, U Stemmer Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022 | 40 | 2022 |
| Breaking quadratic time for small vertex connectivity and an approximation scheme D Nanongkai, T Saranurak, S Yingchareonthawornchai Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019 | 40 | 2019 |
Danupon NanongkaiDirector, Max Planck Institute for InformaticsVerified email at mpi-inf.mpg.de
