Luca Trevisan (1971-2024)
![](https://149663533.v2.pressablecdn.com/wp-content/uploads/2024/06/luca-1024x684.jpg)
(See here for Boaz Barak’s obituary)
Luca Trevisan, one of the world’s leading theoretical computer scientists, has succumbed to cancer in Italy, at only 52 years old. I was privileged to know Luca for a quarter-century, first as my complexity theory and cryptography professor at UC Berkeley and as a member of my dissertation committee, and then as a friend and colleague and fellow CS theory blogger.
I regret that I learned of the seriousness of Luca’s condition only a few days ago. So yesterday morning I wrote him a farewell email, under the impression that, while he was now in hospice care, he had at least a few more weeks. Alas, he probably never saw it. So I’m hereby making the email into a memorial post, with small changes mostly to protect people’s privacy.
Dear Luca,
Dana, the kids, and I were traveling in Israel for the past two weeks, when I received the shocking and sad news that this might be my last chance to write to you.
At risk of stating the obvious — you had a very large and positive effect on my life and career. Starting with the complexity theory summer school at the Institute for Advanced Study in 2000, which was the first time we met and also the first time I really experienced the glories of complexity at full blast. And then continuing at Berkeley, TA’ing your algorithms class, which you had to cancel on 9/11 (although students still somehow showed up for office hours lugging their CLRS books…), and dealing with that student who obviously cheated on the midterm although I had stupidly given back to her the evidence that would prove it.
And then your graduate complexity course, where I was very proud to get 100% on your exam, having handwritten it on a train while everyone else used LaTeX (which, embarrassingly, I was still learning). I was a bit less proud to present the Razborov-Rudich paper to the class, and to get questions from you that proved that I understood it less thoroughly than I thought. I emerged from your course far better prepared to do complexity theory than when I entered it.
Later I took your cryptography course, where I came to you afterwards one day to point out that with a quantum computer, you could pull out big Fourier coefficients without all the bother of the Goldreich-Levin theorem. And you said sure, but then you would need a quantum computer. Over 20 years later, Goldreich and Levin (and you?) can say with satisfaction that we still don’t have that scalable quantum computer … but we’re much much closer, I swear!
I still feel bad about the theory lunch talk I gave in 2003, on my complexity-theoretic version of Aumann’s agreement theorem, where I used you and Umesh as characters instead of Alice and Bob, and which then led to unintended references to “Luca’s posterior.”
I also feel bad about delaying so long the completion of my PhD thesis, until well after I’d started my postdoc in Princeton, so that my former officemate needed to meet you on a street corner in San Francisco to sign the signature page the night before the deadline.
But then a few years later, when Avi and I did the algebrization paper, the fact that you seemed to like it mattered more to me than just about anything else.
Thank you for the excellent dinner when I met you some years ago in Rome. Thank you for the Trevisan-Tulsiani-Vadhan paper, which answered a question we had about BosonSampling (and you probably didn’t even know you were doing quantum computing when you wrote that paper!). Thank you for your blog. Thank you for everything you did for me.
I always enjoyed your dry humor, much of which might sadly be lost to time, unless others wrote it down or it’s on YouTube or something. Two examples spring to my mind across the decades:
- “From my previous lecture, you may have gotten the impression that everything in derandomization is due to Nisan and Wigderson, but this is not the case: Avi has been working with other people as well.”
- After I’d explained that I’d be spending a semester in Jerusalem to work with Avi Wigderson, despite (at that time) knowing only the most rudimentary Hebrew, such as how to say “please” and “excuse me”: “you mean there are words in Hebrew for ‘please’ and ‘excuse me’?”
Speaking of which, my current trip to Israel has given me many opportunities to reflect on mortality — for all the obvious war-related reasons of course, but also because while we were here, we unexpectedly had to attend two shivas of people in our social circle who died during our trip, one of them from cancer. And we learned about a close friend whose stepson has a brain tumor and might or might not make it. Cancer is a bitch.
Anyway, there’s much more I could write, but I imagine you’re getting flooded with emails right now from all the people whose lives you’ve touched, so I won’t take up more of your time. You’ve made a real difference to the world, to theoretical computer science, and to your friends and colleagues, one that many people would envy.
Best,
Scott