67 citations · 176 across the 22 of their papers we have counts for
16 papers · 1 filter
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +2
In this paper we consider the classic matroid intersection problem: given two matroids $\M_{1}=(V,\I_{1})$ and $\M_{2}=(V,\I_{2})$ defined over a common ground set , compute a s…
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu, Aaron Sidford
In this paper we provide an algorithm which given any -edge -vertex directed graph with integer capacities at most computes a maximum - flow for any vertices an…
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
Yujia Jin, Aaron Sidford
Given a data matrix , principal component projection (PCP) and principal component regression (PCR), i.e. projection and regression restrict…
Solving Linear Programs with Sqrt(rank) Linear System Solves
Yin Tat Lee, Aaron Sidford
We present an algorithm that given a linear program with variables, constraints, and constraint matrix , computes an -approximate solution in $\tilde{O}(\sqrt{rank(A)…
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
Brian Axelrod, Yang P. Liu, Aaron Sidford
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given a…
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
Aaron Sidford, Mengdi Wang, Lin F. Yang +1
In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with d…