More Like this

1. Matrix Multiplication and Number On the Forehead Communication

   https://doi.org/10.4230/LIPIcs.CCC.2023.16  

   Alman, Josh; Błasiok, Jarosław (July 2023, 38th Computational Complexity Conference (CCC 2023))

   Ta-Shma, Amnon (Ed.)

   Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly on the other two players' heads, and promised that they are consistent with the inputs of the other players. The set of all allowed inputs under this promise may be thought of as an order-3 tensor. We surprisingly observe that this tensor is exactly the matrix multiplication tensor, which is widely studied in the design of fast matrix multiplication algorithms. Using this connection, we prove a number of results about both Number On the Forehead communication and matrix multiplication, each by using known results or techniques about the other. For example, we show how the Laser method, a key technique used to design the best matrix multiplication algorithms, can also be used to design communication protocols for a variety of problems. We also show how known lower bounds for Number On the Forehead communication can be used to bound properties of the matrix multiplication tensor such as its zeroing out subrank. Finally, we substantially generalize known methods based on slice-rank for studying communication, and show how they directly relate to the matrix multiplication exponent ω. 

   more » « less
2. Ramsey numbers and the Zarankiewicz problem

   https://doi.org/10.1112/blms.13040  

   Conlon, David; Mattheus, Sam; Mubayi, Dhruv; Verstraëte, Jacques (April 2024, Bulletin of the London Mathematical Society)

   Abstract Building on recent work of Mattheus and Verstraëte, we establish a general connection between Ramsey numbers of the form for a fixed graph and a variant of the Zarankiewicz problem asking for the maximum number of 1s in an by ‐matrix that does not have any matrix from a fixed finite family derived from as a submatrix. As an application, we give new lower bounds for the Ramsey numbers and , namely, and . We also show how the truth of a plausible conjecture about Zarankiewicz numbers would allow an approximate determination of for any fixed integer . 

   more » « less
3. A Jensen inequality for partial traces and applications to partially semiclassical limits

   https://doi.org/10.1007/s11005-025-01938-9  

   Carlen, Eric_A; Frank, Rupert_L; Larson, Simon (May 2025, Letters in Mathematical Physics)

   Abstract We prove a matrix inequality for convex functions of a Hermitian matrix on a bipartite space. As an application, we reprove and extend some theorems about eigenvalue asymptotics of Schrödinger operators with homogeneous potentials. The case of main interest is where the Weyl expression is infinite and a partially semiclassical limit occurs. 

   more » « less
4. Rank of the vertex-edge incidence matrix of $$r$$-out hypergraphs

   https://doi.org/10.1137/21M1467572  

   Cooper, C; Frieze, A. (January 2022, SIAM journal on discrete mathematics)

   We consider the rank of a class of sparse Boolean matrices of size $$n \times n$$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about $0.2574$ for large $$n$$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation, can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $$k$$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $$n$$, \cite{ACO}, \cite{CFP}. For fields of higher order, the co-rank is typically Poisson distributed. 

   more » « less
5. Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

   https://doi.org/10.1109/FOCS.2017.90  

   Durfee, David; Peebles, John; Peng, Richard; Rao, Anup B. (November 2017, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017)

   We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $$n^{1.5}$$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $$(1 \pm \delta)$$ approximation to the determinant of any SDDM matrix with constant probability in about $$n^2 \delta^{-2}$$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $$n^2 \delta^{-2}$$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $$\delta$$ from the $$w$$-uniform distribution . 

   more » « less