A toast to Alistair: Two Minutes on Two Great Professional Surprises

Alistair and the Simons Institure friendly and helpful staff 

Luca Trevisan invited me to give a 3-minute (vidotaped or live) toast for Alistair Sinclair to celebrate that Alistair much deservedly received the SIGACT service award and to mourn that he also just retired from his role of associate director of the Simons Institute. These toasts will be part of FOCS 2017 Saturday evening reception (October 14) which will be hosted by the SI and turn into a party for Alistair. It is great that leading scientists excel also in the all so important academic administration tasks. I can think in this context about Michael Rabin who was the rector (provost) of my university and many others.

But I thought it could be a good idea to mainly mention in my toast two of Alistair’s great and mind-boggling scientific contributions. Miraculously, I had a videotaped which was lying on the editing floor for three years.  It was part of the first ever  (and maybe the only ever) Simons Institute videotaped production. (The toast video was done by me using my smartphone and it took many takes to do.) So you can hear for one minute and a half quick stories about rapid mixing and approximate permanents and inspiring persistence and volume.

From the editing floor: Two Minutes on approximating permanents, rapidly mixing random walks in algorithms, and volumes

Click here for the toast video for Alistair!

This brief video was edited out from my videotaped lecture on quantum computers (see this earlier post). When we prepared the videos, I was quite excited by the fact that we do not  need to shoot the video in the right order. (I even use this fact to outline a major difference between classical computation and quantum computation.)  We first shot the pictorial + entertaining  ending  of Video II. Then we moved to shoot Video I and the plan was to start it with Alistair Sinclair introducing me. In the beginning of the unedited video, I say to Tselil in Hebrew that we do not need to bring Alistair up to the production room  since he can record his introduction later.  (At the end we decided not to have an introduction at all.) As seen from my smile, when I thanked Alistair for his yet-to-be-given introduction I felt as sophisticated as Niccolò Machiavelli.

And here are links to the papers mentioned: Approximating the Permanent by Jerrum and Sinclair, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries by Jerrum, Sinclair and Vigoda (and here is the Journal version), and A random polynomial time algorithm for approximating the volume of convex bodies by Dyer, Frieze and Kannan.

Indeed these amazing algorithmic applications of  rapidly mixing random walks came as great surprises and are extremely important!

Lovely ending presentation, forgotten pictures of Avi and Oded, Jesus, the camel and Bob Simons, and Scott Aaronson’s 100,000$ promise.

Talking about my old Simon Institute lectures videos, let me first recommend to you the two minutes ending of the second video – lovely pictures and a wonderful song in the background. Can you identify the people there? (There are 49 altogether!)


The second video includes (toward the end, click here to jump to this part) a presentation of some pictures +funny things related (more or less) to the debate on quantum-computers. It contains (click to jump) a forgotten picture of Avi Wigderson and Oded Goldreich, Continue reading

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

TYI 31 – Rados Radoicic’s Rope Problem


Ropemaker (source)

Rados Radoicic wrote me:

“Several years back, I heard the following puzzle that turns out to be rather ‘classical’:

“There are N ropes in a bag. In each step, two rope ends are picked uniformly at random, tied together and put back into a bag. The process is repeated until there are no free ends. What is the expected number of loops at the end of the process?”

Before moving on, please try to answer this question.

Let me go on with Rados’ email:

“Upon hearing this puzzle, I came up with and have been wondering (for years now) about the following “natural” variation:

“What if at each step, each end is picked with the probability proportional to the length of its rope?”

I made no epsilon-worthy progress on this problem since then. A properly-trained probabilist (unlike me) might find it easy, but somehow my gut feeling tells me it may be very interesting and not simple at all.”

The challenges are to test yourself on the first question and try to answer the second. No polls this time; comments and thoughts on both versions are welcome.

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 7 Comments

Eran Nevo: g-conjecture part 4, Generalizations and Special Cases

