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
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