CS Paper Radar

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion

Xiaohong Cai, Mingyang Zhu

cs.IT cs.CC ·submitted 2026-11-02 07:36 UTC · v1
theoryhot direction

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.

Comment
38 pages, including appendices

Closest papers

Nearest neighbours by meaning across the whole index.

A note on exact external information complexity

cs.CC ·2026-11-08 ·Henning Wunderlich
similarity 0.67
Abstract

We study the prior-free zero-error private-coin external information complexity $B(f)$ of finite two-party functions, with correctness on every input. An elementary rectangle/entropy argument gives $B(\mathsf{AND})=\log_2 3$. A complete classification of Boolean $3\times3$ matrices leaves, up to input permutations and output complementation, only the two-overlapping-rectangles function $F$ without an exact value. An entropy potential and a finite rational protocol give $2.1212661667060486842\ldots\le B(F)<2.130998318$. We also determine its deterministic external information and zero-error communication costs. A separate product-prior certificate and internal-information additivity yield $R_0^{\mathrm{pub}}(F^{\times t})\ge2.021991187178562\ldots\,t$, strictly exceeding the fractional-cover rate $2t$.

0.30

Strongly Refuting Semirandom Linear Systems in Subexponential Time

cs.DS ·2026-09-24 ·Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
theory similarity 0.65
Abstract

In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+ε$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + γ}$ equations, for a small constant $γ$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$Ω(n)$ sum-of-squares lower bound, showing that ''[BKW03]-style'' algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.

0.35

Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields

cs.CR ·2026-11-03 ·Mark Braverman, Aayush Jain, Stephen Newman
hot direction similarity 0.64
Abstract

\emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.

0.35

Unbounded Holevo additivity gaps in finite dimensions

cs.IT quant-phmath-ph ·2026-09-16 ·Jinzhao Wang
code/data similarity 0.64
Abstract · 22+8pp; v2:added a short discussion of concurrent works; corrected estimates in Appendix B; added a Lean certificate: https://github.com/JWa…

We establish unbounded two-use Holevo additivity gaps in finite dimensions. For each sufficiently large fixed integer $K$ and all sufficiently large $n$, we construct channels $T_n$ with output dimension $K^n$, input dimension $\exp(Θ_K(n^2))$, and \[ χ(T_n^{\otimes2})-2χ(T_n) \ge n\left[\frac{\log_2K}{K}-2\log_2(1+9/K)\right]-O(1/n). \] The gap is linear in output qubits, with an explicit quadratic input-qubit cost and an explicit threshold on $n$. We also obtain channels whose single-use Holevo quantity tends to zero while their two-use Holevo information, and hence classical capacity, diverges. The channels arise from structured tensor products of the complementary mixed-unitary channels used in Collins's free-probabilistic proof. We establish minimum-output-entropy gaps by combining Collins--Youn's product-group Haagerup inequality with Bordenave--Collins's quantitative strong-convergence estimates. We also provide a Lean certificate for our proofs.

0.52

Optimal Deterministic Fully Sparse Matrix Multiplication

cs.DS ·2026-08-19 ·Omar Graia
similarity 0.63
Abstract

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\operatorname{nnz}(A),\operatorname{nnz}(B)=O(n^{δ_{\mathrm{in}}})$ and $\operatorname{nnz}(AB)=O(n^{δ_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\!\left(n^{β_R(δ_{\mathrm{in}},\min\{δ_{\mathrm{out}},2δ_{\mathrm{in}}\})+\varepsilon}\right)$$ operations, where $β_R(δ_{\mathrm{in}},δ)$ denotes the maximum of $δ_{\mathrm{in}}$ and $ω_{δ_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in[0,1]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω_R((δ_{\mathrm{out}}-1)_+,1,1)+\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\varepsilon})$, for every $δ_\mathrm{out}\le1.321334$, improving the previous deterministic range of $δ_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

0.30

Approximate Hamming Convolution via Rectangular Matrix Multiplication

cs.DS ·2026-11-05 ·Przemyslaw Uznanski
similarity 0.62
Abstract

We study $(1 \pm ε)$-approximate text-to-pattern Hamming distance: given a length-$N$ pattern and a length-$2N$ text, compute the Hamming distance at every alignment to relative error $ε$. For every fixed $a \ge 0$ and $ε= N^{-a}$, we give a randomized algorithm with simultaneous high-probability correctness on a logarithmic-word RAM and expected running time $\widetilde{O}(N^{ω(4a)/2})$, where $\widetilde{O}$ suppresses subpolynomial factors and $ω(k)$ is the exponent for multiplying an $n \times n^k$ matrix by an $n^k \times n$ matrix. With a recent rectangular bound, this improves the published bounds [CGK+20, FKN26] for $1/12 < a < (3 + \sqrt{3})/16$. In particular, the algorithm runs in expected time $\widetilde{O}(N)$ for $0 \le a \le 1/8$, extending the previous near-linear guarantee through $a = 1/12$.

0.25

Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model

cs.DC cs.DS ·2026-11-11 ·Chetan Gupta, Jukka Suomela, Hossein Vahidi
theory similarity 0.62
Abstract · Lean formalization available at https://doi.org/10.5281/zenodo.24127514

We study sparse matrix multiplication in the low-bandwidth model: $n$ computers multiply two $n\times n$ matrices, and each computer can send and receive one $O(\log n)$-bit message per round. The input matrices are uniformly sparse, meaning that there are at most $d$ nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an $O(d^{1.907})$-round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to $O(d^{1.832})$ rounds. In this work, we give a deterministic algorithm that solves this problem in $O(d^{3/2})$ rounds in the supported setting, improving the previous bounds over fields and semirings.

0.14

Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies

cs.IT quant-ph ·2026-08-18 ·Kean Chen, Qisheng Wang
similarity 0.61
Abstract · 32 pages, 1 table, 4 algorithms

In this paper, we provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity. Specifically, for order $α$, dimension $d$, and additive error $\varepsilon$, 1. For $0 < α< 1$, the sample complexity is $O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})$ for Rényi entropy and $O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)$ for Tsallis entropy. In particular, for $0 < α\leq 1/2$, the sample complexity for both entropies is $O(d^{1+1/α}/\varepsilon^{1/α})$. 2. For non-integer $α> 1$, the sample complexity is $O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)$ for Rényi entropy. Our upper bounds improve the quantum Rényi entropy estimators due to Acharya, Issa, Shende, and Wagner (2017) and the quantum Tsallis entropy estimators due to Chen, Liu, and Wang (2026), and match the lower bounds recently established by Wang (2026).

0.51