$\widetilde{O}(\sqrt{m})$ passes.

In Line 11, since we are finding maximum matching in a graph with $n$ vertices
and $n$ edges, we can store them in memory, then check all the $2^{n}$
possible sets of edges. This cost $\widetilde{O}(n)$ space without any pass.
We find the set of edges that is a matching and has the maximum weight.

With $O(\log n)$ iterations overhead (Line 5), the number of passes blow up by
an $O(\log n)$ factor. So overall, we used $\widetilde{O}(n)$ space and
$\widetilde{O}(\sqrt{m})$ passes. ∎

###  11.3 Correctness

The goal of this section is to prove the correctness of our algorithm (Lemma
11.3).

######  Lemma 11.3 (Correctness).

Given a bipartite graph $G$ with $n$ vertices and $m$ edges. With probability
at least $1-1/\operatorname{poly}(n)$, Algorithm 6 outputs one maximum
matching.

###### Proof.

Consider the linear programming Eq. (28). According to part 1 of Lemma 11.7,
with probability at least $1/4$, there is a unique solution $y^{*}$ to Eq.
(28).

By Lemma 10.1, with probability at least $1/2$ the algorithm
MinimumVertexCover successfully returns a subset $S$ of tight constraints
which corresponds to an optimal solution $x^{*},s^{*}$ on dual problem Eq.
(29) (note that the linear programming in Lemma 10.1 and Eq. (29) only differ
in signs). This means $s^{*}_{i}=0$ if and only if $i\in S$. According to part
1 and part 2 of Lemma 11.7, $|S|\leq n$ and $y_{i}^{*}=0$ for all $i\notin S$.
Therefore, there exists a maximum matching using only edges in $S$, and we
will find it in Line 11.

Overall, in each iteration of the for loop (Line 5), with probability at least
$(1/2)\cdot(1/4)=1/8$ we can find a maximum matching. After $O(\log n)$ loops,
we can find a maximum matching with probability at least
$1-1/\operatorname{poly}(n)$. ∎

###  11.4 Primal to dual

This section tells the preliminary stuff for proving correctness Lemma 11.3.
We give Theorem 11.6, which is later used in Lemma 11.7.

######  Definition 11.4 (Maximum weighted matching).

Given a bipartite graph $G=(V,E)$ with $|V|=n$ and $|E|=m$. Let
$A\in\\{0,1\\}^{m\times n}$ be the unsigned edge-vertex incident matrix. Given
weight $b\in\operatorname*{\mathbb{Z}}^{m}$ on every edge, the maximum
weighted matching can be written as the following linear programming:

$\displaystyle{\bf Primal}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \max_{y\in\mathbb{R}^{m}}$
$\displaystyle\leavevmode\nobreak\ b^{\top}y$ (28)
$\displaystyle\mathrm{\leavevmode\nobreak\ s.t.\leavevmode\nobreak\ }$
$\displaystyle\leavevmode\nobreak\ A^{\top}y\leq\mathbf{1}_{n}$
$\displaystyle\leavevmode\nobreak\ y\geq 0$

Its dual form is

######  Definition 11.5 (Fractional minimum vertex cover).

Let $A\in\operatorname*{\mathbb{Z}}^{m\times n}$,
$b\in\operatorname*{\mathbb{Z}}^{m}$ be defined as in Definition 11.4. The
dual form of Eq. (28) is141414The dual LP is a _generalized_ version of the
minimum vertex cover problem: each edge $i$ needs to be _covered_ by at least
$b_{i}$ times, where the case of $b=\mathbf{1}_{m}$ is the classic minimum
vertex cover.

$\displaystyle{\bf Dual}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \min_{x\in\mathbb{R}^{n}}$
$\displaystyle\leavevmode\nobreak\ \mathbf{1}_{n}^{\top}x$ (29)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\leavevmode\nobreak\ Ax\geq b$
$\displaystyle\leavevmode\nobreak\ x\geq 0$

