Complexity theorist Luca Trevisan lost his battle to cancer yesterday in Milan at the age of 52. A terrible loss for our community and our hearts go out to his family.
The community will honor Trevisan’s life and legacy 12:30 PM Pacific Time Monday at the TCS4All talk that he was scheduled to give at the STOC conference in Vancouver. Register to watch the talk online.
Luca was one of the great minds of our field, an expert on randomness and pseudorandomness. He’s the first computer science member of Italy’s National Academy of Science. He has taught at Columbia, Berkeley and Stanford until 2019 when he moved back to his home country to join Bocconi University in Milan.
My favorite result from Trevisan is his connections between extractors and pseudorandom generators, especially as the first works on arbitrary distributions and the latter fools computationally randomized algorithms. This paper laid the framework for better bounds for both extractors and generators. I had one paper with Trevisan, where, with Rahul Santhanam, we show time hierarchies for almost all natural semantic classes with a small amount of advice.
Trevisan had his own blog In Theory full of technical course notes and wonderful stories. Bill has two guest posts on the polynomial van der Waerden theorem in Luca’s blog following up on Luca’s posts on Szemeredi’s theorem.
A few years ago Trevisan started the BEATCS theory blogs column to highlight theory blogs and bloggers. Bill and I were both highlighted in this column.
Trevisan is one of the first theoretical computer scientists to come out as openly gay and many followed. We’ve come a long way from Turing.
More remembrances from Boaz and Scott.
In 2014 Luca Trevisan returned to Berkeley and joined the Simons Institute as its first permanent senior scientist. Christos Papadimitriou interviewed Luca for the occasion.
