5 papers
Improved Sparse Recovery for Approximate Matrix Multiplication
Yahel Uffenheimer, Omri Weinstein
We present a simple randomized algorithm for approximate matrix multiplication (AMM) whose error scales with the *output* norm . Given any matrices and…
Proofs of Useful Work from Arbitrary Matrix Multiplication
Ilan Komargodski, Omri Weinstein
We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task (as opposed to artificial random h…
(Approximate) Matrix Multiplication via Convolutions
Yahel Uffenheimer, Omri Weinstein
We study the capability of the Fast Fourier Transform (FFT) to accelerate exact and approximate matrix multiplication without using Strassen-like divide-and-conquer. We present a s…
Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
Nir Ailon, Akhiad Bercovich, Yahel Uffenheimer +1
Modern AI relies on huge matrix multiplications (MatMuls), whose computation poses a scalability problem for inference and training. We propose an alternative, GPU native bilinear…
Proof of Work With External Utilities
Yogev Bar-On, Ilan Komargodski, Omri Weinstein
Proof-of-Work (PoW) consensus is traditionally analyzed under the assumption that all miners incur similar costs per unit of computational effort. In reality, costs vary due to fac…