Interview with Ryan O'Donnell

Ryan O'Donnell is an Assistant Professor in Carnegie Mellon University’s School of Computer Science.  Originally from Canada, he completed his Ph.D. at MIT before coming to Carnegie Mellon in 2006. His research interests include analysis of Boolean functions, hardness of approximation, complexity theory, property testing, and probability.

Interviewed by Alissa Briggs, senior CSD, and Linda Cai, junior CSD

Where did you grow up?
I grew up in a city in Canada called Oshawa, maybe 50 km away from Toronto. I went to college at the University of Toronto and then went to grad school at MIT.

When did you come to the US from Canada, and what was the first major difference you noticed between the two places?
This might annoy Canadians since some Canadians like to define themselves by how they’re different from Americans, but I think the two countries are pretty similar—I wouldn’t notice the difference travelling across the border. People’s accents are slightly different. I’ve tried to cultivate an American accent. A lot of Canadian professors at Toronto were actually Americans; they tried to say ‘Zed’ instead of ‘Z’, because that’s what most Canadians do. I tried to be appreciative of that, though I still say ‘corollary’ a little differently. I’m still working on some of them, like ‘orange’ and ‘sah-rry’ vs. ‘SO-ree’.

How have your academic interests evolved since you began your undergraduate studies?
Going into the University of Toronto, I thought I mostly liked to do math, although I liked programming too. I took a lot of math and CS classes. I didn’t really know what I really liked until my last year there, when I took a class on computational complexity. Still, I only applied to math departments for grad school. It’s nice at MIT because you can do CS theory in the math department, which is what I ended up doing. But when I first got to MIT, I thought that maybe I liked pure math, so during my first semester, I took some algorithms and commutative algebra classes.  The algebra was super boring – I couldn’t stand it! But the algorithms classes were great. After that, I didn’t look back on pure math, and did CS theory instead. I still keep up with a lot of math topics, but I guess it’s more a form of self-study.

How did you decide to come to CMU?
My reason is probably the same as yours. It’s the best school that you got into! But it’s also arguably the best school, so given that you got into it, of course it’s the best one you get into. When I was looking for jobs, I applied to 30 different places that were hiring. My wife wanted to go to business school, so we also had to take that into account and choose a place with a good business school. I got a couple offers, and ended up coming here. My wife did her MBA here for a couple years at Tepper, and now works at McKinsey.

Did you always think you would teach?
I guess maybe. I always knew I liked working on math and CS research.  I eventually realized that the only way to do this as a career is try to become a professor somewhere. I didn’t mind teaching, and I kind of knew it was the more likely career path. I wasn’t quite thinking about this since high school, since I was kind of young in high school, but once I began college I knew liked math and CS for real and that this is the path I wanted to take.

Which is your favorite class to teach?
Probability and Computing is my favorite undergrad class to teach; I’m teaching it for the second time now. This is actually the only undergrad class I teach. I kind of like it because I’m sort of a math person at heart; the class is at least half math, and it’s also a sort of an elective course so most people who take it are actually interested. Also it’s a great topic—definitely underused in CS.
The first class I taught at CMU was Fourier Analysis of Boolean functions, which is my main research area. It was cool that CMU let me come in and teach a topic I was interested in. Also, I got to create lecture notes about the topic so it was cool to gather all the info I knew into one location. I might teach this course again one year from next spring.
Another class I’ve taught is Advanced Approximation Algorithms. I co-taught it with Professor Anupam Gupta. Gupta’s research is about coming up with efficient algorithms for Approximation problems. My research is the opposite, showing that there are no efficient algorithms. We thought it would be cool to teach a class that presents both sides of the picture and asks questions like “What are the best algorithms, vs. what are the best NP completeness results?” and “How does thinking about algorithms help thinking about NP completeness?”

What’s your favorite thing about CMU that distinguishes from places you've been previously?
I’ve only been at 2 other universities so that’s a tough question. What is good about CMU that distinguishes it? The students are really smart, and that’s awesome. Also, I feel like the students are a little more laid back, a little happier, maybe not quite as egocentric as at other schools. There’s a good vibe from students, and it’s really nice to interact with them.

