English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the Matrix Multiplication Verification Problem (MMV) where the goalis, given three $n \times n$ matrices $A$, $B$, and $C$ as input, to decidewhether $AB = C$. A classic randomized algorithm by Freivalds (MFCS, 1979)solves MMV in $\widetilde{O}(n^2)$ time, and a longstanding challenge is to(partially) derandomize it while still running in faster than matrixmultiplication time (i.e., in $o(n^{\omega})$ time).  To that end, we give two algorithms for MMV in the case where $AB - C$ issparse. Specifically, when $AB - C$ has at most $O(n^{\delta})$ non-zeroentries for a constant $0 \leq \delta < 2$, we give (1) a deterministic$O(n^{\omega - \varepsilon})$-time algorithm for constant $\varepsilon =\varepsilon(\delta) > 0$, and (2) a randomized $\widetilde{O}(n^2)$-timealgorithm using $\delta/2 \cdot \log_2 n + O(1)$ random bits. The formeralgorithm is faster than the deterministic algorithm of K\"{u}nnemann (ESA,2018) when $\delta \geq 1.056$, and the latter algorithm uses fewer random bitsthan the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the sametime and uses $\log_2 n + O(1)$ random bits (in turn fewer than Freivalds'salgorithm).  We additionally study the complexity of MMV. We first show that allalgorithms in a natural class of deterministic linear algebraic algorithms forMMV (including ours) require $\Omega(n^{\omega})$ time. We also show a barrierto proving a super-quadratic running time lower bound for matrix multiplication(and hence MMV) under the Strong Exponential Time Hypothesis (SETH). Finally,we study relationships between natural variants and special cases of MMV (withrespect to deterministic $\widetilde{O}(n^2)$-time reductions).

Matrix Multiplication Verification Using Coding Theory