######  Theorem 11.6 (Strong duality from complementary slackness [PS98]).

Let $y\in\mathbb{R}^{m}$ be a feasible solution to the primal Eq. (28), and
let $x\in\mathbb{R}^{n}$ be a feasible solution to the dual Eq. (29). Let
$s:=Ax-b\in\mathbb{R}^{m}$. Then
$x\in\mathbb{R}^{n},s\in\mathbb{R}^{m},y\in\mathbb{R}^{m}$ satisfy

$y^{\top}s=0\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\
}x^{\top}(\mathbf{1}_{n}-A^{\top}y)=0$

if and only if $x\in\mathbb{R}^{n},s\in\mathbb{R}^{m}$ is optimal to the dual
and $y\in\mathbb{R}^{m}$ is optimal to the primal.

###  11.5 Properties of primal and dual LP solutions

The goal of this section is to prove Lemma 11.7.

######  Lemma 11.7 (Properties of LP solutions).

Given a bipartite graph $G$ with $n$ vertices and $m$ edges. Let
$w\in\mathbb{N}^{m}$ be edge weight. Let $\overline{b}\in\mathbb{Z}^{m}$ be
the output of $\textsc{Isolation}(m,Z)$ where $Z:=n^{n}$ (Algorithm 1). Let
$b:=\overline{b}+n^{10}\cdot w\in\operatorname*{\mathbb{Z}}^{m}$. Let
$A\in\\{0,1\\}^{m\times n}$ be edge-vertex incident matrix of $G$ (unsigned).
Consider the linear programming in Eq. (28) and Eq. (29) with parameter $A$
and $b$. With probability at least $1/4$, we have

  1. 1.

There is a unique solution $y^{*}\in\mathbb{R}^{m}$ to the primal LP (Eq.
(28)). Furthermore, $y^{*}\in\\{0,1\\}^{m}$, $y^{*}$ is the maximum candidate
matching of $G$;

  2. 2.

Let $x^{*}\in\mathbb{R}^{n}$, $s^{*}\in\mathbb{R}^{m}$ be optimal solution to
the dual LP (Eq.(29)). Then we have the following properties on $s^{*}$.

    1. (a)

For any $i\in[m]$, if $s^{*}_{i}>0$ then $y^{*}_{i}=0$;

    2. (b)

$\|s^{*}\|_{0}\geq m-n$.

###### Proof.

Part 1

Let the feasible space of $y$ be $S:=\\{y\in\mathbb{R}^{m}\mid
Ay\leq\mathbf{1}_{n},y\geq 0\\}$. We implicitly have that
$y\leq\mathbf{1}_{m}$, so $S$ is a bounded region. Let $\overline{S}$ denote
all extreme points on $S$.

First, we argue that there is a unique extreme point in $\overline{S}$ which
has the optimal solution.

By Lemma 3.5, we know all extreme points is integral. Since
$\mathbf{0}_{m}\leq y\leq\mathbf{1}_{m}$, all extreme points are in
$\\{0,1\\}^{m}$, which correspond to a matching. Because we set
$b:=\overline{b}+n^{10}\cdot w$ as our objective vector, we can write $\langle
b,y\rangle=\langle\overline{b},y\rangle+n^{10}\cdot w^{\top}y$. Since
$\|\overline{b}\|_{\infty}\leq n^{7}$ by Lemma 4.2, the extreme point who has
the optimal objective value must be a maximum weighted matching. Let
$\mathcal{F}$ be all possible matchings. We have $|\mathcal{F}|\leq n^{n}=Z$.

By applying Lemma 4.2, with probability at least $1/4$, we know that there is
a unique extreme point $y^{*}$ in $\overline{S}$ which has the optimal
solution.

