Member @ IAS. Phd @ Columbia. Anything TCS. https://nitter.cf/t.co/Dk6UWikXxt
Joined July 2022
- Tweets113
- Following161
- Followers200
- Likes42.8K
Yuval Efron retweeted
An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4
Yuval Efron retweeted
Wow, here is a substantial advancement in theoretical consensus research from @komasito55 (of @category_xyz), @ElodinStorm and Ling Ren!
It resolves a long-standing open question and improves on the previous-best O(n^3) communication complexity of the Dolev-Strong algorithm published in 1983. The new algorithm is near-quadratic while tolerating any number of faulty participants below the total
Category Labs is making fundamental research progress as they continue to improve Monad through exceptional pragmatic algorithm engineering
Dolev–Strong is arguably the best-known consensus protocol, and for roughly 45 years, no deterministic protocol improved on its O(n³) communication.
A new paper by @komasito55, Yuval Efron and Ling Ren improves that bound to O(n² log⁴ n) for Byzantine Broadcast, tolerating t < n faults in O(t) rounds.
After thinking about the problem on and off for years, they started leveraging AI models. The paper is the result of a month of human experts digesting and simplifying the discourse with AI.
Yuval Efron retweeted
Dolev–Strong is arguably the best-known consensus protocol, and for roughly 45 years, no deterministic protocol improved on its O(n³) communication.
A new paper by @komasito55, Yuval Efron and Ling Ren improves that bound to O(n² log⁴ n) for Byzantine Broadcast, tolerating t < n faults in O(t) rounds.
After thinking about the problem on and off for years, they started leveraging AI models. The paper is the result of a month of human experts digesting and simplifying the discourse with AI.
Dolev–Strong is arguably the most well-known consensus protocol, yet in about 45 years no deterministic protocol improved on its O(n^3) communication.
With @komasito55 & Ling Ren, we get O(n^2 log^4 n) for Byzantine Broadcast, t<n faults, O(t) rounds:
eprint.iacr.org/2026/2504
My coauthors and I have thought about this problem on and off for years. Some of our ideas, or kernels of them, do appear in the final protocol, but the elegance, clarity and attention to detail in the AI’s techniques would probably have taken us a long time to find on our own.
Yuval Efron retweeted
@ElodinStorm and I wrote a short paper showing that Byzantine lattice agreement can be solved in sublogarithmic rounds without any crypto. A simple reduction from Byzantine lattice agreement to Byzantine approximate agreement lets it inherit the sub-log bounds of approximate agreement.
Link: eprint.iacr.org/2026/2400
Yuval Efron retweeted
Just posted a survey of pseudorandom codes! They're a fascinating new crypto primitive equivalent to robust and quality-preserving watermarks.
The survey is a handbook for researchers & has many open questions. Enjoy!
eprint.iacr.org/2026/2162
Yuval Efron retweeted
A hypothetical AI ethic problem: Suppose group A solves an important problem (using AI) and uploads it to arXiv. An unethical group B gives their manuscript to AI & asks for a different proof; uploads new proof tomorrow & claims an independent result. How can we prevent this?
Yuval Efron retweeted
While I am glad to see the mathematics world start thinking about itself in the age of AI, I share the disappointment of @tylercowen that they are pointing a finger at the AI companies rather than accepting that the new mathematical sensibilities must come from themselves.
Very good post from @tylercowen. Endorse.
The mathematicians rebel against AI marginalrevolution.com/margi…
Yuval Efron retweeted
How fast, in the common case, can consensus be without cryptography? As fast as with it.
Meet Floor-IT: information-theoretic BFT for partial synchrony that decides in 2 rounds in the good case, at the optimal n = 5f−1 — with O(1) persistent storage and O(n²) messages per view.
Link: eprint.iacr.org/2026/1496
With @ittaia, @ElodinStorm, and @alranpe
Yuval Efron retweeted
If someone gave you a cure for cancer, if you are like me, you'll take/use the cure regardless of which AI tool was used to generate it.
The main question I find important: what kind of TCS research is important science when we no longer can claim weightlifting as a motivation?
Yuval Efron retweeted
Is there anything computers can't do? Does Alan Turing's revolutionary work remain relevant in a world with generative AI and quantum computers? Announcing a new mini-series, for a general audience, on Computation and Its Limits.
This is one of several short courses on the new Ergo platform, "a nonprofit that publishes long-form philosophical lectures online, without ads or paywalls."
Get started at ergo.org/courses/computation…
Beyond thrilled to share that this fall I'll be starting as a postdoc with @Tim_Roughgarden at @the_IAS. Feeling very fortunate to be joining the TCS community at IAS.
Life update: I've joined @the_IAS as a Professor in the School of Mathematics! Very excited to be part of the Institute’s growing commitment to theoretical computer science, its connections to other fields, and its importance for understanding and shaping modern technology.
Yuval Efron retweeted
📢 @Tim_Roughgarden, a world-renowned authority in the field of algorithmic game theory and "an intellectual leader in algorithms and optimization," has joined @the_IAS as a Professor in the School of Mathematics: ias.edu/news/algorithmic-gam…
This conversation is a gem.
Barbara Liskov is one of the giants of computer science and a personal hero of mine 😍
Her episode on First Principles, hosted by @Tim_Roughgarden, is a must watch 🔥🔥🔥
youtube.com/watch?v=5N2MGCh2…
Yuval Efron retweeted
In advance of conversations with Barbara Liskov and Leslie Lamport, @ittaia and I trace the path from Byzantine Generals to Bitcoin, and beyond
First Principles Ep. 1
Bitcoin gets credited with inventing trustless consensus. It didn’t. The problem was named in the 1980s, and it took the research world years to even notice Satoshi had solved it.
A new series hosted by @Tim_Roughgarden, with @ittaia.
00:00 Introduction to First Principles: The Scientific Roots of Blockchain Technology
00:56 Why consensus matters for blockchains
02:30 Byzantine agreement: The old computer science problem Bitcoin made practical
04:34 Blockchains as a shared system of record: State machine replication and blockchain state
06:41 How two research worlds — distributed computing and crypto — began to converge
07:49 Proof of work vs. proof of stake
09:27 Why Ethereum’s move to proof-of-stake took years
11:08 When crypto rediscovered decades of distributed systems research
12:49 Throughput, latency, and modern consensus design
14:05 DAG-based protocols and faster blockchains
15:25 Peace time vs. war time: why modern blockchains need two modes
16:47 Theory, practice, and the future of blockchain research
Yuval Efron retweeted
1/ Bitcoin 2009: 10min block times
Ethereum 2014: 12s block times
Solana 2020: 400ms block times
New chains in 2026: still 400ms!
Gatling 2026: 10ms slots with 214ms end-to-end tx latency
Gatling: Rapid-Fire Consensus from Parallel Composition, w/ @jneu_net & @MaxResnick 🧵