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.

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

ReplyDeleteThumbs up!

ReplyDeleteJust curious: Did you conduct this interview in person, record it and then transcribe it, or over email?

DeleteWe 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.

DeleteI 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.