Farewell to Luca

by Venkatesan Guruswami, Nikhil Srivastava, and Kristin Kane

We are heartbroken by the untimely loss of Luca Trevisan, who served as senior scientist at the Simons Institute from 2014 to 2019. Luca passed away on June 19 in Milan at the age of 52. His husband, Junce, was at his side along with a few other loved ones, notably our colleagues Alon Rosen and Salil Vadhan, who accompanied him in his last difficult months. Luca leaves behind a rich and diverse legacy of influential results, the Trevisan extractor being a masterpiece highlight.

An only child, Luca was born and raised in Rome, where as an adolescent he spent many long afternoons reading books about mathematics. He loved to cycle to Villa Ada or along the river Tiber, and was passionate about film — in particular Mel Brooks’s Young Frankenstein, and films by Monty Python and Woody Allen. In school, Luca earned the highest marks, but he was particularly precocious in mathematics. Luca’s lifelong friend Flavio Marchetti recalls, “I’ve often spoken about Luca with our high school mathematics teacher Daniela Crosti … and we joke about Luca’s questions, which frequently turned into extemporaneous original demonstrations in which he arrived at the answers by reasoning together with the class, without any advance preparation.”

As an undergraduate at Sapienza University in Rome, he became the first student to graduate from the department of information science. An article about the event in the Roman newspaper Il messaggero from July 20, 1993, sheds some light on Luca’s youthful personality. Luca’s mother, Giuseppina, described him as calm, disorganized, and not very well equipped to deal with practical matters. Friends remarked that he drove like a madman and was a danger to public safety, but had a great sense of humor. 

After receiving his doctorate from Sapienza in 1997, Luca went on to postdoctoral positions at MIT and DIMACS. He then served on the faculty of Columbia, Berkeley, and Stanford, before taking a position as the Simons Institute’s senior scientist in 2014.

As senior scientist at the Simons Institute, Luca oversaw the Institute’s postdoctoral training program, mentoring a generation of rising stars in the field. He also spearheaded a research program on Pseudorandomness in Spring 2017 and brought several other successful research programs to the Institute through his outreach to potential organizers. 

“There is no question that Luca significantly elevated the intellectual climate in the theory group at Berkeley,” remarks Simons Institute Founding Associate Director Alistair Sinclair, “and did so moreover with great humility and a disarming sense of humor. His ability to distill the essence of a huge range of mathematical ideas, and generously share his insights with others, through his blog and elsewhere, was a truly rare gift. It was a major coup for Berkeley to bring him back from Stanford as senior scientist at Simons. His advice and words of wisdom were invaluable during the endless rounds of decisions we faced in the early years of the Institute.”

In 2019, Luca returned to Italy to help launch the new Department of Computing Sciences at Bocconi University in Milan. At Bocconi, Luca held the Invernizzi Foundation Chair in Computer Science and cofounded and directed the two-year master of science in artificial intelligence, which was launched in Fall 2023.

Simons Institute Director Shafi Goldwasser recollects, “I overlapped with Luca at several stations along the way. I recall Luca as a young Italian postdoc who arrived at MIT, quiet and deep with an engaging smile, who surprised us one day with his extractor result while we were all occupied with PCPs. A few years later we had a pivotal conversation in a café in NYC when he was laboring over the decision to move to Berkeley; more than a decade passed before Luca welcomed me back to Berkeley, where he already was a senior scientist at the Simons Institute and his eloquent descriptions of ‘scientific pearls’ that arose in the programs were second to none. And finally a few months ago before any notion of illness was in the air, at dinner in Milan at the truly beautiful home he built for himself and Junce. I cannot believe we shall not meet again someday, somewhere.”

In the course of his career, Luca made beautiful contributions across the theory of computing, spanning pseudorandomness, approximate optimization and PCPs, property testing, spectral algorithms, and, in recent years, distributed computing. Luca’s PhD research in the mid-1990s focused on approximability and included two very elegant non-approximability results: one showing that the doubly exponential dependence on the dimension of the approximation schemes for Euclidean TSP was inherent, and another that provided a systematic LP-based framework to discover gap-preserving gadget reductions and argue their optimality. By the time he received his PhD, Luca had become an expert on the then rapidly evolving PCP literature. (Speaking of Luca’s PCP works, I (Venkat) was fortunate to coauthor my first paper in graduate school with Luca, which included a 3-query PCP with optimal soundness error.)

