Information complexity of inner product and matrix multiplication clarified
Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion
Information TheoryComputational Complexity
Summary
This paper figures out how much information must be communicated to correctly compute inner products and matrix multiplications over finite fields when inputs come from random sources. They answer a long-standing question about how much this information depends on allowing some error. The authors use a new mathematical tool that connects uncertainty measured in two different ways, which works even for complicated groups. Their results precisely characterize the minimum communication needed for these problems, with very small error margins.
What this means in practice
- •For communication protocol designers: Design communication-efficient protocols by knowing the minimal information needed to compute matrix operations with bounded error.
- •For cryptography engineers: Use the entropy bounds to analyze security and efficiency in protocols involving matrix computations over finite fields.
A theory result. No direct application yet.
Authors
Xiaohong Cai, Mingyang Zhu
Abstract
We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.