E-viri
Odprti dostop
-
Huck Bennett; Gajulapalli, Karthik; Golovnev, Alexander; Warton, Philip G
arXiv.org, 09/2023Paper, Journal Article
We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three \(n \times n\) matrices \(A\), \(B\), and \(C\) as input, to decide whether \(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 matrix multiplication time (i.e., in \(o(n^{\omega})\) time). To that end, we give two algorithms for MMV in the case where \(AB - C\) is sparse. Specifically, when \(AB - C\) has at most \(O(n^{\delta})\) non-zero entries 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)\)-time algorithm using \(\delta/2 \cdot \log_2 n + O(1)\) random bits. The former algorithm is faster than the deterministic algorithm of K\"{u}nnemann (ESA, 2018) when \(\delta \geq 1.056\), and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses \(\log_2 n + O(1)\) random bits (in turn fewer than Freivalds's algorithm). We additionally study the complexity of MMV. We first show that all algorithms in a natural class of deterministic linear algebraic algorithms for MMV (including ours) require \(\Omega(n^{\omega})\) time. We also show a barrier to 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 (with respect to deterministic \(\widetilde{O}(n^2)\)-time reductions).
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.