Because our feasible space $S$ is bounded, all point $y\in
S\backslash\overline{S}$ can be written as a linear combination of extreme
points on $S$. That is, if we write
$\overline{S}=\\{y^{(1)},\cdots,y^{(s)}\\}$ where $s:=|\overline{S}|$, then
all point $y\in S\backslash\overline{S}$ can be written as

$\displaystyle y=\sum_{i\in[s]}a_{i}y^{(i)},$

where $0\leq a_{i}<1,\forall i\in[s]$ and $\sum_{i\in[s]}a_{i}=1$. Therefore,
we have

$\displaystyle
b^{\top}y=\sum_{i\in[s]}a_{i}\cdot(b^{\top}y^{(i)})<\max_{i\in[s]}b^{\top}y^{(i)}.$

So $y^{*}$ is actually the unique optimal solution among all points in $S$.

Part 2 Part (a) follows trivially from Theorem 11.6.

Now we prove Part (b). Assume $\|s^{*}\|_{0}<m-n$. Let
$x^{*}\in\mathbb{R}^{n}$ be any optimal dual solution that relates to $s^{*}$,
i.e. $Ax^{*}-b=s^{*}$. We will show that there exist a feasible solution to
the primal $y^{\prime}\in\mathbb{R}^{m}$ such that $y^{\prime}\neq y^{*}$,
$\langle y^{\prime},s^{*}\rangle=0$, $\langle
x^{*},\mathbf{1}_{n}-A^{\top}y^{\prime}\rangle=0$. By Theorem 11.6,
$y^{\prime}$ is also an optimal solution to the primal LP, contradicting with
the uniqueness of $y^{*}$. (In fact, we will prove that such $y^{\prime}$’s
are infinitely many.)

Consider the following linear system

$\displaystyle y_{i}$ $\displaystyle=0,\leavevmode\nobreak\ \forall
i\in[m]\text{\leavevmode\nobreak\ such that\leavevmode\nobreak\ }s^{*}_{i}\neq
0$ (30) $\displaystyle A^{\top}y$ $\displaystyle=A^{\top}y^{*}.$ (31)

In constraint Eq. (30) there are less than $\|s^{*}\|_{0}<m-n$ equalities,
while in constraint Eq. (31) there are $n$ equalities. So if we write the
above system in the matrix form
$\widetilde{A}y=\widetilde{c},\leavevmode\nobreak\ y\geq\mathbf{0}_{m}$, it
must be that $\textrm{rank}(\widetilde{A})\leq\|s\|_{0}+n<m$. We obtain

$y=\widetilde{A}^{{\dagger}}\widetilde{c}+(I-\widetilde{A}^{{\dagger}}\widetilde{A})z,$

where $z\in\mathbb{R}^{m}$ is a free variable. Since
$\text{rank}(\widetilde{A}^{\top}\widetilde{A})\leq\text{rank}(\widetilde{A})<m$,
it must be
$I_{m}-\widetilde{A}^{{\dagger}}\widetilde{A}\neq\mathbf{0}_{m\times m}$.
Observe that
$f(z):=\widetilde{A}^{{\dagger}}\widetilde{c}+(I-\widetilde{A}^{{\dagger}}\widetilde{A})z$
is an affine function passing through point $y^{*}$. Also note that
$y^{*}\geq\mathbf{0}_{m}$ and $y^{*}\neq\mathbf{0}_{m}$ (otherwise
$y^{*}=\mathbf{0}_{m}$ then we can increase an arbitrary component of $y^{*}$
to $1$ to increase $b^{\top}y$, contradicting with the optimality). As a
result, $f(z)$ must pass through infinitely many points in the subspace
$y\geq\mathbf{0}_{m}$. Let $y^{\prime}$ be any such solution. By Eq. (30), we
have

$\langle y^{\prime},s^{*}\rangle=0$

By Eq.(31) and Theorem 11.6, we have

$\langle x^{*},\mathbf{1}_{n}-A^{\top}y^{\prime}\rangle=\langle
x^{*},\mathbf{1}_{n}-A^{\top}y\rangle=0$

