Danupon Nanongkai

According to our database1, Danupon Nanongkai authored at least 76 papers between 2004 and 2020.

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

2020
Distributed Weighted Min-Cut in Nearly-Optimal Time.
CoRR, 2020

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
CoRR, 2020

An Improved Algorithm for Dynamic Set Cover.
CoRR, 2020

Weighted min-cut: sequential, cut-query, and streaming algorithms.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Coarse-Grained Complexity for Dynamic Algorithms.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond.
CoRR, 2019

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex.
CoRR, 2019

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries.
CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.
Algorithmica, 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

Equivalence Classes and Conditional Hardness in Massively Parallel Computations.
Proceedings of the 23rd International Conference on Principles of Distributed Systems, 2019

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A New Deterministic Algorithm for Dynamic Set Cover.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
J. ACM, 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

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time.
CoRR, 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

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.
SIAM J. Comput., 2016

Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time.
CoRR, 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
An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths.
CoRR, 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

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.
Algorithmica, 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

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

The Distributed Complexity of Large-scale Graph Processing.
CoRR, 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

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
Distributed Verification and Hardness of Distributed Approximation.
SIAM J. Comput., 2012

Quantum Distributed Network Computing: Lower Bounds and Techniques
CoRR, 2012

Multi-Attribute Profit-Maximizing Pricing (Extended Abstract)
CoRR, 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

2011
Best-order streaming model.
Theor. Comput. Sci., 2011

A Tight Lower Bound on Distributed Random Walk Computation
CoRR, 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.
Proc. VLDB Endow., 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.
Proc. VLDB Endow., 2009

Near-Optimal Sublinear Time Bounds for Distributed Random Walks
CoRR, 2009

Stackelberg Pricing is Hard to Approximate within 2-ε
CoRR, 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...