The first part of the post is devoted to eight-year anniversary of my 2016 paper. I will go on to describe a recent lecture by Dorit Aharonov and conclude with my toast to Michael Ben-Or. The Quantum Computer Puzzle, Notices AMS, May 2016. In the eight years since my Notices AMS paper (with the beautiful drawings by my daughter Neta) “The quantum computer puzzle” appeared, my point of view has been challenged by several experimental attempts for demonstrating quantum advantage and quantum error correction. From what I can discern, my argument still holds as a serious alternative to the prevale ..read more

Happy Passover to all our readers On the way from Cambridge to Tel Aviv I had a splendid three hour visit to London (from Kings Cross to UCL and back), where I met my graduate student Gabriel Gendler and Freddie Illingworth. (Like Tim Gowers and Imre Leader but a few decades later, Freddie and Gabriel first met at an IMO.)  Gabriel and Freddie told me about several striking things including the remarkable “glider” proof for showing that Kneser graphs, Schrijver graphs, and stable Kneser graphs are Hamiltonian. To quote Merino, Mütze, and Namrata: “Our main technical innovation is to study ..read more

I am writing from Cambridge, UK, where I participated in an impressive conference celebrating Tim Gowers’s 60 birthday and I an about to take part in a satellite workshop of Theoretical computer science. Coming here was my first travel since the start of the war on October 7, and earlier today (April 14, around 02:00) we were witnessing a major dangerous escalation of the war with a direct Iranian drone and missile attack on Israel. (The sky in Israel during the attack  source: Haaretz.) The group photo of the conference. (Tim Gowers is second on the right on the first row.) Let me tell ..read more

Our new paper Yosi Rinott, Tomer Shoham and I wrote a new paper on our statistical study of the data from the 2019 Google quantum supremacy experiment. Random Circuit Sampling: Fourier Expansion and Statistics, by Gil Kalai, Yosef Rinott, and Tomer Shoham This version is still a draft and any corrections, comments, related thoughts, and discussion are most welcome. In my view the results are quite interesting; we develop statistical tools and study data from experiments and simulations. As before, we try to discuss as much as possible the findings and possible interpretations with the authors ..read more

Jerusalem October 4, 2023 The picture on the right is from ~ 60 years ago. Tel Aviv, five sunsets and a horse Efi Arazi school of Computer Science Corona times Tel Aviv (in the balcony – our grandchildren) with my sister and daughter Drawings by My grandchildren (Ilan and Yoav) Ilan: demonstrations for democracy Yoav: Mona Lisa Cats Above, Herzeliya, 2022, below photo by Izabella Laba (a FB comment to my post), old city of Jerusalem, date unknown. New York Discussing the logarithmic Minkowski problem, with Deane Yang and Gaoyong Zhang, above; The logarithmic origin of NYC, below ..read more

A carpet of flowers in Shokeda, near Gaza, a few years ago. This is the fourth post of this type (I (2008); II(2011); III(2015).) I started planning this post in 2019 but as it turned out, earlier drafts have quickly became obsolete and the process of writing this post did not converge. Updates Current academic life around here In an earlier post I wrote about the hectic academic scene around here last spring. These were post-corona times, we had many visitors, workshops, conferences, and other activities. Since October 7, things are different also on the academic side of my life: only few vi ..read more

In the picture (compare it to this picture in this  post) you can see David DiVincenzo’s famous 7-steps road map (from 2000) to quantum computers, with one additional step “quantum supremacy on NISQ computers” that has proposed around 2010. Step 4 of logical memory with a substantial longer lifetime than physical qubits has not yet been achieved (Craig Gidney expects it in five years); However, Dolev Bluvstein et al.’s paper makes a bold move toward higher steps in DiVincenzo’s plan and toward some kind of quantum fault tolerance even before reaching very stable logical qubits. I would l ..read more

The power of negative thinking: Combinatorial and geometric inequalities Two weeks ago, I participated (remotely) in the discrete geometry Oberwolfach meeting, and Ramon van Handel gave a beautiful lecture about the equality cases of Alexandrov-Fenchel inequalities which is among the most famous problems in convex geometry. In the top left, Ramon explains the AF-inequality and its equality cases for three dimensions. The extremal bodies, also depicted in the top right, remind me of “stacked polytopes.” On the bottom right, you can see the AF-inequality, with the definition of mixed vol ..read more

Alex Samorodnitsky The most powerful general method for proving upper bounds for the size of error correcting codes and of spherical codes (and sphere packing) is the linear programming method that goes back to Philippe Delsarte. There are very interesting results and questions about the power of this method and in this post I would like to present a few of them, especially results from 2001 and 2004 papers by Alex Samorodnitsky, a 2001 paper by Alexander Barg and David Jaffe, and a 2009 paper by Alex and Michael Navon, finally I will briefly mention a 2023 paper by  Matthew de Courcy-Ir ..read more

Two months ago I presented five riddles and here, in this post, you will find a few more. (These types of riddles are called by Maya Bar-Hillel “stumpers”.) This time, we will have a discussion about how riddles are related to psychology and how this relation might be connected to (or even explored by) AI. Let’s start with three new riddles. Three new riddles Cecil is a criminal lawyer. Many years ago, he spent a couple of days in hospital. When he was discharged, he was in perfect health. Indeed, there was nothing at all wrong with him. Nonetheless, he was incapable of leaving his hospital b ..read more