Research
Research
Research
Research
22+ open-access research outputs.
We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$-node $m$-arc networks. Our results imply an $n^{\omega + o(1)}$-time strongly polynomial time algorithms fo…
We introduce fast algorithms for solving $\ell_{p}$ regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iteration complexity, outpe…
Effective Resistance (ER) is a fundamental tool in various graph learning tasks. In this paper, we address the problem of efficiently approximating ER on a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})…
For $n$-vertex $m$-edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with $\tilde O(m+n^ {1.5})$ work and…
We provide an algorithm that, given an $n$-vertex $m$-edge Eulerian graph with polynomially bounded weights, computes an $\breve{O}(n\log^{2} n \cdot \varepsilon^{-2})$-edge $\varepsilon$-approximate …
In this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time \~O(m). Further, our algorithm can maintain such a decomposition in a…
Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear system solvers are cru…
We provide an algorithm which, with high probability, maintains a $(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing $m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ tim…
We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and cap…
We provide new algorithms and conditional hardness for the problem of estimating effective resistances in $n$-node $m$-edge undirected, expander graphs. We provide an $\widetilde{O}(m\epsilon^{-1})$-t…
A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly …
In this paper we provide an algorithm for maintaining a $(1-\epsilon)$-approximate maximum flow in a dynamic, capacitated graph undergoing edge additions. Over a sequence of $m$-additions to an $n$-no…
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem is ba…
We show that the sparsified block elimination algorithm for solving undirected Laplacian linear systems from [Kyng-Lee-Peng-Sachdeva-Spielman STOC'16] directly works for directed Laplacians. Given acc…
In this paper we obtain improved iteration complexities for solving $\ell_p$ regression. We provide methods which given any full-rank $\mathbf{A} \in \mathbb{R}^{n \times d}$ with $n \geq d$, $b \in \…
Success in academia hinges on publishing in top tier journals. This requires innovative results. And this requires clear and convincing presentation of said results. Presentation can make the differen…
Recommendation Systems (RS) have become an essential part of many online services. Due to its pivotal role in guiding customers towards purchasing, there is a natural motivation for unscrupulous parti…
In this paper we provide an algorithm which given any $m$-edge $n$-vertex directed graph with integer capacities at most $U$ computes a maximum $s$-$t$ flow for any vertices $s$ and $t$ in $m^{4/3+o(1…
We present an $m^{4/3+o(1)}\log W$-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where $W$ is the maximum absolute value of any edge weight. For sparse graphs,…
In this paper we provide an algorithm which given any $m$-edge $n$-vertex directed graph with integer capacities at most $U$ computes a maximum $s$-$t$ flow for any vertices $s$ and $t$ in $m^{11/8+o(…
Free open-access publishing with Google Scholar indexing.
Submission Guide →