This is the fourth in a series of posts by Eran Nevo on the g-conjecture. Eran’s first post was devoted to the combinatorics of the g-conjecture and was followed by a further post by me on the origin of the g-conjecture. Eran’s second post was about the commutative-algebra content of the conjecture. It described the Cohen-Macaulay property known to hold for simplicial spheres and the Lefshetz property which is known for simplicial polytopes and is wide open for simplicial spheres. Eran’s third post was about the connection to algebraic shifting. The fifth and last post is planned to deal with connections to rigidity, a fascinating topic on its own which is related also like yesterday’s post  to architecture and art.

(From right): Udo Pachner, Peter Kleinschmidt, and Günter Ewald. (Oberwolfach photo collection)

All kinds of spheres

It is possible that the link of a vertex in a simplicial sphere is no longer a sphere. This is not good if we look for a proof by induction. A subfamily which is closed under links is the piecewise linear spheres. Another advantage of this family for inductive proof is given by Pachner: any PL-(d-1)-sphere can be obtained from the boundary of the d-simplex by a finite sequence of bistellar moves aka Pachner moves.  This is a family of d+1 possible local moves, defined combinatorially.

However, so far no proof of the g-conjecture for PL-spheres is known. Continue reading

Posted in Combinatorics, Convex polytopes, Guest blogger, Open problems | Tagged , | 2 Comments

The World of Michael Burt: When Architecture, Mathematics, and Art meet.


This remarkable 3D geometric object tiles space! It is related to a theory of “spacial networks” extensively studied by Michael Burt and a few of his students. The network associated to this object is described in the picture below.

And below you can see the first step in tiling the whole space: How two tiles fit together.

Michael Burt started finding and classifying related objects in his 1967 Master thesis. My academic grandfather Branko Grunbaum (below left) helped him in his early works. The thesis was so impressive that Michael (below, right) was awarded a doctorate for it.


You can find more about it in Michael’s site. The site includes slides for various lectures like the one on UNIFORM NETWORKS, SPONGE SURFACES AND UNIFORM SPONGE POLYHEDRA IN 3-D SPACE.

Below are some more pictures from Michel Burt’s home. In one of them you can see Michael, his wife Tamara, and my friend since university days Yoav Moriah who initiated the visit.


Posted in Art, Combinatorics, Geometry | Tagged , , | 4 Comments


This story is implicitly referred to in the 2008 opening post of this blog.


It was high time to raise the level of the discussion, I thought. Princeton, Fall 1995. We were a group of mathematicians at the IAS lunch table, and discussing a really profound idea was called for. But I was missing a word and I asked Avi Wigderson what is the English word for a lion’s hair. Avi replied “layish”.

This was precisely what I was missing. It was time to voice my new thought:

” Isn’t it the case and isn’t it amazing that Avi’s hair looks just like a layish?”, I asked



Pierre Deligne looked busy thinking about his own business, but Enrico Bombieri looked interested and he was trying to understand what I was saying. Robert Langlands seemed to have got it –  he was nodding his head in agreement – or so I thought. I also sensed a positive reaction from Bob MacPherson.  Well, it takes time for great ideas, however simple, to get through.

But as is often the case, one great idea led to another.

Isn’t it amazing that the word “layish” means in Hebrew “a lion,” a meaning so close to the English meaning? I asked

While trying to further repeat, promote and discuss these two ideas a conflicting piece of information came to my mind. Another word for a lion’s hair in English was something like “main” or “mane”, I started to vaguely remember. When I asked Avi about it, he could not hold his laughter any longer, and the sad reality had emerged.

The second great idea was just an artifact of Avi’s juvenile behavior, a behavior that  also had a devastating effect on the presentation of the first idea. The first idea, as great as it might be,  failed to come through due to problematic notation. It should have waited for another opportunity. And now, 22 years later this opportunity has come!

The observation regarding Avi’s hair is not isolated. Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games, Mathematics to the rescue, Philosophy, Rationality, Sport, Taxi-and-other-stories | Tagged , , | 6 Comments

