The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids M1 = (V, I1) and M2 = (V, I2) on a comment ground set V of n elements, and then we have to find the largest common independent set S e I1 I2 by making independence oracle queries of the form "Is S e I1?"or "Is S e I2?"for S ? V. The goal is to minimize the number of queries. Beating the existing O(n2) bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunningham's algorithm [SICOMP 1986], whose O(n2)-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019] (more generally, these algorithms take O(nr) queries where r denotes the rank which can be as big as n). The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with o(n2) independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing O(n9/5) independence queries with high probability, and a deterministic algorithm guaranteeing O(n11/6) independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results. 

Dynamic algorithms are used to efficiently maintain solutions to problems where the input undergoes some changes.This thesis studies dynamic algorithms that maintain solutions to linear algebra problems and we explore their applications and implications for dynamic graphs and optimization problems.

Dynamic graph algorithms maintain properties of changing graphs, such as the distances in a graph that undergoes edge deletions and insertions.The main question is how to maintain the information without recomputing the solution from scratch whenever the graph changes.If maintaining the information without trivial recomputation is possible, the next natural question is how quickly the information can be maintained.This thesis makes progress on both questions:

(i) We construct the first non-trivial fully dynamic graph algorithms for single-source shortest paths, diameter and other problems. This answers open questions stated in, e.g., [Demetrescu-Italiano'04].

(ii) We obtain matching upper and conditional lower bounds for the complexity of maintaining reachability, maximum matching, directed cycle detection and many other graph properties. This settles the complexity for these problems and answers an open problem stated in [Abboud-V.Williams'14].

We get these results by reducing the dynamic graph problems to dynamic linear algebra problems for which we develop new algorithms. At the same time, conditional lower bounds for the dynamic graph problems thus imply lower bounds for dynamic linear algebra problems as well.

We apply the developed techniques for dynamic linear algebra to algorithms for linear programs and obtain optimal (i.e. nearly-linear time) algorithms for dense instances of linear programs, Markov decision processes, linear L1 regression, and graph specific special cases thereof such as bipartite matching, minimum-cost flow, and (negative weight) shortest paths.For bipartite matching on dense graphs, this is the first improvement since the classic algorithms by [Dinic'70;Hopcroft-Karp'71;Karzanov'73;Ibarra-Moran'81].

The results are obtained by using that algorithms (i.e. interior point methods) for these problems are iterative and must repeatedly solve linear systems and other linear algebra problems. By using techniques from dynamic linear algebra (i.e. dynamic matrix algorithms), we are able to maintain the solution to these subproblems, reducing the time required per iteration.The construction of our algorithms relies on a joint analysis of the iterative algorithm and the dynamic matrix algorithms.On one hand, we develop robust interior point methods which are able to handle relaxations and approximations to the linear algebra subroutines.On other hand, we develop fast dynamic matrix algorithms that are able to maintain the solution to these relaxed subproblems efficiently.

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on n-vertex m-edge graphs with integer polynomially-bounded costs and capacities we obtain a randomized method which solves the problem in O(m + n1.5) time. This improves upon the previous best runtime of O(m ?n) [Lee-Sidford'14] and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of m4/3 + o(1) [Liu-Sidford'20, Kathuria'20] and O(m ?n) [Lee-Sidford'14] for sufficiently dense graphs. In the case of ?1-regression in a matrix with n-columns and m-rows we obtain a randomized method which computes an ?-approximate solution in O(mn + n2.5) time. This yields a randomized method which computes an ?-optimal policy of a discounted Markov Decision Process with S states and, A actions per state in time O(S2 A + S2.5). These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were O(mn1.5) [Lee-Sidford'15] and O(S2.5 A) [Lee-Sidford'14, Sidford-Wang-Wu-Ye'18] respectively. To obtain this result we introduce two new algorithmic tools of possible independent interest. First, we design a new general interior point method for solving linear programs with two sided constraints which combines techniques from [Lee-Song-Zhang'19, Brand et al.'20] to obtain a robust stochastic method with iteration count nearly the square root of the smaller dimension. Second, to implement this method we provide dynamic data structures for efficiently maintaining approximations to variants of Lewis-weights, a fundamental importance measure for matrices which generalize leverage scores and effective resistances. 

The slow convergence rate and pathological curvature issues of first-order gradient methods for training deep neural networks, initiated an ongoing effort for developing faster second-order optimization algorithms beyond SGD, without compromising the generalization error. Despite their remarkable convergence rate (independent of the training batch size n), second-order algorithms incur a daunting slowdown in the cost per iteration (inverting the Hessian matrix of the loss function), which renders them impractical. Very recently, this computational overhead was mitigated by the works of [79, 23], yielding an O(mn2)-time second-order algorithm for training two-layer overparametrized neural networks of polynomial width m. We show how to speed up the algorithm of [23], achieving an Oe(mn)-time backpropagation algorithm for training (mildly overparametrized) ReLU networks, which is near-linear in the dimension (mn) of the full gradient (Jacobian) matrix. The centerpiece of our algorithm is to reformulate the Gauss-Newton iteration as an `2-regression problem, and then use a Fast-JL type dimension reduction to precondition the underlying Gram matrix in time independent of M, allowing to find a sufficiently good approximate solution via first-order conjugate gradient. Our result provides a proof-of-concept that advanced machinery from randomized linear algebra – which led to recent breakthroughs in convex optimization (ERM, LPs, Regression) – can be carried over to the realm of deep learning as well. 

Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form min(Ax=b,x >= 0) c inverted perpendicular x with n variables and d constraints, the generic case d = Omega (n) has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in (O) over tilde (n(omega) log(n/delta)) expected time(1), where 6 is the relative accuracy. This is essentially optimal as all known linear system solvers require up to O(n(omega)) time for solving Ax = b. However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old O(n(2.5) log(n/delta)) bound [FOCS'89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.'s (O) over tilde (n(omega) log(n/delta)) time algorithm. This allows for a strict (O) over tilde (n(omega) log(n/delta)) time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Song's PhD Thesis. The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain root UA inverted perpendicular (AU A inverted perpendicular)(-1) A root U upsilon in subquadratic time under l(2) multiplicative changes to the diagonal matrix U and the vector upsilon. This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC'89; Lee, Sidford FOCS'15; Cohen, Lee, Song STOC'19] required Omega(n(2)) time for this task. In [Cohen, Lee, Song STOC'19] they managed to maintain the matrix root UA inverted perpendicular (AU A inverted perpendicular)(-1) A root U in subquadratic time, but multiplying it with a dense vector to solve the linear system still required Omega(n(2)) time. To improve the complexity of their linear program solver, they restricted the solver to only multiply sparse vectors via a random sampling argument. In comparison, our data-structure maintains the entire product root UA inverted perpendicular (AU A inverted perpendicular)(-1) A root U upsilon additionally to just the matrix. Interestingly, this can be viewed as a simple modification of Cohen et al.'s data-structure, but it significantly simplifies their analysis of their central path method and makes their whole algorithm deterministic.

We present an tilde{O}(m+n{1.5})-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on m-edge, n-node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i.e. m= Omega(n{1.5}), our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic O(m sqrt{n})-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and widetilde{O}(n{omega})-time algorithms [Ibarra-Moran 1981] (where currently omega approx 2.373). On sparser graphs, i.e. when m=n{9/8+ delta} for any constant delta > 0, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an widetilde{O}(m{4/3+o(1)}) runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand et al.] and our new IPMs. Combining this general machinery yields a simpler widetilde{O}(n sqrt{m}) time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art widetilde{O}(m+n{1.5}) time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand et al.]).

In this paper we provide an (O) over tilde (nd + d(3)) time randomized algorithm for solving linear programs with d variables and n constraints with high probability. To obtain this result we provide a robust, primaldual (O) over tilde(root d)-iteration interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.

Consider the following distance query for an n-node graph G undergoing edge insertions and deletions: given two sets of nodes I and J, return the distances between every pair of nodes in I x J. This query is rather general and captures several versions of the dynamic shortest paths problem. In this paper, we develop an efficient (1 + epsilon)-approximation algorithm for this query using fast matrix multiplication. Our algorithm leads to answers for some open problems for Single-Source and All-Pairs Shortest Paths (SSSP and APSP), as well as for Diameter, Radius, and Eccentricities. Below are some highlights. Note that all our algorithms guarantee worst-case update time and are randomized (Monte Carlo), but do not need the oblivious adversary assumption. Subquadratic update time for SSSP, Diameter, Centralities, ect.: When we want to maintain distances from a single node explicitly (without queries), a fundamental question is to beat trivially calling Dijkstra's static algorithm after each update, taking Theta(n(2)) update time on dense graphs. A better time complexity was not known even with amortization. It was known to be improbable for exact algorithms and for combinatorial any-approximation algorithms to polynomially beat the Omega(n(2)) bound (under some conjectures) [Roditty, Zwick, ESA'04; Abboud, V. Williams, FOCS'14].(1) Our algorithm with I = {s} and J = V (G) implies a (1 + epsilon)-approximation algorithm for this, guaranteeing O(n(1.823)/epsilon(2)) worst-case update time for directed graphs with positive real weights in [1, W](2) With ideas from [Roditty, V. Williams, STOC'13], we also obtain the first subquadratic worst-case update time for (5/3 + epsilon)-approximating the eccentricities and (1.5 + epsilon)-approximating the diameter and radius for unweighted graphs (with small additive errors). We also obtain the first subquadratic worst-case update time for (1 + epsilon)-approximating the closeness centralities for undirected unweighted graphs. Worst-case update time for APSP: When we want to maintain distances between all-pairs of nodes explicitly, the (O) over tilde (n(2)) amortized update time by Demetrescu and Italiano [STOC'03] already matches the trivial Omega(n(2)) lower bound. A fundamental question is whether it can be made worst-case. The state-of-the-art algorithm takes (O) over tilde (n(2+2/3)) worst-case update time to maintain the distances exactly [Abraham, Chechik, Krinninger, SODA'17; Thorup STOC'05]. When it comes to (1+epsilon)-approximation, this bound is still higher than calling the O(n(omega)/epsilon)-time static algorithm of Zwick [FOCS'98], where omega approximate to 2.373. Our algorithm with I = J = V (G) implies nearly tight bounds for this, namely (O) over tilde (n(2)/epsilon(1+omega)) for undirected unweighted graphs and (O) over tilde (n(2.045)/epsilon(2)) for directed graphs with positive real weights. Besides this, we also obtain the first dynamic APSP algorithm with subquadratic update time and sublinear query time.