We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an ε-approximation to the Jordan Normal form of an integer matrix with a-bit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for ε-approximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational a-bit coefficients having a-bit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.

We survey recent progress on efficient algorithms for approximately diagonalizing a square complex matrix in the models of rational (variable precision) and finite (floating point) arithmetic. This question has been studied across several research communities for decades, but many mysteries remain. We present several open problems which we hope will be of broad interest.

We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure 1-o(1) and polynomial diameter. Both bounds rely on spectral gaps - of a certain Schrödinger operator in the first case, and a certain continuous time Markov chain in the second - which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.

We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded by O(n Δ7/5/log1/5−o(1)n) for any Δ, and improve this to O(nlog1/2d/log1/4−o(1)n) for simple d-regular graphs when d≥ log1/4n. In fact, the same bounds hold for the number of eigenvalues in any interval of width λ2/logΔ1−o(1)n containing the second eigenvalue λ2. The main ingredient in the proof is a polynomial (in k) lower bound on the typical support of a closed random walk of length 2k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.

We exhibit a randomized algorithm which given a square matrix A ∈ \mathbbCn×nwith ||A|| ≤ 1 and , computes with high probability an invertible V and diagonal D such that ||A-VDV-1|| ≤ δ in O(TMM(n)log2(n/δ)) arithmetic operations on a floating point machine with O(log4(n/δ)logn) bits of precision. The computed similarity V additionally satisfies ||V||||V-1|| ≤ O(n2.5/δ). Here TMM(n) is the number of arithmetic operations required to multiply two n×n complex matrices numerically stably, known to satisfy TMM(n)=O(nω+η) for every where ω is the exponent of matrix multiplication [1]. The algorithm is a variant of the spectral bisection algorithm in numerical linear algebra [2] with a crucial Gaussian perturbation preprocessing step. Our running time is optimal up to polylogarithmic factors, in the sense that verifying that a given similarity diagonalizes a matrix requires at least matrix multiplication time. It significantly improves the previously best known provable running times of O(n10/δ2) arithmetic operations for diagonalization of general matrices [3], and (with regards to the dependence on n) O(n3) arithmetic operations for Hermitian matrices [4], and is the first algorithm to achieve nearly matrix multiplication time for diagonalization in any model of computation (real arithmetic, rational arithmetic, or finite arithmetic). The proof rests on two new ingredients. (1) We show that adding a small complex Gaussian perturbation to any matrix splits its pseudospectrum into n small well-separated components. In particular, this implies that the eigenvalues of the perturbed matrix have a large minimum gap, a property of independent interest in random matrix theory. (2) We give a rigorous analysis of Roberts' [5] Newton iteration method for computing the sign function of a matrix in finite arithmetic, itself an open problem in numerical analysis since at least 1986 [6]. This is achieved by controlling the evolution of the pseudospectra of the iterates using a carefully chosen sequence of shrinking contour integrals in the complex plane.

We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on n vertices up to a 1 + ∊ error must use Ω(n log n/∊2) bits of space in the worst case, improving the Ω(n/∊2) bound of [ACK+16] and matching the best known upper bound achieved by spectral sparsifiers [BSS12]. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two d–regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.

Hyperbolic programming is a generalization of semidefinite programming in which one optimizes over linear sections of hyperbolicity cones rather than semidefinite ones. It is not known whether this generalization is strict: the Generalized Lax Conjecture asks whether every hyperbolicity cone is a section of a semidefinite cone of sufficiently high dimension. We study a quantitative version of this question, and prove that the space of hyperbolicity cones of hyperbolic polynomials of degree d in n variables contains (n/d)Ω(d) pairwise distant cones in the Hausdorff metric, implying that any semidefinite representation of such cones must have dimension at least (n/d)Ω(d) (even allowing a small approximation error). The cones are perturbations of the hyperbolicity cones of elementary symmetric polynomials. Our proof contains several ingredients of independent interest, including the identification of a large subspace in which the elementary symmetric polynomials lie in the relative interior of the set of hyperbolic polynomials, and a quantitative generalization of the fact that a real-rooted polynomial with two consecutive zero coefficients must have a high multiplicity root at zero.

We study the problem of approximating the largest root of a real-rooted polynomial of degree n using its top k coefficients and give nearly matching upper and lower bounds. We present algorithms with running time polynomial in k that use the top k coefficients to approximate the maximum root within a factor of n1/k and when k ≤ log n and k > log n respectively. We also prove corresponding information-theoretic lower bounds of nΩ(1/k) and , and show strong lower bounds for noisy version of the problem in which one is given access to approximate coefficients. This problem has applications in the context of the method of interlacing families of polynomials, which was used for proving the existence of Ramanujan graphs of all degrees, the solution of the Kadison-Singer problem, and bounding the integrality gap of the asymmetric traveling salesman problem. All of these involve computing the maximum root of certain real-rooted polynomials for which the top few coefficients are accessible in subexponential time. Our results yield an algorithm with the running time of for all of them.

