Danupon Nanongkai

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., October, 2023

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.

[BibT_eX]

[DOI]

CoRR, 2023

Fast Algorithms via Dynamic-Oracle Matroids.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fully Dynamic Exact Edge Connectivity in Sublinear Time.

[BibT_eX]

[DOI]

Gramoz Goranci

Mikkel Thorup

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Near-Linear Time Approximations for Cut Problems via Fair Cuts.

[BibT_eX]

[DOI]

Jason Li

Debmalya Panigrahi

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Equivalence classes and conditional hardness in massively parallel computations.

[BibT_eX]

[DOI]

Michele Scquizzato

Distributed Comput., 2022

Negative-Weight Single-Source Shortest Paths in Almost-linear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time.

[BibT_eX]

[DOI]

Jason Li

Debmalya Panigrahi

Karthekeyan Chandrasekaran

CoRR, 2022

Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition.

[BibT_eX]

[DOI]

Calvin Beideman

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver.

[BibT_eX]

[DOI]

Chien-Chung Huang

Pattara Sukprasert

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

[BibT_eX]

[DOI]

Maximilian Probst Gutenberg

Jan van den Brand

Aaron Sidford

He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Nearly Optimal Communication and Query Complexity of Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Negative-Weight Single-Source Shortest Paths in Near-linear Time.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Cut Query Algorithms with Star Contraction.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Minimum Cuts in Directed Graphs via √n Max-Flows.

[BibT_eX]

[DOI]

CoRR, 2021

A Note on Isolating Cut Lemma for Submodular Function Minimization.

[BibT_eX]

[DOI]

CoRR, 2021

Vertex connectivity in poly-logarithmic max-flows.

[BibT_eX]

[DOI]

Jason Li

Debmalya Panigrahi

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Distributed weighted min-cut in nearly-optimal time.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Breaking the quadratic barrier for matroid intersection.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.

[BibT_eX]

[DOI]

Andrés López-Martínez

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Minimum Cuts in Directed Graphs via Partial Sparsification.

[BibT_eX]

[DOI]

Kent Quanrud

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018).

[BibT_eX]

[DOI]

Thomas Vidick

Dimitris Achlioptas

SIAM J. Comput., 2020

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

An Improved Algorithm for Dynamic Set Cover.

[BibT_eX]

[DOI]

CoRR, 2020

Weighted min-cut: sequential, cut-query, and streaming algorithms.

[BibT_eX]

[DOI]

Proceedings 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.

[BibT_eX]

[DOI]

Sebastian Forster

Liu Yang

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Coarse-Grained Complexity for Dynamic Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[BibT_eX]

[DOI]

Aaron Sidford

Zhao Song

Di Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

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

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

New Tools and Connections for Exponential-Time Approximation.

[BibT_eX]

[DOI]

Algorithmica, 2019

Breaking quadratic time for small vertex connectivity and an approximation scheme.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed edge connectivity in sublinear time.

[BibT_eX]

[DOI]

Mohit Daga

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed exact weighted all-pairs shortest paths in near-linear time.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds.

[BibT_eX]

[DOI]

Jan van den Brand

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.

[BibT_eX]

[DOI]

Jan van den Brand

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A New Deterministic Algorithm for Dynamic Set Cover.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. ACM, 2018

Dynamic Algorithms for Graph Coloring.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Faster Distributed Single-Source Shortest Paths Algorithm.

[BibT_eX]

[DOI]

Sebastian Forster

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.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time.

[BibT_eX]

[DOI]

CoRR, 2017

Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds.

[BibT_eX]

[DOI]

Chien-Chung Huang

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time.

[BibT_eX]

[DOI]

CoRR, 2016

New deterministic approximation algorithms for fully dynamic matching.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

CoRR, 2015

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Distributed Computation of Large-scale Graph Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Social Network Monetization via Sponsored Viral Marketing.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Faster Algorithms for Semi-Matching Problems.

[BibT_eX]

[DOI]

Jittat Fakcharoenphol

ACM Trans. Algorithms, 2014

Polynomial-Time Algorithms for Energy Games with Special Weight Structures.

[BibT_eX]

[DOI]

Krishnendu Chatterjee

Algorithmica, 2014

Almost-Tight Distributed Minimum Cut Algorithms.

[BibT_eX]

[DOI]

Hsin-Hao Su

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Distributed Symmetry Breaking in Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Distributed approximation algorithms for weighted shortest paths.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Brief announcement: almost-tight approximation distributed algorithm for minimum cut.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Can quantum communication speed up distributed computation?

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

An Approximate Restatement of the Four-Color Theorem.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2013

Distributed Random Walks.

[BibT_eX]

[DOI]

J. ACM, 2013

Simple FPTAS for the subset-sums ratio problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

The Distributed Complexity of Large-scale Graph Processing.

[BibT_eX]

[DOI]

CoRR, 2013

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2013

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Distributed Verification and Hardness of Distributed Approximation.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Quantum Distributed Network Computing: Lower Bounds and Techniques

[BibT_eX]

[DOI]

CoRR, 2012

Multi-Attribute Profit-Maximizing Pricing (Extended Abstract)

[BibT_eX]

[DOI]

CoRR, 2012

Dense Subgraphs on Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Interactive regret minimization.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2012

Brief announcement: maintaining large dense subgraphs on dynamic networks.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011

Best-order streaming model.

[BibT_eX]

[DOI]

Richard J. Lipton

Theor. Comput. Sci., 2011

A Tight Lower Bound on Distributed Random Walk Computation

[BibT_eX]

[DOI]

Gopal Pandurangan

CoRR, 2011

A tight unconditional lower bound on distributed randomwalk computation.

[BibT_eX]

[DOI]

Gopal Pandurangan

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Representative skylines using threshold-based preference distributions.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Data Engineering, 2011

2010

Regret-Minimizing Representative Databases.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Efficient distributed random walks with applications.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Faster Algorithms for Semi-matching Problems (Extended Abstract).

[BibT_eX]

[DOI]

Jittat Fakcharoenphol

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Randomized Multi-pass Streaming Skyline Algorithms.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2009

Near-Optimal Sublinear Time Bounds for Distributed Random Walks

[BibT_eX]

[DOI]

CoRR, 2009

Stackelberg Pricing is Hard to Approximate within 2-ε

[BibT_eX]

[DOI]

CoRR, 2009

Fast distributed random walks.

[BibT_eX]

[DOI]

Gopal Pandurangan

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.

[BibT_eX]

[DOI]

Jittat Fakcharoenphol