Danupon Nanongkai

According to our database1, Danupon Nanongkai authored at least 53 papers between 2004 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Breaking quadratic time for small vertex connectivity and an approximation scheme.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed edge connectivity in sublinear time.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed exact weighted all-pairs shortest paths in near-linear time.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018
Dynamic Algorithms for Graph Coloring.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Faster Distributed Single-Source Shortest Paths Algorithm.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.
ACM Trans. Algorithms, 2017

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization.
Encyclopedia of Algorithms, 2016

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

New deterministic approximation algorithms for fully dynamic matching.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Distributed Computation of Large-scale Graph Problems.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Social Network Monetization via Sponsored Viral Marketing.
Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2015

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Faster Algorithms for Semi-Matching Problems.
ACM Trans. Algorithms, 2014

Almost-Tight Distributed Minimum Cut Algorithms.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Distributed Symmetry Breaking in Hypergraphs.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Distributed approximation algorithms for weighted shortest paths.
Proceedings of the Symposium on Theory of Computing, 2014

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs.
Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Brief announcement: almost-tight approximation distributed algorithm for minimum cut.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Can quantum communication speed up distributed computation?
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
An Approximate Restatement of the Four-Color Theorem.
J. Graph Algorithms Appl., 2013

Distributed Random Walks.
J. ACM, 2013

Simple FPTAS for the subset-sums ratio problem.
Inf. Process. Lett., 2013

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.
Chicago J. Theor. Comput. Sci., 2013

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Dense Subgraphs on Dynamic Networks.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Interactive regret minimization.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012

Brief announcement: maintaining large dense subgraphs on dynamic networks.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Distributed verification and hardness of distributed approximation.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

A tight unconditional lower bound on distributed randomwalk computation.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Representative skylines using threshold-based preference distributions.
Proceedings of the 27th International Conference on Data Engineering, 2011

2010
Regret-Minimizing Representative Databases.
PVLDB, 2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Efficient distributed random walks with applications.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Faster Algorithms for Semi-matching Problems (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Randomized Multi-pass Streaming Skyline Algorithms.
PVLDB, 2009

Best-Order Streaming Model.
Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

Fast distributed random walks.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2004
A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004


  Loading...