By Theorem 11.6, $y^{\prime}$ is also an optimal solution, contradicting with
the uniqueness of $y^{*}$. ∎

## Appendix

##  Appendix A Solver reductions

In this section, we reduce the problem of solving an SDD0 system to solving an
SDDM system, giving an SDD0 solver in the streaming model, completing Section
9.

###  A.1 From SDDM0 solver to SDD0 solver

We recall Gremban’s reduction in [ST04] that reduces the problem of sovling an
SDD0 system to solving an SDDM0 system. Let $A$ be an SDD0 matrix, decompose
$A$ into $D+A_{\mathrm{neg}}+A_{\mathrm{pos}}$, where $D$ is the diagonal of
$A$, $A_{\mathrm{neg}}$ contains all the negative off-diagonal entries of $A$
with the same size, and $A_{\mathrm{pos}}$ contains all the positive off-
diagonal entries of $A$ with the same size. Consider the following linear
system

$\displaystyle\widehat{A}\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}=\widehat{b},$

where

$\displaystyle\widehat{A}=\begin{bmatrix}D+A_{\mathrm{neg}}&-A_{\mathrm{pos}}\\\
-A_{\mathrm{pos}}&D+A_{\mathrm{neg}}\end{bmatrix}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \widehat{b}=\begin{bmatrix}b\\\
-b\end{bmatrix}$

The matrix $\widehat{A}$ can be (implicitly) computed in the streaming model:
in one pass we compute and store the diagonal matrix $D$ by adding the edge
weights incident on each vertex; then $\widehat{A}$ is given as a stream of
edges (entries) since whenever an edge (an entry in $A$) arrives, we
immediately know its position in $\widehat{A}$. Note that if $Ax=b$ admits a
solution, then $x=(x_{1}-x_{2})/2$ is exactly its solution. Moreover, if

$\left\|\begin{bmatrix}x_{1}\\\
x_{2}\end{bmatrix}-\widehat{A}^{{\dagger}}\widehat{b}\right\|_{\widehat{A}}\leq\epsilon\|\widehat{A}^{{\dagger}}\widehat{b}\|_{\widehat{A}},$

then $x$ satisfies
$\|x-A^{{\dagger}}b\|_{A}\leq\epsilon\|A^{{\dagger}}b\|_{A}$. So we obtain an
SDD0 solver with asymptotically the same number of passes and space as an SDD0
sovler.

###  A.2 From SDDM solver to SDDM0 solver

In this section, we show that to approximately solve an SDDM0 system $Ay=b$,
it suffices to pre-process the input in $O(1)$ passes, approximately solve an
SDDM system $\widetilde{A}y=\widetilde{b}$ with at most the same size, and
possibly do some post-process in $O(1)$ passes.

If $A$ is positive definite, then we can solve the system by an SDDM solver,
so assume not in the following.

From Fact 3.4 we know that $A$ must be a Laplacian matrix. Therefore, it
remains to reduce the problem of (approximately) solving a Laplacian system
$Ly=b$ to (approximately) solving an SDDM system. The following facts are
well-known.

######  Fact A.1.

Given a Laplacian matrix $L$ corresponding to graph $G$, the following holds:

  * •

$L\succeq 0$;

  * •

$L\mathbf{1}_{n}=0$ and thus $\lambda_{1}(L)=0$;

  * •

$G$ is connected iff $\lambda_{2}(L)>0$.

Given a Laplacian matrix $L$ as a stream of entries, it is equivalent to treat
it as a stream of edges of $G$. In one pass, we can identify all the connected
components of $G$ using $\widetilde{O}(n)$ space (e.g., by maintaining the
spanning forest of $G$). Next, any entry in the stream is identified and
assigned to the subproblem corresponding to the connected component that
contains it.151515The above process is equivalent to partition $L$ into block
diagonal matrices, solve each linear system with respect to the submatrices
and corresponding entries of $b$, and combine the result. This does not
influence the worst-case pass and space complexity, because each subproblem
uses space proportional to the size of its connected component and the total
number of passes depends on the connected component that takes up the most
passes. Therefore, we can assume that $G$ is connected, which implies that
$\text{rank}(L)=n-1$ by Fact A.1.