We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is O(log2 n). This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is O(log2 n). This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.

We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if G is an n-node weighted undirected graph of average combinatorial degree d (that is, G has dn/2 edges) and girth g > 2d1/8 + 1, and if λ1 ≤ λ2 ≤ · · · λn are the eigenvalues of the (non-normalized) Laplacian of G, then (The Alon-Boppana theorem implies that if G is unweighted and d-regular, then if the diameter is at least d1.5.) Our result implies a lower bound for spectral sparsifiers. A graph H is a spectral є-sparsifier of a graph G if where L(G) is the Laplacian matrix of G and L(H) is the Laplacian matrix of H. Batson, Spielman and Srivastava proved that for every G there is an є-sparsifier H of average degree d where and the edges of H are a (weighted) subset of the edges of G. Batson, Spielman and Srivastava also show that the bound on є cannot be reduced below when G is a clique; our Alon-Boppana-type result implies that є cannot be reduced below when G comes from a family of expanders of super-constant degree and superconstant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an “online” setting. We show that for the online matrix setting the bound is tight, up to lower order terms.

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves upon the inequality in [Sutter, Berta and Tomamichel 17], as well as an adaptation of an argument for the scalar case due to [Healy 08]. Our new multi-matrix Golden-Thompson inequality could be of independent interest. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time.

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on an analysis of the expected characteristic polynomial of a union of random perfect matchings and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real-rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by √c-1+√d-1, for all c, d ≥ q 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials".

We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log2 n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which takes ~O(m+nF) time, we obtain a running time of ~O(m n1/3/ε2/3) for uncapacitated graphs, improving the previous best dependence on ε by a factor of O(1/ε3). Like the algorithm of Christiano, Kelner, Madry, Spielman and Teng, our algorithm reduces the problem to electrical flow computations which are carried out in linear time using fast Laplacian solvers. However, in contrast to previous work, our algorithm does not reweight the edges of the graph in any way, and instead uses local (i.e., non s-t) electrical flows to reroute the flow on congested edges. The algorithm is simple and may be viewed as trying to find a point at the intersection of two convex sets (the affine subspace of st-flows of value F and the l∞ ball) by an accelerated version of the method of alternating projections due to Nesterov.

We initiate a principled study of graph densification. Given a graph G the goal of graph densification is to come up with another graph H that has significantly more edges than G but nevertheless approximates G well with respect to some set of test functions. In this paper we focus on the case of cut and spectral approximations.

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1)\rceil$ edges such that for every $x\in\mathbb{R}^{V}$, $x^{T}L_{G}x\leq x^{T}L_{H}x\leq\bigl(\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}}\bigr)\cdot x^{T}L_{G}x$, where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.

We present a nearly linear time algorithm that produces high-quality spectral sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $\epsilon>0$, we produce a weighted subgraph $H=(V,\tilde{E},\tilde{w})$ of G such that $|\tilde{E}|=O(n\log n/\epsilon^2)$ and all $x\in\mathbb{R}^V$ satisfy $(1-\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}\leq\sum_{uv\in\tilde{E}}\,(x(u)-x(v))^2\tilde{w}_{uv}\leq(1+\epsilon)\sum_{uv\in E}\,(x(u)-x(v))^2w_{uv}$. This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had $O(n\log^{c}n)$ edges for some large constant c, and upon the cut sparsifiers of Benczúr and Karger, which only satisfied these inequalities for $x\in\{0,1\}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(\log n)$ time.

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every d > 1 and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,~{w}) with at most ⌈d(n-1)⌉ edges such that for every x ∈ RV, [xT LG x ≤ xT LH x ≤ ((d+1+2√d)/(d+1-2√d)) • xT LG x] where LG and LH are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G=(V,E,w) and a parameter ε>0, we produce a weighted subgraph H=(V,~E,~w) of G such that |~E|=O(n log n/ε2) and for all vectors x in RV. (1-ε) ∑uv ∈ E (x(u)-x(v))2wuv≤ ∑uv in ~E(x(u)-x(v))2~wuv ≤ (1+ε)∑uv ∈ E(x(u)-x(v))2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O(n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in {0,1}V. We conjecture the existence of sparsifiers with O(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. A key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in O(log n) time.