Shreyas Srinivas
@lean-samaritan.bsky.social
Research : Formal Math ∩ Algorithms ∩ Lean ∩ Hardware
Reposted by Shreyas Srinivas
In optimization problems, randomness thwarts complexity.
Researchers Discover the Optimal Way To Optimize | Quanta Magazine
The leading approach to the simplex method, a widely used technique for balancing complex logistical constraints, can’t get any better.
www.quantamagazine.org
October 14, 2025 at 5:45 PM
In optimization problems, randomness thwarts complexity.
Reposted by Shreyas Srinivas
Open Printer: an open-source inkjet printer with no DRM, no subscriptions, and repairable parts.
Sometimes the best innovation is just making things work the way they should have all along.
Sometimes the best innovation is just making things work the way they should have all along.
October 7, 2025 at 7:39 AM
Open Printer: an open-source inkjet printer with no DRM, no subscriptions, and repairable parts.
Sometimes the best innovation is just making things work the way they should have all along.
Sometimes the best innovation is just making things work the way they should have all along.
Reposted by Shreyas Srinivas
Today at IAS, I gave a 2 hr 15 mins lecture on why TIME[t] is in SPACE[√(t log t)]. You can watch it here!
www.youtube.com/watch?v=ThLv...
www.youtube.com/watch?v=ThLv...
Simulating Time With Square-Root Space (And With Details) - Ryan Williams
YouTube video by Institute for Advanced Study
www.youtube.com
September 23, 2025 at 8:22 PM
Today at IAS, I gave a 2 hr 15 mins lecture on why TIME[t] is in SPACE[√(t log t)]. You can watch it here!
www.youtube.com/watch?v=ThLv...
www.youtube.com/watch?v=ThLv...
Reposted by Shreyas Srinivas
You likely have a world model running inside your skull right now — it’s how you know not to step in front of a moving train without needing to run the experiment first. So far, AI lacks such a scaled-down representation of the environment.
‘World Models,’ an Old Idea in AI, Mount a Comeback | Quanta Magazine
You’re carrying around in your head a model of how the world works. Will AI systems need to do the same?
www.quantamagazine.org
September 7, 2025 at 3:15 PM
You likely have a world model running inside your skull right now — it’s how you know not to step in front of a moving train without needing to run the experiment first. So far, AI lacks such a scaled-down representation of the environment.
Reposted by Shreyas Srinivas
"The day the paper was published should have been a moment of pride. Instead, it felt like a quiet erasure." #ScienceWorkingLife https://scim.ag/4p3eH5g
August 25, 2025 at 1:24 PM
"The day the paper was published should have been a moment of pride. Instead, it felt like a quiet erasure." #ScienceWorkingLife https://scim.ag/4p3eH5g
Reposted by Shreyas Srinivas
To all the people mocking LLMs because it's "just matrix multiplication (linear algebra):"
Careful there! You're going to piss off the quantum physicists
Careful there! You're going to piss off the quantum physicists
August 10, 2025 at 10:13 AM
To all the people mocking LLMs because it's "just matrix multiplication (linear algebra):"
Careful there! You're going to piss off the quantum physicists
Careful there! You're going to piss off the quantum physicists
Reposted by Shreyas Srinivas
Thorsten Altenkirch explains Gödel's Incompleteness Theorem on @computerphile.bsky.social, and shows some definitions in #LeanLang! 🎯
Watch here: www.youtube.com/watch?v=IuX8...
Watch here: www.youtube.com/watch?v=IuX8...
Gödel's Incompleteness Theorem - Computerphile
YouTube video by Computerphile
www.youtube.com
August 6, 2025 at 1:46 PM
Thorsten Altenkirch explains Gödel's Incompleteness Theorem on @computerphile.bsky.social, and shows some definitions in #LeanLang! 🎯
Watch here: www.youtube.com/watch?v=IuX8...
Watch here: www.youtube.com/watch?v=IuX8...
Reposted by Shreyas Srinivas
After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available.
arxiv.org/abs/2507.11536
arxiv.org/abs/2507.11536
Understanding Quantum Information and Computation
This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...
arxiv.org
July 16, 2025 at 11:06 AM
After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available.
arxiv.org/abs/2507.11536
arxiv.org/abs/2507.11536
Reposted by Shreyas Srinivas
Reminder/plug: my graduate-level monograph on "Topics and Techniques in Distribution Testing" (FnT Comm. and Inf Theory, 2022).
📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
November 15, 2024 at 8:02 PM
Reminder/plug: my graduate-level monograph on "Topics and Techniques in Distribution Testing" (FnT Comm. and Inf Theory, 2022).
📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
📖 ccanonne.github.io/survey-topic... [Latest draft+exercise solns, free]
📗 nowpublishers.com/article/Deta... [Official pub]
📝 github.com/ccanonne/sur... [LaTeX source]
Reposted by Shreyas Srinivas
This lecture provides a gentle introduction to amortized analysis.
For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before.
www.youtube.com/watch?v=8mHa...
For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before.
www.youtube.com/watch?v=8mHa...
Lecture 4.1: Amortized Analysis: Bank account method, Binomial heaps, Hollow heaps
YouTube video by Thatchaphol Saranurak
www.youtube.com
July 18, 2025 at 4:32 PM
This lecture provides a gentle introduction to amortized analysis.
For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before.
www.youtube.com/watch?v=8mHa...
For experts: At the end, I explained Hollow Heaps, an optimal heap like Fibonacci heaps, but simpler! Surprisingly, I have not seen video lectures on this before.
www.youtube.com/watch?v=8mHa...
Reposted by Shreyas Srinivas
Markus Himmel has written a blog post about how to write a simple imperative program in Lean and then how to verify that the program is bug-free.
markushimmel.de/blog/my-firs...
markushimmel.de/blog/my-firs...
My first verified (imperative) program
One of the many exciting new features in the upcoming Lean 4.22 release is a preview of the new verification infrastructure for proving properties of imperative programs. In this post, I’ll take a fir...
markushimmel.de
July 6, 2025 at 4:03 PM
Markus Himmel has written a blog post about how to write a simple imperative program in Lean and then how to verify that the program is bug-free.
markushimmel.de/blog/my-firs...
markushimmel.de/blog/my-firs...
Reposted by Shreyas Srinivas
📣 We're excited to share the new lean-lang.org!
Relaunching our website was a key deliverable in our Year 2 roadmap to provide "improved navigation and access to valuable content, resources, and tools." We hope you like it!
#LeanLang #LeanProver
Relaunching our website was a key deliverable in our Year 2 roadmap to provide "improved navigation and access to valuable content, resources, and tools." We hope you like it!
#LeanLang #LeanProver
July 7, 2025 at 9:02 PM
📣 We're excited to share the new lean-lang.org!
Relaunching our website was a key deliverable in our Year 2 roadmap to provide "improved navigation and access to valuable content, resources, and tools." We hope you like it!
#LeanLang #LeanProver
Relaunching our website was a key deliverable in our Year 2 roadmap to provide "improved navigation and access to valuable content, resources, and tools." We hope you like it!
#LeanLang #LeanProver
I finally understand the mechanism of the Jacquard loom. Still cannot fathom how designers program the holes.
youtu.be/pzYucg3Tmho
youtu.be/pzYucg3Tmho
Binary and the Jacquard Mechanism - demonstration
YouTube video by Macclesfield Museums
youtu.be
July 6, 2025 at 9:46 PM
I finally understand the mechanism of the Jacquard loom. Still cannot fathom how designers program the holes.
youtu.be/pzYucg3Tmho
youtu.be/pzYucg3Tmho
Reposted by Shreyas Srinivas
Graph theorist Maria Chudnovsky proved the strong perfect graph theorem, which was proposed back in the 1960s. Tune in to “The Joy of Why” with co-host @jannalevinastro.bsky.social:
How Does Graph Theory Shape Our World? | Quanta Magazine
Maria Chudnovsky reflects on her journey in graph theory, her groundbreaking solution to the long-standing perfect graph problem, and the unexpected ways this abstract field intersects with everyday…
www.quantamagazine.org
July 4, 2025 at 12:07 PM
Graph theorist Maria Chudnovsky proved the strong perfect graph theorem, which was proposed back in the 1960s. Tune in to “The Joy of Why” with co-host @jannalevinastro.bsky.social:
Reposted by Shreyas Srinivas
Our ICALP 2025 paper is now available here! We present the first example of a locally checkable labeling problem that becomes much easier to solve with distributed algorithms if you have access to shared randomness.
doi.org/10.4230/LIPI...
doi.org/10.4230/LIPI...
Shared Randomness Helps with Local Distributed Problems
doi.org
June 30, 2025 at 10:31 PM
Our ICALP 2025 paper is now available here! We present the first example of a locally checkable labeling problem that becomes much easier to solve with distributed algorithms if you have access to shared randomness.
doi.org/10.4230/LIPI...
doi.org/10.4230/LIPI...