Some Mathematical Puzzles that I encountered during my career

Recently, I gave some lectures based on a general-audience personal tour across four (plus one) mathematical puzzles that I encountered during my career. Here is a paper based on these lectures which is meant for a very wide audience (in English)

Puzzles on trees, high dimensions, elections, computation and noise.

A  videotaped lecture is here. An earlier Hebrew version is

חידות על עצים , ממדים גבוהים, בחירות, חישוב ורעש

(It deals only with the first four puzzles.) A short videotaped Hebrew lecture (where I only discuss the first two puzzles and touch on the third) is here.

A drawing by my daughter Neta for puzzle number 3. (Based on a famous Florida recount picture.)

Summary: I will talk about some mathematical puzzles that have preoccupied me over the years, and I will also reveal to you some of the secrets of our trade. Continue reading

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

Friendship and Sesame, Maryam and Marina, Israel and Iran

Happy new (Jewish) year everybody.

Amazing scientific partnership  between Jordan, Cyprus, Egypt, Iran, Israel, Pakistan, the Palestinian Authority, and Turkey

SESAME (Synchrotron-light for Experimental Science and Applications in the Middle East) is a “third-generation” synchrotron light source that was officially opened in Allan (Jordan) on 16 May 2017. It is the Middle East’s first major international research center. It is very nice to see scientific cooperation between countries which otherwise do have some difficulties in their relationships.

Narrowing on Israel and Iran, there are many personal scientific friendships and collaborations between Israeli and Iranian scientists and it will certainly be nice to see in the future visits of Israeli scientists to Iran and of  Iranian scientists to Israel.

Marina, Maryam and Maths Friendships

Last July, Marina Ratner and Maryam Mirzakhani, two eminent mathematicians working in the area of dynamics passed away. Maryam was the first woman to win the Fields Medal, and Marina was, for a short time, a faculty member at my department and a close friend of the Hebrew University ever since.   Many of my colleagues knew both Marina and Maryam very well, and were great admirers of their personalities as much as their mathematics. Amie Wilkinson wrote a beautiful NYT article about Marina and Maryam’s mathematics: With Snowflakes and Unicorns, Marina Ratner and Maryam Mirzakhani Explored a Universe in Motion. (See also this HUJI memorial page, this post on Terry Tao’s blog, and this post on GLL.)

Amir Asghari had a nice idea to open a site dedicated to maths friendships in memory of Maryam Mirzakhani.  Let me also mention that there is a well known Israeli Facebook group for “digging into mathematics” that dedicated its profile picture to Maryam.



Posted in Obituary, Updates, Women in science | Tagged , , , , | 1 Comment

Elchanan Mossel’s Amazing Dice Paradox (your answers to TYI 30)

TYI 30 asked Elchanan Mossel’s Amazing Dice Paradox (that I heard from Yuval Peres yesterday)

You throw a die until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers?

Most people answered 3.

Is it the right answer?


Continue reading

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 63 Comments

TYI 30: Expected number of Dice throws

Test your intuition:

You throw a dice until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers.

follow-up post

Posted in Combinatorics, Probability, Test your intuition | Tagged | 37 Comments

Test your intuition 29: Diameter of various random trees

Both trees in general and random trees in particular are wonderful objects. And there is nothing more appropriate to celebrate Russ Lyons great birthday conference “Elegance in Probability” (taking place now in Tel Aviv) than to test your intuition, dear reader, with questions about probability and trees.


Model 1: consider a set of n vertices {1,2,…,n} and a random spanning tree T on these vertices.

Test your intuition: What is the behavior of the diameter of T?

The diameter of a graph G is the maximum distance between pairs of vertices of G. The distance between a pair of vertices is the length of the smallest path between them. (For a tree there is a unique path.)

The answer and two follow up questions are below the fold.

Continue reading

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 19 Comments