We study matrix inversion and solving linear systems on diagonally dominant matrices. These are associated with random walk quantities such as hitting times and escape probabilities in graphs. Such quantities can be exponentially small, even on undirected unit-weighted graphs. However, their nonnegativity suggests that they can be approximated entrywise, leading to a stronger notion of approximation than vector norm–based error.

We present a randomized linear-space solver for general linear systems \(\textbf A\text x=\textbf b\) with \(\textbf A \in \mathbb{Z}^{n \times n}\) and \(\textbf b \in \mathbb{Z}^n\), without any assumption on the condition number of \(\textbf A\). For matrices whose entries are bounded by \(\mathrm{poly}(n)\), the solver returns a \((1+\epsilon)\)-multiplicative entry-wise approximation to vector \(\text x \in \mathbb{Q}^n\) using \(\tilde O(n^2 \cdot \mathrm{nnz}(\textbf A))\) bit operations and \(O(n \log n)\) bits of working space (i.e., linear in the size of a vector), where \(\mathrm{nnz}\) denotes the number of nonzero entries. Our solver works for right-hand vector \(\textbf b\) with entries up to \(n^{O(n)}\). To our knowledge, this is the first linear-space linear system solver over the rationals that runs in \(\tilde O(n^2 \cdot \mathrm{nnz}(\textbf A))\) time. We also present several applications of our solver to numerical linear algebra problems, for which we provide algorithms with efficient polynomial running time and near-linear space. In particular, we present results for linear regression, linear programming, eigenvalues and eigenvectors, and Singular Value Decomposition.

We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, L and a nonnegative vector b, computes an entrywise approximation to the solution of L x = b in Õ(m no(1)) time with high probability, where m is the number of nonzero entries and n is the dimension of the system.

We study the cost of parallelizing weak-to-strong boosting algorithms for learning, following the recent work of Karbasi and Larsen. Our main results are two-fold:•First, we prove a tight lower bound, showing that even “slight” parallelization of boosting requires an exponential blow-up in the complexity of training.Specifically, let γ be the weak learner's advantage over random guessing. The famous AdaBoost algorithm produces an accurate hypothesis by interacting with the weak learner for Õ(1/γ2)1 rounds where each round runs in polynomial time.Karbasi and Larsen showed that “significant” parallelization must incur exponential blow-up: Any boosting algorithm either interacts with the weak learner for Ω(1/γ) rounds or incurs an exp(d/γ) blow-up in the complexity of training, where d is the VC dimension of the hypothesis class. We close the gap by showing that any boosting algorithm either has Ω(1/γ2) rounds of interaction or incurs a smaller exponential blow-up of exp(d).•Complementing our lower bound, we show that there exists a boosting algorithm using Õ(1/(tγ2)) rounds, and only suffer a blow-up of exp(d · t2).Plugging in t = ω(1), this shows that the smaller blow-up in our lower bound is tight. More interestingly, this provides the first trade-off between the parallelism and the total work required for boosting.

Log-structured merge-trees (LSM-trees) are widely used in key-value stores because of its excellent write performance. To reduce LSM-tree's read amplification due to overlapping sorted runs, each file (i.e., SSTable) in an LSM-tree is typically associated with a point or range filter to reduce unnecessary I/Os to the runs that do not contain the target key (range). However, as modern SSDs get faster, probing multiple in-memory filters per query often makes the system CPU bottlenecked, thus compromising the system's throughput. In this paper, we developed the Global Range Filter (GRF) for RocksDB that reduces the number of filter probes per query to one. We follow the pioneering Chucky's approach by storing the sorted run IDs within the filter. However, we identify two practical challenges in building a global range filter: correctness in multi-version concurrency control and efficiency in frequent updates. We solve both challenges by the novel Shape Encoding algorithm. With further optimizations, GRF achieves a dominating performance over the state-of-the-art filters under different workloads when integrated into RocksDB.

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS’16, JACM’19]. A line of work that followed extended this result to a large class of learning problems. Until recently, all these results considered learning in the streaming model, where each sample is drawn independently, and the learner is allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC’19] considered a stronger model, allowing multiple passes over the stream. In the 2-pass model, they showed that learning parities of size n requires either a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples. (Their result also generalizes to other learning problems.) In this work, for any constant q, we prove tight memory-sample lower bounds for any parity learning algorithm that makes q passes over the stream of samples. We show that such a learner requires either $\Omega\left(n^{2}\right)$ memory size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower bound, this is the first nontrivial lower bound for q-pass learning for any $q \geq 3$. Similar to prior work, our results extend to any learning problem with many nearly-orthogonal concepts.We complement the lower bound with an upper bound, showing that parity learning with q passes can be done efficiently with $O\left(n^{2} / \log q\right)$ memory.