The Simons Institute is pleased to announce the appointment of Luca Trevisan as our first permanent Senior Scientist. Luca rejoined UC Berkeley this fall, with joint appointments at the Simons Institute and Department of Electrical Engineering and Computer Sciences, and the Department of Mathematics. He comes to us most recently from Stanford University, where he was a Professor of Computer Science. He has also held posts at Columbia University, MIT and DIMACS, and earned his Ph.D. from the Sapienza University of Rome, under Pierluigi Crescenzi.

Full Transcript

CP: Luca, welcome back!

LT: Thanks. It’s good to be back here.

CP: So, how does it feel to be back?

LT: It feels a little like when I go back to Italy. And everything is good, and people are great…

CP: The espresso’s better.

LT: The espresso’s good, yes. But things are a bit complicated.

CP: Yes, we do complexity here.

LT: Right.

CP: We have known each other for the longest time, right? You were an undergraduate when I first met you in Italy.

LT: Yes.

CP: I spent a sabbatical in Rome and there you were. I was really amazed to meet you. I have a good eye.

LT: Yes, I was a senior in college. And you knew my advisor, who I guess was your postdoc at San Diego the year before. I had a really great time doing a somewhat research-oriented senior thesis. And I didn’t get any offer of a real job after I graduated. So I went to grad school.

CP: Great.

LT: That seems to have worked out pretty well.

CP: At some point, you started working at IBM.

LT: Yes. Pilu Crescenzi, my advisor, he also knew Madhu Sudan, who was at IBM at that point. And in my second year of grad school, as was pretty common for students in my program, I was looking for somewhere to go to and spend a period abroad. So I wrote to Madhu to say that I would like to come to IBM and visit, and the Italian government would pay for the visit. And Madhu was happy. This was off-season, so not in summer but in the fall, where they don’t have a lot of students in general. And they were always happy to have someone new. And so I went. And very luckily, just a few weeks before going, I was reading this paper on PCP and hardness of approximation that Mihir Bellare and Oded Goldreich and Madhu had just put online. It was a 120-page paper. And it was the first time that a lot of those new ideas on how to go beyond the original PCP construction and get stronger results were written down with all the details. And I’d been thinking about one section where they show how you do reductions from PCP to optimization problems with gadgets. They had a very abstract way of thinking about that. And I was thinking that it should be possible to search for an optimal gadget automatically.

CP: Right. So this is where this idea came from. Okay, right. It was made in Italy. (Laughs.)

LT: Indeed. So I flew to New York with Alitalia. And they lost my bags, with all my stuff. And I then had to get a car to get to the IBM lab, which was a bit outside of New York City. But I was not 25, so I couldn’t rent a car. And so my first day there, with no clothes and no house and no car, but, still, I had this idea. And I told Madhu, and he immediately got it. And then the following day, he basically reexplained the idea to me, but much, much better.

CP: Wow.

LT: Then we talked to Greg Sorkin and David Williamson, who showed how it could be extended to other problems. So in a few days, we had a pretty nice piece of work.

CP: Great. You kept working with Madhu after that – or not?

LT: We stayed in touch. Just before I left, we were starting to work on a classification of constraint-satisfaction problems.

CP: I see. Yes, of course.

LT: Then I ran out of my graduate fellowship. Which, the way it was working in Italy at that point (or not working) was that the fellowship would run out one year before you would actually graduate. Or sort of the time it took to get together the graduation bureaucracy took a year after that. So I spent that gap-year in Geneva. And I started to work on pseudorandomness and extractors.

CP: Yes, that was also very lucky.

LT: So finally, I got officially my PhD and I was going to spend a year again in New York at IBM working with Madhu. But at that point, Madhu got offered to move to MIT and so he told me, would you like to come to MIT instead? And I said, well, I would very much like to come to MIT instead. And so off I went.

CP: Then you went to Columbia after that year.

LT: Yes – I was originally thinking that maybe after that year abroad, I would go back to Italy. But that year at MIT was life-changing: There were a lot of great people there. Oded Goldreich was there on sabbatical, and he had a big impact on me. The students there, they were… Amit Sahai was there, Salil Vadan, Danny Lewin, Adam Klivans, Yevgeny Dodis, Tal Malkin, Daniele Micciancio, Anna Lysyanskaya…

CP: Wow.

LT: It was a great group. And in the spring semester, we did this reading group to try to understand the work of Avi Wigderson and Russell Impagliazzo that had just come out, where they were showing that P equals PPP under plausible assumptions. And we actually spent like three months on that, because that paper was building upon five or six papers from the previous ten years. We decided that we would really like to understand the whole sequence – with no particular goal in mind, because it seemed that the work of Russell and Avi was the final word on the matter. And, instead, that reading group led to a lot of new work. So Adam Klivans had this idea of applying the same stuff non-deterministically. So, independently with Dieter van Melkebeek, he proved that graph non-isomorphism is in NP, under complexity assumptions. And then I did this work on extractors and pseudorandom generators that seems to be the best thing I’ve done.

CP: Yes, well, we will be the judge, okay. (Laughs.)

