Probabilistic Machines Can Use Less Running Time

By R. Freivalds. 1977

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (2018, methodology): “018). The main observation that guides our approach is that matrix multiplication—the main bottleneck in DNNs— admits a concretely efﬁcient veriﬁable outsourcing scheme known as Freivalds’ algorithm (Freivalds, 1977), which can also be turned private in our setting. Our TEE selectively outsources th”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “En route we also use embeddings to estimate the Frobenius norm of implicitly formed matrices akin to Freivalds’ technique [34] (Lemma 8).”
Randomized algorithms (1995, unknown): “The technique for verifying matrix and univariate polynomial multiplication is due to Freivalds [157].”
The NP-Completeness Column: An Ongoing Guide (1982, unknown): “These can be found in such fields as automata theory [14], VLSI design [27], data structure manipulation [11], and distributed computing [20,27,33,52].”
Subcubic Equivalences between Path, Matrix and Triangle Problems (2010, background): “The above relationship between matrix product and its verification is particularly surprising, as n × n matrix product verification over rings can be done inO (n2) randomized time [11, 31], but it is not known whether ring matrix multiplication can be efficiently reduced to this fast verification.”