Monday, June 18, 2012

An interview of Avi Wigderson

Q: Do you consider yourself a Mathematician or a Computer Scientist?
A: Both. It is very clear that Theoretical Computer Science is a mathematical field. We prove theorems. The reason why we are in Computer Science is that the main mathematical object that we study is computation.
Q: How did you get interested in this?
A: In college, in computer science, the best teachers I had were in theoretical computer science, for example Shimon Even. I was also into Math beforehand.
Q: Why did you decide to do a PhD?
A: I didn't come from an academic background, but all the good students in my class went on to do a PhD, so I followed their example. Once, as a PhD student, I realized what research was, I knew that that was what I wanted to do. Dick Lipton, in Princeton, was my advisor. He's the most amazing guy. He was changing his field of interest almost every month, and I was following along and learning many things.
Q: What was your first research project?
A: An efficient algorithm to sqrt{n}-color 3-chromatic graphs. I also worked on succinct graph representations, cryptography, VLSI layout and parallel computing in collaboration with other PhD students.

Q: How do you work with your graduate students?
A: In the last decade I have been working mostly with postdocs, so I'll talk mainly about my time at the Hebrew University.
I don't let them wander off. I keep in constant touch with them. I started off as a young faculty member at the Hebrew University with an excellent group of 4 graduate students. We'd meet and talk. I like talking, as you know. They were into different types of problems, and we often learned an area together.
Q: Would you have advice for first year graduate students?
A: I would advise them to do things that they really like, things that they develop a passion for. There are students who try to find "hot" topics, others who try to find topics on which there won't be the stress of competition, but those are secondary reasons.
Q: How do you get your beginning students started with research?
A: I give them a bunch of papers in different areas that they might be interested in. Then I ask them: What did you feel? What are you most attracted to? Then we discuss the ones they liked and try to think of related problems in these areas.

Q: What makes a question a "good" research question?
A: I like a technical challenge, when the usual attempts don't work. More precisely, I like problems for which natural-to-apply techniques don't provide the answer. Then there is "taste". Taste is hard to define. I am usually motivated by some higher goal of understanding, so that the question is part of a journey towards some bigger goal to which it is potentially related. Sometimes I also simply develop trust in the taste of my friends. You know that, of course: if, say, Alistair Sinclair comes to you with a problem to work on, you'll be happy to work on it even if you yourself do not quite see immediately why he likes it or the larger context in which it fits.
Q: What is your favorite result in your own work?
A: Zero-knowledge. It's so much fun explaining it to people. It's very rewarding.
Q: Practical impact. What would you say about that?
A: It's not a strong motivating force for me. Many of the questions I study are fundamental in nature. The intellectual challenge is my primary motivation. Of course, in our field, I believe there is a strong correlation between fundamental questions and practical impact (eg theoretically defining and understanding computationally such basic notions of "secret", "knowledge", "randomness", "learning", "proof" yielded great benefits, both intellectual and practical)

Q: How much time do you spend reading papers?
A: When I was a student, I devoured journal papers. Now, not so much. After hearing a lecture, I read the paper when I want to learn a technique. Sometimes I go to a math textbook to learn a certain topic which may be useful to a research project.
Q: Do you have role models?
A: I had Dick Lipton, when I was a PhD student, of course. I also have great admiration for some people who have developed completely new models and notions, and thereby new areas of research that have changed the field: Valiant or Blum for example.

Q: You've been in the field for roughly 30 years. How has it changed?
A: It's much larger in many ways. The number of areas we study has increased a lot. Learning didn't exist. In crypto, Goldwasser, Micali and Yao had just started. Distributed computing was very limited. Few Probabilistic algorithms existed. Connections with statistical physics ideas, Monte Carlo methods, all that was not there. Mechanism design and other connections to economics did not exist. A large part of the growth was due to connections with other fields. There were also developments with subfields of Mathemetics such as analytic number theory, group theory, pseudorandomness...
A: The other way in which it has changed is the recognition by the mathematical community of the importance of the field, that just blasted. We are generating great questions for mathematicians, and they love it. They recognize that they are fundamental questions. They have to rethink a lot of what they're doing and use the computational lense.
Q: So, students have to be much more mathematicaly sophisticated?
A: Yes, but they can learn what they need. There are fantastic people in the field. The young people entering the field have phenomenal talent, both technically and conceptually. TCS is a primary field of interest for the best mathematically talented young people to go in. It is a great sign for the health of a scientific field when it attracts such talent.
Q: I actually find it a bit intimidating. How to advise students who are so talented?
A: I am not intimidated by talented people, young or old - they are great to learn from. When advising young people, age provides the advantage of experience. Sometimes we can predict which directions will be fruitful and which directions that will turn out to be dead ends (although we're sometimes wrong), sometimes we can tell which questions people will like (although we are sometimes wrong). But youth provides energy and fresh thought which can often be more important than experience and is always wonderful to be around. Our profession is among a few that allows real constant interaction with young people, and to me this is a great aspect of academia.
Q: Concretely, how did you go about attracting students to theoretical computer science?
A: Here's one method. I teach a graduate course in computer science, I open it to undergraduates, and I advertise it in the Math department. That's how I got Ran Raz, for example.


  1. Nice interview. A bit sad that he doesn't mention quantum computing in the question about the last 30 years of TCS :(

  2. Replies
    1. Just curious: Did you conduct this interview in person, record it and then transcribe it, or over email?

    2. We had lunch together, I jotted down some handwritten notes on a notepad as we were talking, and I typed them up afterwards. Any mistakes are my own. As to the absence of any reference to quantum computing, since this was an improvised conversation, it must just not have come to his mind on the spot. One should not read anything into it.

      I have only once tried to record a conversation, and found that its style was much more stilted. The old-fashioned way is more freeing, even though (or maybe because) it might introduce some errors.