Tuesday, December 06, 2005

How I Became a Theorist

Someone asked me recently how I became a complexity theorist? After all most high school students don't say they want to be a theoretical computer scientist when they grow up. Every one of us has a story. Here's mine.

In high school I wanted to be an engineer. "Using science to help society" read one brochure I saw in junior high. I applied to several engineering programs and matriculated at Cornell.

During my first semester in an engineering math class, the professor writes an equation on the board. I raised my hand "Why is that equation true?"

"We don't do that in this class" the professor responded.

I then dropped out of engineering and transferred within Cornell to the College of Arts and Sciences and started my life as a math major. My mother, convinced I would become an unemployed mathematician, talked me into a double major in math and computer science, which was a relatively easy double major at Cornell.

In my junior year, as part of the CS requirements, I took an introductory theoretical computer science class with Juris Hartmanis. I had found my calling and the rest, as they say, is history.


  1. Similar story, except I was majoring in math. In some advanced algebra class, I was watching the prof do a proof. I realized I could follow every line, but I had no intuition as to where the proof was going, and why I cared. On the other hand, Harry Lewis's automata theory course and Michael Rabin's randomized algorithms course seemed, well, so beautiful, real, and intuitive.

    I'm glad I found TCS. It just goes to show you really should experiment and try new (intellectual) things in college. Despite this, I still always, always feel I should have taken more math classes...

  2. I started as an undergrad in pure math. I asked my Calculus II teacher who had a C64 at home to teach me how to program, just for general culture (back then we had no generally available computers at the math department).

    He was a really busy higher up honcho but he agreed to teach me, provided I showed at his house on Saturday from 7:00 to 12:00am. I learned to write programs in basic, but didn't get really excited about it.

    Then one day, a classmate I liked was having problems with her programming assignment which was due next day. So I decided to read the entire book overnight and identify the bug. It was some arcane 'only-in-apple-pascal' reserved word problem. It was only then that I realized that there was great beauty (pun intended) in the world of computer science, and that the deep ideas behind CS were highly mathematical in nature.

    I completed my undergrad in pure math, but focused all my electives in CS theory: graph theory I and II, game theory, complexity I and II, advanced data structures, operations research, programming languages and grammars, numerical analysis, probability I and II, measure theory, etc.

    Alex Lopez-Ortiz

  3. I heard occasional complaints from mathematicians that they were losing bright students first to physics, then to CS. This blog's readers are not a good sample to prove this, of course.

    Is their complaint substantiated?

  4. I think it is true that *some* bright students in math go into other fields, especially CS. But I don't think there's anything to complain about. Enough number of the best and the brightest stay in math that it thrives (at its own pace). In fact, if every mathematically talented person stays in math, the market for mathematicians cannot absorb them (of course, they can become school teachers and do some good). It is actually good for everyone that some of them go into Physics, CS, Finance, etc..

  5. For me, one turn off to CS PhD programs was that there seems to be a pressure to find and advisor and start publishing immediately. This attitude seems less prevalent in math, where it is expected students will spend a fair ammount of time learning a subject area. Although its annoying that one is there mostly because universities need billions of calculus TAs, it also means there's more of an opportunity to really size up the different things you could be studying without being pressured into commiting immediately.

  6. As a math undergraduate, I liked numbers and was convinced I would go into number theory. But then, as part of the requirements, I reluctantly had to take an intro to programming course, which was taught with an emphasis on algorithms and had challenging monthly programming assignments.

    First programming assignment: the stable marriage problem. I was frustrated by my inability to prove correctness of the algorithm. (students were supposed to come up with that proof as part of the assignment).

    Second programming assignment: red-black trees. A total nightmare, with messy pointers all over the place; I was unable to finish the assignment, even with an extended deadline.

    One question asked for an estimate of the average height of a tree containing n values and was the occasion of a serious headache -- we had zero probability background and it took a while to realize that the uniform distribution was not the same as the distribution obtained after inserting n values in random order.

    Third programming assignment: quadtrees and 2-d trees. A comparately pleasurable way to explore recursive programs. I thought that that was magical and fascinating!!

    Then there were some memorable lectures on sorting algorithms. For some inexplicable reason, I thought that the n log n average running time of quicksort was the coolest thing I had ever seen.

    So, that's how I became a computer scientist, via the powerful attraction of programming, and a theorist, via trying to design and analyze algorithms for my programming assignments.

  7. During my first semester in an engineering math class, the professor writes an equation on the board. I raised my hand "Why is that equation true?"

    "We don't do that in this class" the professor responded.

    I then dropped out of engineering and transferred within Cornell to the College of Arts and Sciences and started my life as a math major.

    Lance, you're the man.

  8. I forgot to post my question that went with that: what was the equation?

  9. I would like to agree with Bryce, that Lance's response was awesome.

  10. I don't remember the equation but I do remember that when I did find out why it was true, it wasn't for any particularly interesting reason.

  11. May be, there was no such question! Lance just wrote it to make things look more melodramatic!

  12. So either it's true that Lance has a flair for fiction or that he switched to theory for an interesting reason (or perhaps both).

    But we will never know which is the case. Just like a theorem in complexity... EIP, anyone?

  13. For a change, here's my story.

    I ended up in computer science because I had done well in some IIT-JEE. The only thing I knew about CS at that time was that it involved programming which was interesting. I was happy for not having to study electrical engineering which I would have done if my rank had been a little lower. After that, some fascinating classes on algorithms and theory of computation convinced me.