Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion
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 𝔽2m and error at most ε∈[0,1/2], the information complexity with output at Bob lies between (1−2ε)m−c0 and (1−2ε)m, where c0<4.772 is a universal constant. For independent uniform matrices X∈𝔽qt× m and Y∈𝔽qs× m, where t≤ s, computing XYT with output at Bob and error at most ε∈[0,1] has information complexity (1−qtsε/(qts−1))+mtlog2q, 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 mtlog2q. 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 Q1,…,Qk 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≥⌈⌊log2s⌋ln2⌉, then the min-entropy of their ordered product is at least the average Shannon entropy of the Qi minus c0 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.
Related
- The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
- Defining the Crick-Franklin-Watson genes of any robot (equals a finite state machine) and defining the Shannon genetic code attached to each gene. We also define the Krohn-Rhodes complexity of any regular maximal prefix code
- Product-Aware Deterministic Rounding for Quantized Matrix Multiplication
- Borel complexity for product of trees and commuting partial maps
- Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
BibTeX
@misc{cai2026information,
title = {{Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion}},
author = {Xiaohong Cai and Mingyang Zhu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02684},
eprint = {2611.02684},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02684},
}
RIS
TY - UNPB
TI - Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion
AU - Xiaohong Cai
AU - Mingyang Zhu
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02684
UR - https://arxiv.org/abs/2611.02684
AB - 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 𝔽_2^m and error at most ε∈[0,1/2], the information complexity with output at Bob lies between (1−2ε)m−c_0 and (1−2ε)m, where c_0<4.772 is a universal constant. For independent uniform matrices X∈𝔽_q^t× m and Y∈𝔽_q^s× m, where t≤ s, computing XY^T with output at Bob and error at most ε∈[0,1] has information complexity (1−q^tsε/(q^ts−1))^+mtlog_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 mtlog_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,…,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≥⌈⌊log_2s⌋ln2⌉, 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.
ER -