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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by studying the power of randomness, certifying algorithms andbarriers for fine-grained reductions, we investigate the question whether themultiplication of two $n\times n$ matrices can be performed in near-optimalnondeterministic time $\tilde{O}(n^2)$. Since a classic algorithm due toFreivalds verifies correctness of matrix products probabilistically in time$O(n^2)$, our question is a relaxation of the open problem of derandomizingFreivalds' algorithm.  We discuss consequences of a positive or negative resolution of this problemand provide potential avenues towards resolving it. Particularly, we show thatsufficiently fast deterministic verifiers for 3SUM or univariate polynomialidentity testing yield faster deterministic verifiers for matrixmultiplication. Furthermore, we present the partial algorithmic progress thatdistinguishing whether an integer matrix product is correct or contains between1 and $n$ erroneous entries can be performed in time $\tilde{O}(n^2)$ --interestingly, the difficult case of deterministic matrix product verificationis not a problem of "finding a needle in the haystack", but rather cancellationeffects in the presence of many errors.  Our main technical contribution is a deterministic algorithm that corrects aninteger matrix product containing at most $t$ errors in time$\tilde{O}(\sqrt{t} n^2 + t^2)$. To obtain this result, we show how to computean integer matrix product with at most $t$ nonzeroes in the same running time.This improves upon known deterministic output-sensitive integer matrixmultiplication algorithms for $t = \Omega(n^{2/3})$ nonzeroes, which is ofindependent interest.

On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress