Rafael Pass

Prof@Tel-Aviv University
Prof@Cornell Tech

[Rafael Pass @PassRafael]

@prlnet thanks! comments very welcome! there are lots of exciting open problems!!!

[Pearl Research Labs @prlnet]

A common critique on Proof-of-Useful-Work is that the zero marginal cost of mining drives the network’s security budget and price to zero.
A paper just released by Rafael Pass, a renowned cryptographer at @Cornell /@TechnionLive and research scientist at Pearl Research Labs proves why this argument is flawed.
By analyzing the equilibrium dynamics of PoUW, it shows not only that Pearl’s security budget (and hence price) are at least as high as Bitcoin, but in fact that Pearl will increase the SIZE of the global AI inference market, via Jevons Paradox.
https://t.co/hxRGlC3AI2
@initc3org

[Ittai Abraham @ittaia]

Decentralized thoughts chapter on things Simplex BFT - you may want to bookmark it :-)

https://t.co/0mhgd4kniO

[Omri Weinstein @WeinsteinOmri]

Will Fast Matrix Multiplication ever be practical?

Strassen’s 1986 discovery of fast matrix multiplication (FMM) – asserting that the product of two 𝑛×𝑛 matrices can be computed in sub-cubic time 𝑛^𝜔 ∼ 𝑛²·⁸⁷ ≪ 𝑛³ – had a profound impact on theoretical computer science and algorithm design.

Since then, mathematicians improved on Strassen’s algorithm, and some experts believe that, eventually, it will be shown that 𝜔 ≈ 2, which would mean that the time to compute AxB is essentially the time it takes to merely read the inputs: ~O(𝑛²) (!) Needless to say, such result would have a major impact on the AI compute age we’re entering…

Unfortunately, FMM algorithms only work for enormous matrices--on the order of the number of atoms in the universe (“galactic algorithms" [1])--and it is currently hard to imagine them being practical on any imaginable hardware. Besides their asymptotic runtime, a core practical issue with FMM algorithms is that they all inherently rely on recursive divide-and-conquer, which creates memory and IO-bottlenecks, and is numerically unstable; This is likely the reason why the largest hardware manufacturers in the world are not developing chips for FMM. Even Strassen’s original algorithm, which gives nontrivial FLOP speedup for relatively small matrices, struggles to beat the sheer parallelism of naiive MatMul on GPUs or TPUs.

Some interesting progress on practical FMM seems underway [2] and would be interesting to follow, but it remains to be seen whether divide-and-conquer can be implemented in both silicon and memory to deliver wall-clock speedups for realistic dimensions of matrices in LLMs.

What is means for @prlnet. That’s the reason we designed the Pearl proof-of-work protocol (cuPOW) with the underlying baseline being “naiive” matrix multiplication O(𝑛³), which is what NVIDIA, AMD, Cerebras and all other AI hardware accelerators implement today.

Nevertheless, it is important to stress that Pearl’s protocol doesn't rely on naiive MatMul remaining SoTA -- if FMM becomes practical some day, Pearl's protocol can easily adapt to the 𝑛^𝜔 baseline (since the next version of cuPoW will only verify the output AB).

In fact, one of the intriguing aspect of @prlnet is that it creates incentives (for both humans and machines) to develop faster MatMul algorithms and hardware (as had happened in Bitcoin with SHA256). Of course, without proper modification, such breakthrough would break the security assumption of Pearl-GEMM, so such algorithmic breakthrough would better be public.

FMM and FFT. Our recent paper [3] shows that it is possible to achieve fast matrix multiplication without using Strassen-like divide-and-conquer, using only the Fast Fourier Transform, which is omnipresent in countless industry-scale applications. This paper presents a simple algorithm running in 𝑂(𝑛²·⁸⁹) time, which only sums a few convolutions in 𝕫ₖᵐ, using FFT (see figure below for illustration of the algorithm).

Despite being highly parallel (no recursion), this FFT algorithm for MatMul remains asymptotic, as it still requires many parallel repetitions on submatrices in order to obtain noticeable speedup over naiive MatMul (𝑛³). Whether FFT can lead to subcubic time MatMul
for reasonably-sized matrices is a fascinating question!
I believe FFTs are the most promising tool in this direction...

[1] Lipton, Richard J., and Kenneth W. Regan. “David Johnson: Galactic Algorithms.” In People, Problems, and Proofs, 109–112. Springer, 2013. https://t.co/X6N6ViYYai.

[2] Karstadt, Elaye, and Oded Schwartz. “Matrix Multiplication, a Little Faster.” Journal of the ACM 67, no. 1 (2020): 1:1–1:31. https://t.co/VnfiWVLdKK.

[3] Uffenheimer, Yahel, and Omri Weinstein. “Improved Sparse Recovery for Approximate Matrix Multiplication.” arXiv:2602.04386, 2026..

[Ittai Abraham @ittaia]

Decentralized thoughts with @jneu_net on Chained Simplex🔥

https://t.co/aGMHGNl4q0

Many people asked why we focus so much on single shot Simplex posts, arguing that the real challenge is the chained multi shot setting

We argue almost the opposite. The single shot setting isolates the core consensus properties. Once those are understood cleanly, extending them into a chained construction becomes surprisingly simple

[Ittai Abraham @ittaia]

Decentralized thoughts on **Fixed View Schedule** protocols:

1. Why fixed view schedule: https://t.co/XfCTKiMqx1

2. Simplex on a fixed view schedule: https://t.co/5uQzc1wNPu

3. Fast Simplex on a fixed view schedule: https://t.co/A1cDkcN3cr

[Dionysis Zindros @dionyziz]

Today, I taught a delightfully simplex liveness proof in class ("Blockchain Foundations" graduate course at @ntua). Thanks to @PassRafael @Vervious for gifting us this protocol.

[אוניברסיטת תל אביב Tel Aviv University @Tel_Aviv_Uni]

מועצת המחקר האירופית (ERC) פרסמה את תוצאות הקול הקורא של מענק ה- #ERCAdvanced לשנת 2023, בהם שלושה זוכים מאוניברסיטת תל אביב: פרופ' יאיר בר-חיים, פרופ' רפאל פס ופרופ' אמיר שפילקה:
https://t.co/GE6grcyFbR
@ERC_Research @PassRafael

[IC3 @initc3org]

🎉Congrats to IC3 faculty member Prof. Rafael Pass @PassRafael for being named as a 2023 International Association for Cryptologic Research Fellow! @IACR_News

[Steve Weis @sweis]

Hot new IACR Fellows just dropped: https://t.co/qKeQg51qHN

[IC3 @initc3org]

Discover new consensus protocols with our faculty Prof. Rafael Pass and PhD student Benjamin Chan @Vervious from Cornell. Don't miss out their latest cutting-edge research in #blockchain #consensus!

[Simons Institute for the Theory of Computing @SimonsInstitute]

Rafael Pass recently gave a two-part tutorial on Cryptography and Kolmogorov Complexity, at our Meta-Complexity Boot Camp. Here's Part 1, which includes a discussion of recent results and the connections between cryptography and Kolmogorov complexity.
https://t.co/6u4OQn9Zyg

[Steve Weis @sweis]

"Cryptography and Kolmogorov Complexity" talk by @PassRafael at @SimonsInstitute: https://t.co/GN3thvg1e1

[Ittai Abraham @ittaia]

The program for the Bar-Ilan Winter School on Blockchain Technologies is 🔥🔥🔥

https://t.co/Mjj90PhwA1

Speakers @danboneh @lera_banda @HatforceSec @EliBenSasson Mary Maller @PassRafael @SashaSpiegelman @LindellYehuda !!

[MIT EECS @MITEECS]

Constantinos Daskalakis, Hiroshi Ishii, Jaime Teevan, Rafael Pass, Kevin Fu, and Jimmy Lin were honored by the Association for Computing Machinery (ACM) as Fellows of the class of 2022!

https://t.co/RT0jlzdAF6

[Ittai Abraham @ittaia]

Where will you be on February 20-23?
At the BIU winter school on Blockchain Technologies!
https://t.co/Hc1tCax0JA

Lectures by @EliBenSasson, @danboneh, @HatforceSec , @LindellYehuda, Mary Maller, @lera_banda, Rafael Pass, and @SashaSpiegelman!!

[Quanta Magazine @QuantaMagazine]

Rafael Pass, a cryptographer at Cornell Tech and Cornell University, and Yanyi Liu, a graduate student at Cornell, have shown that answering one master problem will prove if secure cryptography exists. https://t.co/peIFwsiS4U

[Doro Unger-Lee @doroungerlee]

Congratulations from @AlgoFoundation to @Algorand Centres of Excellence Faculty Rafael Pass for being named an ACM Fellow! Learn more about the prestigious honor here: https://t.co/kywqcOc2DD