The goal of approximately solving $Ly=b$ is for given error parameter
$\epsilon>0$, finding an $\epsilon$-approximate solution $x$ satisfying

$\|x-L^{{\dagger}}b\|_{L}\leq\epsilon\|L^{{\dagger}}b\|_{L}.$

If $y$ is an (exact) solution to system $Ly=b$, then
$y^{\prime}:=y-y_{1}\mathbf{1}_{n}$ is also a solution, where $y_{1}$ is the
first entry of $y$. So we can assume that the first entry of $L^{{\dagger}}b$
is $0$. (There might be many solutions, but we fix one with the first entry
being $0$.) Let $\widetilde{A}$ be the matrix $L$ with the first row and
column deleted, and let $\widetilde{b}$ be the vector $b$ with the first entry
deleted. Note that $\widetilde{A}\succ 0$.

Let $\widetilde{x}$ be an $\epsilon$-approximate solution to the system
$\widetilde{A}x=\widetilde{b}$, and let $x$ be the vector $\widetilde{x}$ with
$0$ inserted as its first entry. It must be that

$\|x-L^{{\dagger}}b\|_{L}=\|\widetilde{x}-{\widetilde{A}}^{-1}\widetilde{b}\|_{\widetilde{A}}$

because vector ${\widetilde{A}}^{-1}\widetilde{b}$ is the vector
$L^{{\dagger}}b$ with the first entry deleted.

Finally, we have that
$\|x-L^{{\dagger}}b\|_{L}\leq\epsilon\|L^{{\dagger}}b\|_{L}$ since

$\|\widetilde{x}-{\widetilde{A}}^{-1}\widetilde{b}\|_{\widetilde{A}}\leq\epsilon\|{\widetilde{A}}^{-1}\widetilde{b}\|_{\widetilde{A}}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
}\|L^{{\dagger}}b\|_{L}=\|{\widetilde{A}}^{-1}\widetilde{b}\|_{\widetilde{A}},$

which gives an $\epsilon$-approximate solution to the original system $Ly=b$.

