Luca Trevisan (1971-2024)
(See here for Boaz Barak’s obituary, and here for Lance Fortnow’s—they cover different aspects of Luca’s legacy from each other and from this post. Also, click here to register for a free online TCS4All talk that Luca was scheduled to give, and that will now be given in his memory, this Monday at 3:30pm Eastern time.)
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” (probability distribution, I meant).
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, 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
Follow
Comment #1 June 19th, 2024 at 5:53 pm
Thank you, Scott. That is a beautiful email and tribute. I hope Luca had a chance to see it.
He will be dearly missed.
Comment #2 June 19th, 2024 at 6:44 pm
Thanks for sharing a glimpse of a good man-very nice letter.
Comment #3 June 19th, 2024 at 8:03 pm
Death is an absolute point of human life.
RIP
Comment #4 June 20th, 2024 at 2:03 am
Such a lovely email to someone who touched my life even without meeting me but took the liberty to email. The CS community has really lost a giant.
Comment #5 June 20th, 2024 at 3:39 am
[…] at 4:38 pm and is filed under Nerd Interest. You can follow any responses to this entry through the RSS 2.0 […]
Comment #6 June 20th, 2024 at 3:41 am
[…] Nerd Interest. You’ll be able to observe any responses to this entry by means of the RSS 2.0 […]
Comment #7 June 20th, 2024 at 4:04 am
This is indeed sad news. A gem of a person lost to this brutal killer disease. It is surprising to watch humanity not throwing the kitchen sink at this terrible scrouge that has afflicted us since forever, and one of the last ones left that sucks out the young, and mostly no fault of theirs. It is high time some effort is started on the scale of space missions or even CERN, with modern AI from Deepmind etc thrown in, lest the prediction of a third of the population will experience in their lifetime the horrors of this disease are about to become a reality. It may still not give breakthroughs, but not atleast for not trying hard.
Comment #8 June 20th, 2024 at 9:04 am
Prasanna #7
Actually a lot of progress is being done.
Breast cancers linked to hormones can now be treated very effectively.
For a lot of other serious cancers, immunotherapy is making a huge difference.
Some tumors evolve a way to evade the body’s immune system, which can be recognized through a biopsy and a DNA analysis. Then the treatment consists in injecting a synthesized molecule that binds to the cancer cells, allowing for the immune system to recognize them and attack them, it’s actually very similar to a vaccine.
The problem is that, just like for viruses and vaccines, the results can be very spectacular, but are often temporary, because the treatment itself ends up selecting mutations of the cancer that are resistant to the treatment (the same actually happens with common chemotherapy). Such treatments are also pretty expensive, still.
But the hope is that eventually we have so many adapted treatments that even though cancer never goes away, one can live with it for decades (just like for AIDS).
They can also now keep track of resurgence of many cancers by looking for DNA traces of the tumors in the blood stream (all it takes is a simple blood draw and send it to a lab, after the tumors have been profiled).
My recommendation is to get a colonoscopy as soon as possible (early 30s).
Comment #9 June 20th, 2024 at 12:21 pm
Fred #8
The overall cancer survival rate was 49 percent in the mid-1970s. It currently sits at 68 percent. Over a 50 year period that is some progress, but not a significant one. For those who encounter this and survive, its no means a normal life, with the hanging sword of recurrence/metastasis , and living with post surgical complications.
The significant rise in cancer rates in the population also erase the gains in survival rates. Studies have found that American men have about a 40% chance of developing cancer in their lifetimes.
So overall, this definitely needs a Apollo kind of program to bring down incidences and improve survival rates significantly.
Also note
https://www.ncbi.nlm.nih.gov/search/research-news/19988/
Comment #10 June 20th, 2024 at 3:13 pm
Prasanna #9
Thank you, as someone living with cancer (ten years with esophageal squamous cell carcinoma stage 4, and one year with colon adenocarcinoma stage 3), I agree that it’s a challenge.
But the single word “cancer” really covers a lot of different and complex things, with a multitude of causes (in my case possibly a consequence of 9/11) and effects.
And while cancer in young people and children is truly horrible, in the really long run (old age) everyone is almost guaranteed to develop cancer (assuming we dodge heart disease, Alzheimer, and diabetes). One can see this by visiting an “average” oncologist office – the vast majority of patients will be pretty old, and the younger ones tend to go to the cutting edge centers like MSK.
Obviously it’s this way because it’s so fundamentally related to how life works at a very basic level, with DNA, mutations, the immune system… and those things degrade significantly with age.
It’s likely that really curing cancer would pretty much mean we’d have the tools to also extend life indefinitely.
But what’s really concerning these days is that cancer actually appears more and more in younger people.
Apparently only recently scientists realized that environment (water, food chain) was saturated with microscopic particles of plastic (on top of all the carcinogens that we already knew), making their way and accumulating into our bodies, causing not just cancer but also all sorts of hormonal disruptions in kids and teenagers.
So maybe the key here isn’t to just focus on curing the cancer (the effect) but also cleansing our environment (but that’s probably even more difficult given all the economical incentives to keep plastics and pollutants around).
Comment #11 June 20th, 2024 at 3:21 pm
A piece about micro plastic particles being literally everywhere
https://www.sciencenews.org/article/microplastics-human-bodies-health-risks
Comment #12 June 20th, 2024 at 4:43 pm
Oh, wow…
My deepest condolences to all who reading this who knew Luca Trevisan essentially infinitely more than me, since if I recall correctly, I never met him. However, he nonetheless holds a place among my fond early grad school intellectual memories since it was from Chapter 7 of his _Lecture Notes on Computational Complexity_ from his Fall 2002 UC Berkeley Computational Complexity course notes…
https://lucatrevisan.github.io/notes/complexitynotes02.pdf
… that I learned in detail the Valiant-Vazirani Reduction showing an efficient algorithm for “Unique-SAT” (i.e., an algorithm guaranteed to succeed in polynomial time on all formulae that have a unique satisfying assignment) would in fact mean NP = RP. Back then, I was seeking out out some definitive-but-user-friendly reference to that result after hearing Eddie Farhi give me the advice that — for whatever it’d be worth to me — I could, without any meaningful loss of generality, analyze adiabatic quantum algorithms just on problem Hamiltonians guaranteed to have a non-degenerate ground state. Ah, my halcyon days of youth in the early 2000s. 🙂
And on that note of my halcyon days of youth, I recall that much more excitingly, it was from Chapters 15 and 16 of his above-linked lecture notes that I really learned for the first time about the “approximation preserving reductions” of various common NP-complete problems and thus how PCP theorem entails the NP-completeness of approximating all sorts of common NP-complete problems beyond certain fractions of the optimal answer. (To take one canonical example, you’d have in fact actually proved P = NP and not just made a nontrivially good Max-3SAT approximation algorithm if you ever somehow made an algorithm for Max-3SAT that, even in the worst-case, guarantees an output assignment in polynomial time that’ll satisfies at least 7/8 + o(1) of the true maximum number of simultaneously satisfiable 3CNF clauses [with 7/8 sort of being the “trivial” achievable approximation factor given that a single 3CNF clause rules out only 1 of the 8 possibilities for the 3 bits it involves] ).
Again, my deepest condolences to all who knew Luca Trevisan, especially those who, unlike me, knew him personally rather than through his lecture notes.
Comment #13 June 20th, 2024 at 4:54 pm
I was shocked and saddened to hear that Luca Trevisan passed away yesterday. I didn’t know Luca well (or basically at all), but I had a couple brief interactions with him, one of which I would like to mention. It is about my graduate school qualifying exam.
I was a grad student in the math department at Berkeley, where the qualifying exam is a 2-3 hour oral exam with 2 “major topics” and 1 “minor topic,” all of which are chosen by the student. At the time, qualifying exam committees were required to have one “outside member,” meaning a professor who is not in the math department. I decided to kill two birds with one stone by choosing complexity theory as my minor topic and asking Luca to be on my committee. Normally, finding outside members to serve on a qualifying exam committee can be a real pain, but Luca very kindly agreed to serve on mine (replying to my emailed request just 7 minutes after I had sent it).
The first section of my qualifying exam went well, but I had some trouble on the second section. All that remained was the third section, on complexity theory, but I was feeling very flustered after my mistakes in the second section. Luca noticed that I was looking nervous and suggested we take a 5 minute break before moving on to the final section of the exam. After returning from the break, I felt calmer and the rest of the exam went smoothly. Although what Luca did was a small gesture, it really helped me and I feel grateful to him to this day for his kindness. He was also a great committee member, asking interesting questions while also being very kind and encouraging.
Aside from my personal interactions with him, I was a fan of Luca’s blog and an admirer of his research. Also, my highest upvoted mathoverflow answer essentially consists of retelling a story I read on his blog: https://mathoverflow.net/questions/385732/proofs-of-theorems-that-proved-more-or-deeper-results-than-what-was-first-suppos/385767#385767.
Comment #14 June 20th, 2024 at 5:52 pm
This is purely anecdotal and subjective, but I am stunned by the number of fellow late genX-ers struggling with cancer in recent years (i.e. in their late 40s-early 50s).
Comment #15 June 21st, 2024 at 3:24 am
I remember that 2003 theory lunch very well! I thought you were great and I loved the drama and embarrassment around it…
that period at Berkeley was beautiful, and when I think back I am reminded of one of Luca’s lovely blog posts on the dreamy eyed alumni.. https://wp.me/p3rOf-w
Comment #16 June 22nd, 2024 at 9:16 pm
I was only two days ago singing his praises to physicists at the Santa Fe Institute, lamenting that a few years ago he and I attended a workshop there on thermodynamics of computing, but without the progress I had hoped for… I mentioned him this past week because the discussion at this week’s workshop involved one-way functions, expander graphs, pseudorandom generators, derandomization, and other topics where Luca would have been the perfect person to step in and shine light on our confusion. RIP, Luca.
Comment #17 June 23rd, 2024 at 10:03 pm
“Cancer is a bitch”
It is. I’m dying of it; one problem is that the FDA slow-walks potential treatments, delaying them by years while the Lucas of the world die: https://jakeseliger.com/2024/01/29/the-dead-and-dying-at-the-gates-of-oncology-clinical-trials/
Comment #18 June 24th, 2024 at 2:28 am
jseliger #17: Yes, while I can’t speak to the details of Luca’s case, in general that is absolutely true. I’m a huge supporter of right-to-try and of faster clinical trials. And I hope you get what you need in time.
Comment #19 June 24th, 2024 at 4:19 pm
As far as I’m concerned, dying of cancer wouldn’t be such a dreadful prospect if this country (the US) at least gave the dying the option to just ‘bow out gracefully’ once the progression of the disease has become too hard/horrible to bear (for the dying and his loved ones too).
How fast/easily one will die from his cancer by “letting nature take its course” is in itself an extra lottery on top of the lottery of getting the the disease itself.
Comment #20 June 25th, 2024 at 12:23 am
Fred #11 and others :
Is there a blood test to detect if I have microplastics in me?! That’s a point the innumerable articles on microplastics never seem to bring up. Thanks
Comment #21 June 25th, 2024 at 8:41 am
@Qwerty
I doubt there’s any blood test available wildly, it’s all research
https://www.sciencedirect.com/science/article/pii/S0160412022001258
and, anyway, everybody has them (it’s not clear what the problematic levels are).
Maybe you could try limit your exposure by eliminating plastics from your environment (e.g. plastic bottles, plastic containers, …), and use good water filtration systems… but apparently they’re also in the air and in the entire food chain. But I doubt it’s clear what the main sources are and even what the exact effects on health are.
Like the fight against Global Warming, it’s something that is beyond a single individual and has to be coordinated at a large scale.
Comment #22 June 25th, 2024 at 10:25 am
Qwerty #20:
I am going to guess no.
If you could spot some in your blood, that would be a positive test. But there are many kinds of plastics, and many sizes of microplastics, so a negative result would be hard to establish.
Comment #23 June 25th, 2024 at 4:22 pm
A related rant for Qwerty and all;
EVERYONE should avoid drinking water or anything else from plastic bottles unless there is a compelling reason to do so.
In most places in the world tap water is better in all respects than bottled water. Bottled water costs much more; and is usually just some other tap water (maybe filtered) that has been sitting for weeks, months, or years in plastic; leaching out plasticisers, other poisons, carcinogens, and who knows what; while also getting stocked with microplastics.
There is also the issue of making and disposing of thousands of tons of plastics for no reason.
I have no clue why so many people think this is a good idea.
Comment #24 June 26th, 2024 at 9:50 am
Not a plug, but maybe look into reverse osmosis water filtration systems, like
https://www.amazon.com/gp/product/B0BGK3YLTN/ref=ppx_yo_dt_b_search_asin_title?ie=UTF8&psc=1
Comment #25 June 27th, 2024 at 12:40 am
Only tangentially related to this touching post, but:
Scott if a layperson with only (vaguely remembered) high school math wanted to self teach quantum mechanics and computing (and relevant prerequisites) to the point of being able to meaningfully contribute to those fields, where would one find an appropriate syllabus?
Comment #26 June 27th, 2024 at 12:59 pm
Truly a tragic loss. I only had a few interactions with him as someone who’s an outsider to computational complexity but trying to learn, and he was really kind and helpful. He wrote beautifully and made enormous contributions to the field, it’s so sad he was only given 52 years on Earth.
Comment #27 June 27th, 2024 at 1:39 pm
Fred #24:
Is that reverse osmosis filter going to avoid the problem of adding microplastics into the water? Or does it also have plastic parts through which the water has to pass?
To the other commenter Patrick Lutz #13 who wrote about the 5 minute break he was given by Luca…that was an amazing story. It painted an amazing picture of this person I’ve never even heard of before.
Comment #28 June 30th, 2024 at 2:39 pm
Quantum dreams #25:
https://sheafification.com/the-fast-track/ has a collection of excellent mathematical physics texts. However, this list is optimized for becoming a mathematical physicist, not for rapidly reaching the frontier of QM and Quantum Computing.
Scott, do you think you’ll write an obituary about Luca’s impact on complexity theory/cryptography as a whole?
Comment #29 June 30th, 2024 at 3:16 pm
Quantum dreams #25: To get from layperson to active quantum computing theorist is gonna be a journey … are we starting with a working knowledge of linear algebra? Probability? Classical algorithms and programming?
If so, you could try all the free lecture notes available on the websites of (e.g.) Umesh Vazirani, John Preskill, or yours truly! Or Quantum Computer Science: An Introduction by N David Mermin, or the Nielsen & Chuang (“Mike & Ike”) textbook, or my own Quantum Computing Since Democritus. Good luck!
Comment #30 June 30th, 2024 at 3:18 pm
I #28:
Scott, do you think you’ll write an obituary about Luca’s impact on complexity theory/cryptography as a whole?
I feel like there are others (Salil Vadhan, Alon Rosen, Andrej Bogdanov…) who could do justice to such a project much more expertly than I could.
Comment #31 October 24th, 2024 at 9:17 am
A very interesting discussion on cancer.
I skipped to a part where micro-plastics are mentioned, but it’s worth listening to the whole thing.
Comment #32 June 9th, 2025 at 8:02 pm
[…] a new theoretical computer science prize, in memory of my former professor (and fellow TCS blogger) Luca Trevisan, who was lost to the world too […]