Do you have any mentors at CMU?
Here at CMU, it’s really nice because everyone in my theory group is very friendly and helpful. When I first came here, I probably learned the most from Professor Gupta, and oddly enough from Professor Von Ahn even though he started 1 month after me. He had been here for 8 years, though, so he knew everything about CMU. When I had questions about how CMU worked, or how to run classes, I invaded their offices and asked them for advice. They were always very helpful.

How do you approach trying to solve a hard problem?
Most of what I do is sit around and fail to solve problems. Usually I have several hard problems to do at once and I’m sort of stuck on all of them. Yesterday I was flying from San Francisco and had a good four hours to just sit down with math problems, so I sort of daydream about the problems. 50% of the time, I can’t come up with anything. The other half of the time, I might make 5% progress and come up with an idea that makes the problem seem a bit easier. Hopefully, I’ll eventually complete the problem. It’s unlike in some other areas where you know how to build a system and can estimate how much time and resources will be needed. You can’t really plan ahead for this type of research. You might be stuck forever, or occasionally, you’ll just try to solve it, and solve it in one day.

What do you think are the most fascinating applications of your research?
That’s a tough one. I will confess that my research is pretty theoretically slanted and thus it doesn’t have immediate practical applications. I sometimes like to tell people about my research, and what often surprises them is that you can prove with pen and paper that you can’t solve some problems with a computer because your computer won’t be able to run fast enough to solve them.  People ask, “But what if you just need a faster computer, or a smarter computer?” You can just prove you can’t on paper. You can also come up with faster algorithms for e-commerce, or faster algorithms for factoring that totally change the world.

Tell us a little about your interest in Crossword Puzzles.
The New York Times crossword puzzles work on a free submission model – anyone can submit them. While at MIT, one of the favorite pastimes of the grad students in my theory group was to try to solve the crosswords in the NY Times. Every Friday, during lunch, we would get together and collaborate on what was usually the hardest puzzle of the week.
After doing this for a while, my friend David, who is now a professor at Carleton University, asked how long I thought it must take to make these. I said that it couldn’t be that hard, so we decided to try it. Like research, it was collaborative effort. Our first puzzle really sucked, but the next time, we tried really hard and it came out satisfactory and got accepted. We made one more after that. Actually, David went on to write many more, but I was sort of out of ideas at that point. Now I can say that I’ve been published in the NY Times!

Do you have a favorite computer scientist or mathematician?
There is one mathematician—Terry Tao, who’s become famous recently because he won the 2006 Fields medal. I think he has a cool taste in problems, from differential equations, to CS stuff like property testing. The set of problems he works on are really interesting, and his most interesting results regard prime numbers. What is also is amazing is that he has an awesome blog. He posts a lot, which I think is hard to do. I tried to guest blog on another site for a while, but it was hard to always think of things to say! Terry’s blog has long expository articles about problems he’s trying to do, which actually make you understand the problems. His time management must be awesome too, because he makes these really well written page-long posts every day, but also produces papers constantly.

Who is the most famous person you’ve ever met in-person?
I lived in Times Square in Manhattan as a postdoc for 9 months. When I moved there, I was really excited to potentially see celebrities wandering on the streets. Everyone I knew who lived or worked there always saw famous people like Sarah Jessica Parker, or Will Smith, or whoever. But I never did! In the first 8 months and 29 days, I saw Philip Seymour Hoffman, but he’s not really that famous, so he doesn’t count. Then finally on my last day, I saw David Cross, the guy in Arrested Development, sitting in a café that I usually went to. But I was too shy to say anything to him.
I also think I saw the main actress from Amélie sitting in a café once. The friend I was sitting with didn’t know who Amélie was, but I think she looked just like her, and was talking in French to her friend. She dropped her scarf and I picked it up for her, so it was almost like I met her! I tried to look up later if the actress had been in Manhattan at the time, but I couldn’t find any evidence. Really, I haven’t met anybody famous, sadly.

