We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system $Mx=b$ in sublinear time, with the goal of estimating $t^{\top}x^*$ for a given vector $t\in R^n$ and a specific solution $x^*$. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [AKP19] to the asymmetric case. Our first contributions are characterizations of the problem's mathematical structure. We express a solution $x^*$ via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of $M$, termed the maximum $p$-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of $M$ governs the problem's computational difficulty. For systems with bounded maximum $p$-norm gap, we develop a collection of algorithmic results for locally approximating $t^{\top}x^*$ under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum $p$-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.

Abstract. The classic Cheeger’s inequality relates the edge conductance [Formula: see text] of a graph and the second smallest eigenvalue [Formula: see text] of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality [Formula: see text] connecting the vertex expansion [Formula: see text] of a graph [Formula: see text] and the maximum reweighted second smallest eigenvalue [Formula: see text] of the Laplacian matrix. In this work, we first improve their result to [Formula: see text], where [Formula: see text] is the maximum degree in [Formula: see text], which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analogue in relating vertex expansions and reweighted eigenvalues. These include the following: (1) An analogue of Trevisan’s result that relates the bipartite vertex expansion [Formula: see text] of a graph and the maximum reweighted lower spectral gap [Formula: see text] of the adjacency matrix. This implies the first approximation algorithm for bipartite vertex expansion. (2) An analogue of higher-order Cheeger’s inequalities that relates the [Formula: see text]-way vertex expansion [Formula: see text] of a graph and the maximum reweighted [Formula: see text]th smallest eigenvalue [Formula: see text] of the Laplacian matrix. This implies the first approximation algorithm for [Formula: see text]-way vertex expansion. (3) An analogue of improved Cheeger’s inequality that relates the vertex expansion [Formula: see text] and the reweighted eigenvalues [Formula: see text] and [Formula: see text]. This provides an improved bound for [Formula: see text] using [Formula: see text], when the [Formula: see text]-way vertex expansion [Formula: see text] is large for a small [Formula: see text]. Finally, inspired by this connection, we present negative evidence to the [Formula: see text]-polytope edge expansion conjecture by Mihail and Vazirani. We construct [Formula: see text]-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these [Formula: see text]-polytopes is almost linear in the graph size. This does not provide a counterexample to the conjecture, but this is in contrast with known positive results which proved poly-logarithmic mixing time to the uniform distribution on the vertices of subclasses of [Formula: see text]-polytopes.

The classical Cheeger’s inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality connecting the vertex expansion of a graph and the maximum reweighted second smallest eigenvalue of the Laplacian matrix.In this work, we first improve their result to a logarithmic dependence on the maximum degree in the graph, which is optimal up to a constant factor. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. Building on this connection, we then develop a new spectral theory for vertex expansion. We discover that several interesting generalizations of Cheeger inequalities relating edge conductances and eigenvalues have a close analog in relating vertex expansions and reweighted eigenvalues. These include an analog of Trevisan’s result on bipartiteness, an analog of higher order Cheeger’s inequality, and an analog of improved Cheeger’s inequality. Finally, inspired by this connection, we present negative evidence to the 0/1-polytope edge expansion conjecture by Mihail and Vazirani. We construct 0/1-polytopes whose graphs have very poor vertex expansion. This implies that the fastest mixing time to the uniform distribution on the vertices of these 0/1-polytopes is almost linear in the graph size.

We prove a few concentration inequalities for the sum of n binary random variables under weaker conditions than k-wise independence. Namely, we consider two standard conditions that are satisfied in many applications: (a) direct product conditions (b) the XOR condition. Both conditions are weaker than mutual independence and both imply strong concentration bounds (similar to Chernoff-Hoeffding) on the tail probability of the sum of bounded random variables ([Impagliazzo and Kabanets, APPROX-RANDOM 10], [Unger, FOCS 09]). Our inequalities can be stated as the implication of threshold direct product theorems from either k-wise direct product conditions, or the k-wise XOR condition. By proving optimality of our inequalities, we show a clear separation for k « n between k-wise product conditions and XOR condition as well as a stark contrast between k-wise and n-wise product theorems. We use these bounds in the cryptographic application that provides provable security against algorithms with S-bit advice. Namely, we show how the problem reduces to proving S-wise direct product theorems or S-wise XOR lemmas for certain ranges of parameters. Finally, we derive a new S-wise XOR lemma, which yields a tight non-uniform bound for length increasing pseudorandom generators, resolving a 10-year-old open problem from [De, Trevisan, and Tulsiani, CRYPTO 10].

