8 citations · 19 across the 5 of their papers we have counts for
5 papers
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai +1
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" al…
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Joakim Blikstad, Jan van den Brand, Yuval Efron +2
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AN…
Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
The study of graph products is a major research topic and typically concerns the term , e.g., to show that . In this paper, we study graph products in a no…
Almost-Tight Distributed Minimum Cut Algorithms
Danupon Nanongkai, Hsin-Hao Su
We study the problem of computing the minimum cut in a weighted distributed message-passing networks (the CONGEST model). Let be the minimum cut, be the number of nodes in…
Distributed Symmetry Breaking in Hypergraphs
Shay Kutten, Danupon Nanongkai, Gopal Pandurangan +1
Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (stan…