Among Luca’s varied contributions to PCPs is a line of work that culminated with PCPs with the best bang for the buck for queries made, asymptotically yielding an almost factor-two gain in soundness for each additional bit queried. The final paper in this series, from 2006, brought in tools from additive combinatorics like Gowers norms into the purview of TCS. Luca had a real knack for identifying directions in math with fruitful connections to complexity theory (and vice versa). As another example, he found two-way connections between dense model theorems that play a central role in the Green-Tao theorem on arbitrarily long arithmetic progressions in primes and the hard-core set theorem in complexity. 

Luca was a true intellectual leader of our field. One way was of course through his many landmark theorems — for instance, his instant classic work connecting randomness extractors to pseudorandomness generators. Its underlying key insight, relating certain proofs in the computational world to information-theoretic counterparts, was a true gem, something so natural in hindsight yet never realized by the community. Another example is his more recent work generalizing Cheeger’s inequality to k-way cuts. These are the kind of results that will matter as long as our field exists. Reading their beautiful proofs, there is an inevitability about them that makes them hard to unsee. 

Luca had an uncanny ability to quickly identify the significance and potential of a new direction when he saw one. He would comprehend the essence of the first paper on a topic at great depth, write a beautiful follow-up filled with insights that clarified and improved matters, and in turn inspire further follow-ups and progress. He did this repeatedly, on diverse topics, ranging from hardness amplification to Unique Games algorithms. This is best articulated in Luca’s own words in his blog post “On being second.”

Beyond his research prowess, Luca was a leader in another (more subtle) way, which is no less important. As a teacher and expositor, Luca awakened curiosity in others. In his many survey articles and lecture notes, he gave us the crispest expositions of many canonical results in theoretical computer science. His way of explaining was generous, making full use of his intellect but keeping it in the background. His writings made theoretical computer science seem approachable to me (Nikhil), as a graduate student outside one of the big theory groups. Both of us (Nikhil and Venkat) regularly benefited from Luca’s notes for our teaching — he had a gift for distilling advanced material in an engaging style perfectly tuned and packaged for lectures; in fact, we sometimes picked topics to lecture on because Luca had notes on them! 

On his blog, in theory, in addition to his lecture notes, Luca also shared with us what he was learning. This included topics such as zeta functions, manifolds, and other objects not so familiar to the TCS audience. It was an invitation to expand our imagination, and a reminder that it’s okay to just learn something for its own sake. In person, Luca had a way of asking simple questions and then exploring them with clarity, devoid of any hint of competition or rush. Talking with him was a gentle invitation to wonder. He shared his questions and insights generously, and repeatedly went out of his way to collaborate with junior people, not even necessarily his students, including us. We doubt that our journey with Luca is unique. He represents what is best about our field: its openness and the generosity of its leaders. We hope that Luca’s way will forever remain alive in our community.

As a faculty member for over 25 years, Luca was a beloved mentor to many students. He both collaborated with them on influential results, and inspired them to grow as fearless researchers with their own ambitious agendas. 

On a personal level, Luca was one of the out, gay theoretical computer scientists who have helped make this community a welcoming one for LGBTQIA+ researchers and students. He recounted his coming-out in 2000 in a characteristically humorous (and now legendary) blog post in honor of the Turing Centenary.

He was a fellow of the ACM, a member of the Italian National Academy of Science, and the recipient of the Oberwolfach Prize, a Sloan Research Fellowship, an NSF CAREER Award, and an ERC Advanced Grant. At the time of his passing, Luca was a member of the ACM A.M. Turing Award Committee. 

Luca was a brilliant scientist and expositor, and unfailingly funny friend and colleague. His clarity and insight deepened our understanding, and advanced the frontiers of research in the theory of computing. Luca leaves behind an enduring scientific legacy. He will be sorely missed.