## References

  * [AB19] Sepehr Assadi and Aaron Bernstein.  Towards a unified theory of sparsification for matching problems.  In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, volume 69, pages 11:1–11:20, 2019.
  * [ABB+19] Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein.  Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616–1635. SIAM, 2019.
  * [AG09] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In International Colloquium on Automata, Languages, and Programming, pages 328–338. Springer, 2009.
  * [AG11] Kook Jin Ahn and Sudipto Guha.  Linear programming in the semi-streaming model with application to the maximum matching problem.  In ICALP, pages 526–538. Springer, 2011.
  * [AG18] Kook Jin Ahn and Sudipto Guha.  Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.  ACM Transactions on Parallel Computing (TOPC), 4(4):1–40, 2018\.
  * [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 459–467. SIAM, 2012.
  * [AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems (PODS), pages 5–14, 2012.
  * [AKSY20] Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu.  Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems.  In FOCS, 2020.
  * [AKZ19] Sepehr Assadi, Nikolai Karpov, and Qin Zhang.  Distributed and streaming linear programming in low dimensions.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 236–253, 2019.
  * [ALT21] Sepehr Assadi, S. Cliff Liu, and Robert E. Tarjan.  An auction algorithm for bipartite matching in streaming and massively parallel computation models.  In The SIAM Symposium on Simplicity in Algorithms (SOSA@SODA’21), 2021.
  * [Ans00] Kurt M Anstreicher.  The volumetric barrier for semidefinite programming.  Mathematics of Operations Research, 25(3):365–380, 2000.
  * [AR20] Sepehr Assadi and Ran Raz.  Near-quadratic lower bounds for two-pass graph streaming algorithms.  In FOCS. https://arxiv.org/pdf/2009.01161.pdf, 2020.
  * [Ber20] Aaron Bernstein.  Improved bounds for matching in random-order streams.  In ICALP, 2020.
  * [BLN+20] Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Bipartite matching in nearly-linear time on moderately dense graphs.  In FOCS, 2020.
  * [BLSS20] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song.  Solving tall dense linear programs in nearly linear time.  In STOC, 2020.
  * [Bra20] Jan van den Brand.  A deterministic linear program solver in current matrix multiplication time.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–278. SIAM, 2020.
  * [CC07] Timothy M Chan and Eric Y Chen.  Multi-pass geometric algorithms.  Discrete & Computational Geometry, 37(1):79–102, 2007.
  * [CFCHT20] Yi-Jun Chang, Martin Farach-Colton, Tsan-Sheng Hsu, and Meng-Tsung Tsai.  Streaming complexity of spanning tree computation.  In 37th international symposium on theoretical aspects of computer science (STACS), 2020.
  * [CKM+14] Michael B Cohen, Rasmus Kyng, Gary L Miller, Jakub W Pachocki, Richard Peng, Anup B Rao, and Shen Chen Xu.  Solving sdd linear systems in nearly $m\log^{1/2}n$ time.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing(STOC), pages 343–352, 2014.
  * [CKP+21] Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Hucheng Yu.  Almost optimal super-constant-pass streaming lower bounds for reachability.  In STOC, 2021.
  * [CKST19] Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan.  Optimal lower bounds for sketching graph cuts.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2565–2569. SIAM, 2019.
  * [Cla95] Kenneth L Clarkson.  Las vegas algorithms for linear and integer programming when the dimension is small.  Journal of the ACM (JACM), 42(2):488–499, 1995.
  * [CLS19] Michael B Cohen, Yin Tat Lee, and Zhao Song.  Solving linear programs in the current matrix multiplication time.  In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019.
  * [CRS95] Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan.  Randomness-optimal unique element isolation with applications to perfect matching and related problems.  SIAM Journal on Computing, 24(5):1036–1050, 1995.
  * [DJK13] Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg.  Randomized primal-dual analysis of ranking for online bipartite matching.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 101–107. SIAM, 2013.
  * [DLY21] Sally Dong, Yin Tat Lee, and Guanghao Ye.  A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path.  In STOC, 2021.
  * [DNO14] Shahar Dobzinski, Noam Nisan, and Sigal Oren.  Economic efficiency requires interaction.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (STOC), pages 233–242, 2014.
  * [DS08] Samuel I Daitch and Daniel A Spielman.  Faster approximate lossy generalized flow via interior point algorithms.  In Proceedings of the fortieth annual ACM symposium on Theory of computing (STOC), pages 451–460, 2008.
  * [EKMS12] Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav.  Bipartite matching in the semi-streaming model.  Algorithmica, 63(1-2):490–508, 2012.
  * [FHM+20] Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mah, Anup Rao, and Ryan A Rossi.  Approximate maximum matching in random streams.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1773–1785. SIAM, 2020.
  * [FKM+04] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  In ICALP, pages 531–543. Springer, 2004.
  * [FKM+09] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  Graph distances in the data-stream model.  SIAM Journal on Computing, 38(5):1709–1727, 2009.
  * [GKK12] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  On the communication and streaming complexity of maximum bipartite matching.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 468–485. SIAM, 2012.
  * [GO13] Venkatesan Guruswami and Krzysztof Onak.  Superlinear lower bounds for multipass graph processing.  In 2013 IEEE Conference on Computational Complexity (CCC), pages 287–298. IEEE, 2013.
  * [HJST21] Baihe Huang, Shunhua Jiang, Zhao Song, and Runzhou Tao.  Solving tall dense sdps in the current matrix multiplication time.  arXiv preprint arXiv:2101.08208, 2021.
  * [HK73] John E Hopcroft and Richard M Karp.  An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.  SIAM Journal on computing, 2(4):225–231, 1973.
  * [HT56] Isidore Heller and CB Tompkins.  An extension of a theorem of dantzig’s.  Linear inequalities and related systems, 38:247–254, 1956.
  * [JKL+20] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song.  A faster interior point method for semidefinite programming.  In FOCS, 2020.
  * [JSWZ21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang.  Faster dynamic matrix inverse for faster lps.  In STOC, 2021.
  * [Kap13] Michael Kapralov.  Better bounds for matchings in the streaming model.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1679–1697. SIAM, 2013.
  * [Kar84] Narendra Karmarkar.  A new polynomial-time algorithm for linear programming.  In Proceedings of the sixteenth annual ACM symposium on Theory of computing(STOC), pages 302–311. ACM, 1984.
  * [KK15] Dmitry Kogan and Robert Krauthgamer.  Sketching cuts in graphs and hypergraphs.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 367–376, 2015.
  * [KKS14a] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.  Approximating matching size from random streams.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 734–751. SIAM, 2014.
  * [KKS14b] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.  Streaming lower bounds for approximating max-cut.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 1263–1282. SIAM, 2014.
  * [KKSV17] Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker.  (1+ ${\Omega}$(1))-approximation to max-cut requires linear space.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1703–1722. SIAM, 2017.
  * [KL11] Jonathan A Kelner and Alex Levin.  Spectral sparsification in the semi-streaming setting.  In STACS, 2011.
  * [KLM+17] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  SIAM J. Comput., 46(1):456–477, 2017.
  * [KM19] Shahbaz Khan and Shashank K. Mehta.  Depth first search in the semi-streaming model.  In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 42:1–42:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [KMM+19] Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, and Navid Nouri.  Faster spectral sparsification in dynamic streams.  In arXiv preprint. https://arxiv.org/pdf/1903.12165.pdf, 2019\.
  * [KMP10] Ioannis Koutis, Gary L. Miller, and Richard Peng.  Approaching optimality for solving sdd linear systems.  In FOCS, pages 235–244, 2010.
  * [KMP11] Ioannis Koutis, Gary L Miller, and Richard Peng.  A nearly-$m\log n$ time solver for sdd linear systems.  In 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 590–598, 2011.
  * [KNST19] Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos.  Dynamic streaming spectral sparsification in nearly linear time and space.  In arXiv preprint. https://arxiv.org/pdf/1903.12150.pdf, 2019\.
  * [KOSZ13] Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu.  A simple, combinatorial algorithm for solving sdd systems in nearly-linear time.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC), pages 911–920, 2013.
  * [KS16] Rasmus Kyng and Sushant Sachdeva.  Approximate gaussian elimination for laplacians-fast, sparse, and simple.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 573–582. IEEE, 2016.
  * [KW14] Michael Kapralov and David Woodruff.  Spanners and sparsifiers in dynamic streams.  In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC), pages 272–281, 2014.
  * [LJS19] Yang P Liu, Arun Jambulapati, and Aaron Sidford.  Parallel reachability in almost linear work and square root depth.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1664–1686. IEEE, 2019.
  * [LS13] Yin Tat Lee and Aaron Sidford.  Path finding ii: An $\widetilde{O}(m\sqrt{n})$ algorithm for the minimum cost flow problem.  arXiv preprint arXiv:1312.6713, 2013.
  * [LS14] Yin Tat Lee and Aaron Sidford.  Path finding methods for linear programming: Solving linear programs in ${O}(\sqrt{rank})$ iterations and faster algorithms for maximum flow.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424–433. IEEE, 2014.
  * [LS15] Yin Tat Lee and Aaron Sidford.  Efficient inverse maintenance and faster algorithms for linear programming.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 230–249. IEEE, 2015.
  * [LS20a] Yang P Liu and Aaron Sidford.  Faster divergence maximization for faster maximum flow.  In FOCS, 2020.
  * [LS20b] Yang P Liu and Aaron Sidford.  Faster energy maximization for faster maximum flow.  In STOC, 2020.
  * [LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.  A faster cutting plane method and its implications for combinatorial and convex optimization.  In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
  * [LSZ19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang.  Solving empirical risk minimization in the current matrix multiplication time.  In COLT, 2019.
  * [Mad13] Aleksander Madry.  Navigating central path with electrical flows: From flows to matchings, and back.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 253–262. IEEE, 2013.
  * [Mad16] Aleksander Madry.  Computing maximum flow with augmenting electrical flows.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 593–602. IEEE, 2016.
  * [McG05] Andrew McGregor.  Finding graph matchings in data streams.  In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 170–181. Springer, 2005.
  * [MS04] Marcin Mucha and Piotr Sankowski.  Maximum matchings via gaussian elimination.  In 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 248–255. IEEE, 2004.
  * [MVV87] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC), pages 345–354, 1987.
  * [NN89] Yu Nesterov and Arkadi Nemirovsky.  Self-concordant functions and polynomial-time methods in convex programming.  Report, Central Economic and Mathematic Institute, USSR Acad. Sci, 1989.
  * [NN92] Yurii Nesterov and Arkadi Nemirovski.  Conic formulation of a convex programming problem and duality.  Optimization Methods and Software, 1(2):95–115, 1992.
  * [NN94] Yurii Nesterov and Arkadi Nemirovski.  Interior-point polynomial algorithms in convex programming, volume 13.  Siam, 1994.
  * [PS98] Christos H Papadimitriou and Kenneth Steiglitz.  Combinatorial optimization: algorithms and complexity.  Courier Corporation, 1998.
  * [PS14] Richard Peng and Daniel A Spielman.  An efficient parallel solver for sdd linear systems.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (STOC), pages 333–342, 2014.
  * [PS17] Ami Paz and Gregory Schwartzman.  A $(2+\epsilon)$-approximation for maximum weight matching in the semi-streaming model.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2153–2161, 2017.
  * [Ren88] James Renegar.  A polynomial-time algorithm, based on newton’s method, for linear programming.  Mathematical Programming, 40(1-3):59–93, 1988.
  * [Ren01] James Renegar.  A mathematical view of interior-point methods in convex optimization.  SIAM, 2001.
  * [ST04] Daniel A. Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 81–90. https://arxiv.org/abs/cs/0310051, divided into https://arxiv.org/abs/0809.3232, https://arxiv.org/abs/0808.4134, https://arxiv.org/abs/cs/0607105, 2004.
  * [ST14] Daniel A. Spielman and Shang-Hua Teng.  Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems.  SIAM J. Matrix Analysis Applications, 35(3):835–885, 2014.
  * [SY21] Zhao Song and Zheng Yu.  Oblivious sketching-based central path method for solving linear programming.  In ICML, 2021.
  * [Tar83] Robert Endre Tarjan.  Data structures and network algorithms.  SIAM, 1983.
  * [Thr93] W. Thrash.  A note on the least common multiples of dense sets of integers.  ., 1993.
  * [Vai87] Pravin M Vaidya.  An algorithm for linear programming which requires ${O}(((m+n)n^{2}+(m+n)^{1.5}n){L})$arithmetic operations.  In FOCS. IEEE, 1987.
  * [Vai89] Pravin M Vaidya.  Speeding-up linear programming using fast matrix multiplication.  In FOCS. IEEE, 1989.
  * [Ye20] Guanghao Ye.  Fast algorithm for solving structured convex programs.  The University of Washington, Undergraduate Thesis, 2020.