Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University

Daniel Kressner surveys randomized algorithms for joint eigenvalue problems: finding common eigenvectors and their eigenvalues across a family of matrices. The talk covers algorithm development and analysis, with examples from signal processing and multivariate root finding. Joint work with Haoze He and Bor Plestenjak.

Joel Tropp studies structured dimension reduction through the injectivity of random maps, motivated by fast low-rank approximation and least-squares regression. This viewpoint sharpens guarantees for sparse maps and gives exponential improvements for tensor-product dimension reduction. Experiments assess the resulting structured random matrices on synthetic problems and scientific applications. Joint work with Chris Camaño, Ethan Epperly, and Raphael Meyer, available as arXiv:2508.21189.

Sherry Xiaoye Li surveys randomized construction of hierarchically low-rank matrices, including H/H2, HODLR, HSS, and butterfly formats with different off-diagonal structures. Applications include integral equations, boundary elements, discretized PDEs, and statistical or machine-learning kernel matrices, using either iterative matrix-vector products or direct factorization and solves. Constructing these representations from an implicit dense operator is often the main cost. The talk offers a unified view of sketch distributions, sketch sizes, approximation error bounds, high-performance implementation, applications, and open questions.

Alberto Bucci develops single-pass randomized and streaming low-rank approximation, beginning with large matrices and the strengths and limitations of streaming algorithms. The discussion extends to Tucker, tensor-train, and tree tensor-network representations. Tensor-train approximations are then incorporated into Krylov solvers, including sketched GMRES, to reduce expensive intermediate contractions. The framework is presented as applicable beyond tensor trains to other tensor-network architectures.

Daniel Szyld analyzes rand-cholQR, a randomized method for tall-and-skinny QR factorization using one or two sketch matrices. For numerically full-rank inputs, its orthogonality error is bounded with high probability at the scale of unit roundoff. NVIDIA A100 experiments compare multisketching with CholeskyQR2, reporting comparable or better speed and stronger stability with little additional memory or computation. Joint work with Andrew Higgins, Erik Boman, and Ichitaro Yamazaki.

Per-Gunnar Martinsson presents randomized black-box algorithms that compress rank-structured matrices, including H-matrices and HSS matrices, into data-sparse representations. Access is through matrix-vector products, which suits Schur-complement construction and matrix multiplication. When both the operator and its transpose admit O(N) application, the overall compression can also have linear complexity. A featured method combines compression and factorization of an H-matrix under strong admissibility.

Yuji Nakatsukasa explains how CUR decompositions approximate a matrix using selected columns and rows, without inspecting every entry once the indices are chosen. Near-optimal CUR approximations exist relative to the truncated singular value decomposition, and efficient algorithms make them useful for large problems. The talk covers computation and theoretical guarantees before exploring applications to approximation theory, model reduction, and parameter-dependent problems.

Ilse Ipsen examines full-column-rank least-squares systems solved through normal equations with symmetric or nonsymmetric randomized preconditioning computed at lower arithmetic precision. Effective preconditioning can deliver accuracy close to QR-based MATLAB backslash even for badly conditioned matrices. The analysis separates the solution's accuracy from the accuracy of the preconditioner: the original least-squares residual controls the error. The talk develops realistic relative-error perturbation bounds. Joint work with James Garrison.

Ryann Cartor introduces multivariate public-key cryptography, whose fast and compact post-quantum schemes use polynomial systems over finite fields. The tutorial surveys past and current multivariate cryptosystems before examining MinRank as a central cryptanalytic problem. MinRank attacks have broken prominent schemes in both multivariate and code-based cryptography. The material assumes basic algebra and connects these foundations to current research directions.

Eimear Byrne introduces q-matroids and rank-metric codes as vector-space analogues of classical matroids and Hamming-metric codes. The tutorial compares the connections between codes and matroids with those between rank-metric codes and q-matroids. It develops equivalent definitions of q-matroids, relates them to classical definitions, and explains how q-matroid invariants provide invariants for rank-metric codes.

Alexander Barg explores research questions inspired by Reed–Muller codes. The first concerns storage codes on triangle-free graphs, where neighboring vertices determine parity checks. Certain graphs admit codes approaching the maximum size of 2^n; whether Reed–Muller codes yield similar constructions remains open. The second extends the construction of Reed–Muller codes from cosets in an elementary abelian group to Coxeter groups, including permutation groups. Questions include analogues of the |u|u+v| construction and modern decoders, whether these codes share Reed–Muller codes' capacity achievement on the binary erasure channel, and a conjectured minimum-distance formula.

Felice Manganiello introduces network coding, in which intermediate nodes combine incoming packets algebraically before forwarding them. This can improve communication efficiency, latency, and resilience to packet loss and congestion. The tutorial develops theoretical foundations and practical applications, including linear network coding, multicast communication, and coding across networks.

Alex Gittens studies how many data points must be labelled to fit a linear regression model with nearly the predictive power of a fully labelled dataset. Existing coreset and iterative approaches handle constant-factor approximations, but tighter approximations that improve with dataset size need different methods. The talk presents a polynomial-time algorithm that reduces label complexity by an additive O(sqrt(n)), using a sharp analysis of regression error for a coreset formed by backward selection.