Category Archives: Computer Science and Optimization

November’s Lectures, 2025

Posted on December 21, 2025 by Gil Kalai

Happy Chanukah, everybody! There is a lot of academic activity around, and the ceasefire in Gaza has brought some relief and hope. Let me tell you about the (unusually high number of) lectures I attended in November 2025, in reverse … Continue reading →

Posted in AI, Combinatorics, Computer Science and Optimization, Geometry, Physics, Quantum, Updates | 11 Comments

Computational Complexity and Explanations in Physics

Posted on November 3, 2025 by Gil Kalai

The title of this post is taken from a recent interesting lecture (judging from the slides) by Scott Aaronson at Columbia University. The lecture explored a wide range of topics at the intersection of physics, computation, and philosophy. In this … Continue reading →

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , , , | 11 Comments

Explicit Lossless Vertex Expanders!

Posted on October 10, 2025 by Gil Kalai

(from left to right): Beth Samuels, Uzi Vishne, Alex Lubotzky, and Winnie Li Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang, Explicit Lossless Vertex Expanders Abstract: We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for … Continue reading →

Posted in Algebra, Combinatorics, Computer Science and Optimization | Tagged , , , , , , | Leave a comment

Dror Bar-Natan and Roland Van der Veen – A Fast, Strong, and Fun knot invariant!

Posted on September 25, 2025 by Gil Kalai

Dror Bar-Natan (homepage, Wikipedia) told me about his work with Roland Van der Veen (homepage, arXiv, YouTube) on a wonderful knot invariant which distinguishes knots much better than other knot invariants, and can be computed quickly even for knots of … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 1 Comment

Some Questions from Recent Quantum Events

Posted on July 30, 2025 by Gil Kalai

Over the past few years, I have given several lectures about quantum computation, presenting my argument for why quantum computing—and even significant early milestones toward it—are fundamentally impossible. Recently, I participated in a debate with Matthias Christandl on the possibility … Continue reading →

Posted in Computer Science and Optimization, Controversies and debates, Physics, Quantum | Tagged , , | 6 Comments

Joram’s seminar 2025: Hypercontractivity, Groups and Representations

Posted on July 15, 2025 by Gil Kalai

Joram’s seminar 2025 Here is my summary of the recent Joram’s seminar that took place on July 9 and 10 in Jerusalem. Much of the seminar was about the the paper Product Mixing in Compact Lie Groups by David Ellis, … Continue reading →

Posted in Algebra, Combinatorics, Computer Science and Optimization, Conferences | Tagged , , , , , , , | 5 Comments

Happy Birthday Saharon Shelah and Yuri Gurevich!

Posted on July 7, 2025 by Gil Kalai

Let me briefly report on two birthday conferences for long-time friends and colleagues Saharon Shelah and Yuri Gurevich. Yuri fest took place in Munich and on Zoom between June 20–22 2025 and Shelah’s birthday conference will be held in Vienna … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Happy birthday, Logic and set theory, People, Quantum, Updates | Tagged , , | Leave a comment

Shakhar Smorodinsky’s Solution to a Radon-Type Problem

Posted on June 18, 2025 by Gil Kalai

A brief update: Since Friday June 13 Israel has been engaged in a direct war with Iran. This follows two major missiles attacks of Iran against Israel in April and October 2024, as well as Iran’s central role in the … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry, Updates | Tagged , , , , | 3 Comments

A Few Announcements

Posted on June 11, 2025 by Gil Kalai

Trevisan Prize 2025 Here is a call for nominations for a new theoretical computer science prize, in memory of  Luca Trevisan. (h/t Alon Rosen.) Three Near Future Events at HUJI While the Erdős Lectures 2025 given by Mehtaab S. Sawhney, … Continue reading →

Posted in Algebra, Analysis, Combinatorics, Computer Science and Optimization, Games, Logic and set theory, Number theory, Updates | Tagged , , , , , , | 2 Comments

Ethereum Foundation Talk and Conversation: A Critical View on Quantum Computing & A geometry day honoring Micha Sharir

Posted on June 3, 2025 by Gil Kalai

Ethereum Foundation talk, today This afternoon (Tuesday, June 3, 2025) at 17:00 Israel time I give a zoom lecture on A Critical View on Quantum Computing. The lecture is hosted by the Ethereum Foundation and the 90 minute events will … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry, Quantum, Sport | Tagged , , , | Leave a comment