How about in academia? For example, did you meet Erik Demaine while at MIT?
Yeah, I know Erik Demaine. I was a student when he was job interviewing to be a professor at MIT. It was kind of funny because I went out to one dinner or lunch and he was only 20 at the time so he couldn’t drink alcohol, which is typical feature at these things. I wasn’t sure about him at the time. He always had strange publications about building little puzzles and origami. I thought, “Is this guy for real?” Then, when I got to meet him, I realized he’s pretty awesome and does some cool work in data structures.
MIT also has Rodney Brooks, who builds robots and starred in an Errol Morris movie, called ‘Fast, Cheap & Out of Control’ – but I never met him.

Where is the best place you’ve ever visited?
Right before coming to CMU, I lived in Seattle. In the summer between moving from Seattle to Pittsburgh, my wife and I took 2-month trip to Asia. We went to Southeast Asia, Thailand, Laos, China, and Turkey. We saw many amazing sights along the way. We both like cities a lot – Hong Kong and Kuala Lumpur were some favorites. Also, while travelling we realized that though many cities advertise themselves as a UNESCO World Heritage site, UNESCO actually hands out tons of these. There are really thousands and thousands of these places!

What types of art or music do you enjoy?
I used to listen to a lot of music, but not quite so much any more. Same goes for movies. Now I primarily watch TV, which is really a good artistic medium. There are a lot of great shows on TV. I like some competitive reality shows, like Amazing Race, although the American version is watered down and the tasks are easy. My wife and I discovered there is an Amazing Race Asia, in which the tasks are infinitely more difficult than in the American version. We like to watch that. I also like Bravo reality TV shows, like Project Runway and Top Chef. Also there’s Colbert and John Stewart, sort of the standard TV shows. The Office, 30 Rock, and sports—the Penguins are starting up again!

Are you a big hockey fan?
Yes – it’s one stereotype of Canadians, but yeah, my favorite team is the Toronto Maple Leafs. As long as they’re not playing the Penguins, I’m happy to root for the Penguins too.

What do you like to do in your free time?
I really like to explore and try out different restaurants. My favorite Pittsburgh restaurant is Il Pizzaiolo. It’s a pizza place in the far reaches of Pittsburgh. I first went there with one of my friends who’s a pizza gourmand, and we agreed that the restaurant had some fantastic pizza. Closer to home, I like a restaurant called Point Brugge and the Rose Tea Café in Squirrel Hill.

Do you have any other hobbies?
I guess learning Turkish, my wife’s first language. I’ve been trying to learn it for five or six years now. It’s pretty hard. It’s a lot like when you audit a class. There are all these books you just read but you skim over the actual homework, and never do the practice questions or anything. It’s like reading a math textbook, when you start reading and kind of know what’s going on, but halfway through, you suddenly realize, “I don’t understand what’s going on.”
When you don’t have a teacher, it’s hard to force yourself to learn another language. My wife is trying to help me learn it, but it must be frustrating for her because she speaks in perfect English so we’re conversing in a glacial pace when we speak in Turkish, when we could just speak in English so much more quickly. The main thing that works really well is to talk about people on the street in Turkish, which I’m a little embarrassed to admit. But we have to be careful – most Pittsburgh Turkish speakers live in my neighborhood in Squirrel Hill. I did get quasi-busted once: when my wife and I were waiting for a table, I said something innocuous in Turkish. The person next to us turned around and started talking in Turkish. I panicked, and retraced our conversation. Luckily, we hadn’t said anything bad!

Do you have any advice for CMU grads or undergrads?
My advice is to try to stay a student for as long as possible. At least for me, it was a really fun life. Working at a regular job kind of sucks, but my job is great because I’m still kind of like a student. I can do whatever I want, and I don’t have a boss. Being a student is a fun life – you can go to classes, have freedom, and free time. Lots of interesting things are always going on. I’m not saying that undergrads should stick around for 8 years and not graduate. I was an undergrad, a grad student, and then a postdoc for three years, so that was great.

What is one of your life goals?
Take more vacations! I’ve taken too few. I travel a lot for conferences, but that doesn’t always feel like a vacation.