LT: Salil had some improvement on that that Omer Reingold and Ran Raz also had independently. So they started working together. So Omer and Salil started working together because of that.

CP: Ran was also in that group?

LT: No, Omer and Ran were both in Israel. I told Avi about the result, and Avi told Ran, and then Ran asked for the paper, and then immediately saw this improvement, and Salil also. And that was the beginning of Omer and Salil working together.

CP: This had so much impact that even we at Berkeley heard about it, and decided to hire you.

LT: Yes. And at that point I had pretty much never been to California. And I was enjoying life in New York quite a bit. But everybody was telling me that they wouldn’t speak to me again if I didn’t accept the Berkeley offer.

CP: Really? I thought it was only us who told you that.

LT: Sure. (Laughs.) But everybody else was very adamant that I had to take this job.

CP: Amazing. That’s good to know. Great, so, that’s how we became colleagues. What I remember most fondly is this quality of intellectual leadership. That whenever there was something interesting, you took the chalk or took the marker, and started explaining to us at Theory Lunch. I learned so many things from you. It was here that you started your blog – am I right?

LT: Yes. This was in 2006. It was the first year that Andy Yao had started his institute at Tsinghua University in Beijing and one of my students, Hoeteck Wee was spending a whole year there. He was one of three American students who were there – two from Berkeley, one from MIT. So it was spring break of 2006; it was in the middle of this year. And I went to spend a week, giving a couple of talks to the students there in Beijing – talking to them and also seeing China for the first time. So this before at least I had Facebook.

CP: It was not before Facebook, but before your Facebook.

LT: Before I did, right. I’m a late adopter. So I wanted someplace where I could send friends pictures and stories of what was going on.

CP: So much to say, yes, right.

LT: So I started this blog, and I sent the link to a couple of people. By the end of the week, lots of people were reading it. So when I came back, I thought, maybe I’ll keep it running for a few more weeks and write about some technical stuff. And then eight years later, it’s still going.

CP: I was a great fan; I hope to keep reading it here… Additive combinatorics.

LT: Yeah, that was a time that it seemed that… there was this work of Ben Green and Terry Tao, where they proved that the primes have arbitrarily long arithmetic progressions. And there was a notion of pseudorandomness in that paper. They already knew that dense sets of integers have arbitrary long arithmetic progressions. And they knew that the integers that in some technical sense are almost prime, are pseudorandom in a very strong sense. And that the primes were dense inside these almost-primes. And so they had this intuition that if dense sets of integers have this property, sets that are dense in a pseudorandom sense will also have this property. So they made it work. And what I thought would be really interesting was to see if there was a way to understand what they were doing in the way we think about pseudorandomness. Which there was, and that led to a few interesting pieces of work.

CP: And what came next? You worked more on approximability and PCP? You worked on the Unique Games?

LT: Yes. In complexity theory, the two areas I keep going back to are hardness of approximation and approximation algorithms, and pseudorandomness and average-case complexity. And it was at that point that it seemed that these areas and additive combinatorics had some connection that I wanted to explore. And what I worked on next was motivated by the fact that it seemed that random walks in graphs, and expanded graphs, and properties of expanders and so on, seemed to also come up a lot in various areas of complexity theory. So I thought I would spend maybe a few months learning about spectral graph theory from the beginning, and have those techniques a bit more clear in my mind. Well, that was five years ago, and I’m still working on it, because I found that it was so much… there are so many open questions, and it’s so connected to new work on approximation algorithms, or even exact algorithms – like the work on max flow using electrical networks.

CP: Yes, that’s right. And so much that you are going to be having this semester program starting in a few days.

LT: Yes. Next week, or in a couple of weeks, we’ll be having the program on spectral graph theory, where all the people who we were hoping would come came. And it promises to be really exciting. It’s coming at the right time: There are already a lot of things that people have been developing, and it’s a good place to share them. But it also seems that there is a tipping point, and something much bigger is going to happen. And maybe the Institute…

CP: We want to be the locus, the place for tipping points. That’s what the Simons Institute, as you know, is for. Yes, right… How are you looking at your role at the Institute?

LT: You know, when I interviewed here at Berkeley, it was a bit different from the way interviews usually go. Because there everybody tells you what the place is like, and what your work is going to be like in this place. But when I interviewed here, people were asking me…

CP: You define it.

LT: “What are you going to do with this Senior Scientist job?” And I’m still not so sure. But I think that really…

CP: Let me tell you: Two years later, I have no idea. (Laughs.)

LT: Ever since that experience at MIT, with that reading group, where we were just interested in one thing and all kinds of things came out of it, I’ve really been interested in exploring new things I don’t know much about.

CP: Serendipity. Yes. I love that. This sounds like a great plan.

LT: It seems here, I can do that as a job.

CP: As a job, and very intensely. Yes, right.

LT: When new things are coming up, and try to connect with people who might be good organizers for new programs…

Related Articles:

Letter from the Director
From the Inside: Algorithmic Spectral Graph Theory
From the Inside: Algorithms and Complexity in Algebraic Geometry
Research Vignette: On Sex, Math, and the Origin of Life
Research Vignette: Quantum PCP Conjectures