pith. sign in

Danupon Nanongkai

Identifiers

  • name variant Danupon Nanongkai 0.60 · backfill

Papers (38)

  1. Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries cs.DS · 2019 · author #1
  2. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds cs.DS · 2019 · author #2
  3. Distributed Edge Connectivity in Sublinear Time cs.DS · 2019 · author #3
  4. Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time cs.DC · 2018 · author #2
  5. Dynamic Algorithms for Graph Coloring cs.DS · 2017 · author #4
  6. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More cs.CC · 2017 · author #6
  7. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time cs.DS · 2017 · author #1
  8. Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds cs.DC · 2017 · author #2
  9. New Tools and Connections for Exponential-time Approximation cs.DS · 2017 · author #4
  10. Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(\log^3 n)$ Worst Case Update Time cs.DS · 2017 · author #3
  11. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs cs.DS · 2016 · author #3
  12. Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-\epsilon})$-Time cs.DS · 2016 · author #1
  13. Polynomial-Time Algorithms for Energy Games with Special Weight Structures cs.DS · 2016 · author #4
  14. New Deterministic Approximation Algorithms for Fully Dynamic Matching cs.DS · 2016 · author #3
  15. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time cs.DS · 2015 · author #3
  16. Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks cs.DS · 2015 · author #3
  17. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture cs.DS · 2015 · author #3
  18. Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs cs.DS · 2015 · author #3
  19. A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths cs.DC · 2015 · author #3
  20. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams cs.DS · 2015 · author #3
  21. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs cs.CC · 2014 · author #3
  22. Almost-Tight Distributed Minimum Cut Algorithms cs.DS · 2014 · author #1
  23. Distributed Symmetry Breaking in Hypergraphs cs.DC · 2014 · author #2
  24. Brief Announcement: Almost-Tight Approximation Distributed Algorithm for Minimum Cut cs.DS · 2014 · author #1
  25. Distributed Approximation Algorithms for Weighted Shortest Paths cs.DS · 2014 · author #1
  26. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses cs.CC · 2013 · author #3
  27. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization cs.DS · 2013 · author #3
  28. Distributed Random Walks cs.DC · 2013 · author #2
  29. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More cs.DM · 2012 · author #3
  30. Dense Subgraphs on Dynamic Networks cs.DC · 2012 · author #3
  31. Can Quantum Communication Speed Up Distributed Computation? cs.DC · 2012 · author #3
  32. Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs cs.GT · 2012 · author #4
  33. Geometric Pricing: How Low Dimensionality Helps in Approximability cs.GT · 2012 · author #3
  34. A Tight Lower Bound on Distributed Random Walk Computation cs.DC · 2011 · author #1
  35. Distributed Verification and Hardness of Distributed Approximation cs.DC · 2010 · author #5
  36. Faster Algorithms for Semi-Matching Problems cs.DS · 2010 · author #3
  37. Efficient Distributed Random Walks with Applications cs.DC · 2009 · author #2
  38. Stackelberg Pricing is Hard to Approximate within $2-\epsilon$ cs.GT · 2009 · author #3

Mentions

  • 1302.4544 #2 · backfill · confidence 0.70 Danupon Nanongkai
  • 1212.4129 #3 · backfill · confidence 0.70 Danupon Nanongkai
  • 1208.1454 #3 · backfill · confidence 0.70 Danupon Nanongkai
  • 1207.5211 #3 · backfill · confidence 0.70 Danupon Nanongkai
  • 1203.1940 #4 · backfill · confidence 0.70 Danupon Nanongkai
  • 1202.2840 #3 · backfill · confidence 0.70 Danupon Nanongkai
  • 1102.2906 #1 · backfill · confidence 0.70 Danupon Nanongkai
  • 1011.3049 #5 · backfill · confidence 0.70 Danupon Nanongkai
  • 1004.3363 #3 · backfill · confidence 0.70 Danupon Nanongkai
  • 0911.3195 #2 · backfill · confidence 0.70 Danupon Nanongkai
  • 0910.0443 #3 · backfill · confidence 0.70 Danupon Nanongkai

Frequent Coauthors