We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear convergence. This implies that a simple gradient descent algorithm also has linear convergence under the same assumption. The spectral gap condition for operator scaling is closely related to the notion of quantum expander studied in quantum information theory. The spectral analysis also provides bounds on some important quantities of the scaling problems, such as the condition number of the scaling solution and the capacity of the matrix and operator. These results can be used in various applications of scaling problems, including matrix scaling on expander graphs, permanent lower bounds on random matrices, the Paulsen problem on random frames, and Brascamp--Lieb constants on random operators. In some applications, the inputs of interest satisfy the spectral condition and we prove significantly stronger bounds than the worst case bounds.

The Paulsen problem is a basic open problem in operator theory: Given vectors u1, …, un ∈ ℝd that are є-nearly satisfying the Parseval’s condition and the equal norm condition, is it close to a set of vectors v1, …, vn ∈ ℝd that exactly satisfy the Parseval’s condition and the equal norm condition? Given u1, …, un, the squared distance (to the set of exact solutions) is defined as infv ∑i=1n || ui − vi ||22 where the infimum is over the set of exact solutions. Previous results show that the squared distance of any є-nearly solution is at most O(poly(d,n,є)) and there are є-nearly solutions with squared distance at least Ω(d є). The fundamental open question is whether the squared distance can be independent of the number of vectors n.

Analyzing the mixing time of random walks is a well- studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analysis of random walks and evolving sets using more combinatorial graph structures, and show some implications in approximating small-set expansion. On the other hand, we provide examples showing the limitations of using random walks and evolving sets in disproving the small-set expansion hypothesis. 1. We define a combinatorial analog of the spectral gap, and use it to prove the convergence of non- lazy random walks. A corollary is a tight lower bound on the small-set expansion of graph powers for any graph. 2. We prove that random walks converge faster when the robust vertex expansion of the graph is larger. This provides an improved analysis of the local graph partitioning algorithm using the evolving set process, and also derives an alternative proof of an improved Cheeger's inequality. 3. We give an example showing that the evolving set process fails to disprove the small-set expansion hypothesis. This refutes a conjecture of Oveis Gharan and shows the limitations of all existing local graph partitioning algorithms in approximating small-set expansion.

We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph $G$, $\lambda_2 = \Omega( \phi^V(G) \phi(G) )$, where $\phi^V(G)$ denotes the robust vertex expansion of $G$ and $\phi(G)$ denotes the edge expansion of $G$. The second generalization relates the second eigenvalue to the edge expansion and the expansion profile of $G$, for all $k \geq 2$, $ \lambda_2 = \Omega( \phi_k(G) \phi(G) / k )$, where $\phi_k(G)$ denotes the $k$-way expansion of $G$. These show that the spectral partitioning algorithm has better performance guarantees when $\phi^V(G)$ is large (e.g., planted random instances) or $\phi_k(G)$ is large (instances with few disjoint nonexpanding sets). Both bounds are tight up to a constant factor. Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.

We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G, where φV(G) denotes the robust vertex expansion of G and φ(G) denotes the edge expansion of G. The second generalization relates the second eigenvalue to the edge expansion and the expansion profile of G, for all k ≥ 2, where φk(G) denotes the k-way expansion of G. These show that the spectral partitioning algorithm has better performance guarantees when φV(G) is large (e.g. planted random instances) or φk(G) is large (instances with few disjoint non-expanding sets). Both bounds are tight up to a constant factor. Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors, and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.

Given a lazy regular graph G, we prove that the expansion of G^t is at least sqrt(t) times the expansion of G. This bound is tight and can be generalized to small set expansion. We show some applications of this result.

Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ1 ≤ λ2 ≤ ... ≤ λn ≤ 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k ≥ 2, [φ(G) = O(k) l2/√lk,] and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any $k$. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if lk is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.

We consider the problem of computing the rank of an m × n matrix A over a field. We present a randomized algorithm to find a set of r = rank( A ) linearly independent columns in Õ (| A | + r ω ) field operations, where | A | denotes the number of nonzero entries in A and ω < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with deterministic running time O ( mnr ω-2 ). Our algorithm is faster when r < max{ m , n }, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in Õ ( mn ) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in exact linear algebra, combinatorial optimization and dynamic data structure.

We consider the problem of computing the rank of an mxn matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in O(|A| + rw) field operations, where |A| denotes the number of nonzero entries in A and w < 2.38 is the matrix multiplication exponent. Previously the best known algorithm to find a set of r linearly independent columns is by Gaussian elimination, with running time O(mnrw). Our algorithm is faster when r < max{m,n}, for instance when the matrix is rectangular. We also consider the problem of computing the rank of a matrix dynamically, supporting the operations of rank one updates and additions and deletions of rows and columns. We present an algorithm that updates the rank in O(mn) field operations. We show that these algorithms can be used to obtain faster algorithms for various problems in numerical linear algebra, combinatorial optimization and dynamic data structure.