67 citations · 176 across the 22 of their papers we have counts for
6 papers · 1 filter
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
Parallel Submodular Function Minimization
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang +1
We consider the parallel complexity of submodular function minimization (SFM). We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function…
Sparse Submodular Function Minimization
Andrei Graur, Haotian Jiang, Aaron Sidford
In this paper we study the problem of minimizing a submodular function that is guaranteed to have a -sparse minimizer. We give a deterministic a…
Quantum speedups for stochastic optimization
Aaron Sidford, Chenyi Zhang
We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Li…
Towards Optimal Effective Resistance Estimation
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
We provide new algorithms and conditional hardness for the problem of estimating effective resistances in -node -edge undirected, expander graphs. We provide an $\widetilde{O…
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford +1
We study dynamic -approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contributi…