Wednesday, August 29, 2007

Theory Starts Here! (Informatics Olympiad)

(Guest post by Mihai Patrascu)
A while ago, I promised the community around the International Olympiad in Informatics that I would bring them into the conscience of the theory community, and now I am trying to fulfil this promise. I have written a short " practical guide " of what we, as the theory community, should know and why we should care. Below is your executive summary:

Understand. What happens when you cross homo ludens with scientists? Imagine the Olympic Games, where you throw Computer Science into the arena. In short, you ask each country to send their best 4 high school students, who then compete in solving algorithmic questions.

Appreciate. The problems given in the contest are meant to challenge the brightest young minds in Computer Science. For a quick reference, problems in [CLRS] are "easy". Many questions asked are truly original, and thus can be fun even for a mature audience. Many questions can also make excellent assignments in algorithms courses (with or without a programming component).

Care. Informatics Olympiads are part of our intellectual tradition, and a part that should make us proud. The parallel olympiad in Mathematics is highly regarded in that community. A theory community that embraces the Olympiad is a stronger theory community.

More practically, the Olympiad gives us outreach to the high school level for free. We need a healthy flow of new talent, and the olympiad is already motivating hundreds of the smartest kids to learn theory. Our awareness can tell them that they are on the right path.

Most practically, we should be paying attention to it in the admissions process. The International Mathematics Olympiad, which has been running since 1959, has had a very significant impact on theory.

Our very own Informatics Olympiad is much younger (1989) and the contestant are only now coming of age. However, check out this list for notable theorists coming straight out of the Olympiad. If you want to know how well people are doing on average (and be impressed!), check this out. It is a statistic about the career paths of all Romanians who ever participated in the Olympiad.

12 comments:

  1. These Olympiads are the closest thing to a global yet reliable IQ test.

    For students applying to grad school, a medal in one of these Olympiads would probably be taken more seriously than anything else on their resume.

    ReplyDelete
  2. For students applying to grad school, a medal in one of these Olympiads would probably be taken more seriously than anything else on their resume.

    And that's why most of them are students at MIT. I would say that while IMO/IOI medalists represent the cream, students who pass the USAMO, Balkan Math Olympiad, Indian National Math Olympiad, and other regional olympiads are equally good.

    ReplyDelete
  3. Let's not scare people. There are plenty of us who didn't excel at Olympiads yet still turn out to be decent theorists.

    ReplyDelete
  4. For students applying to grad school, a medal in one of these Olympiads would probably be taken more seriously than anything else on their resume.

    Not more seriously than solid previous research.

    ReplyDelete
  5. The mathematics community already takes the IMO a little too seriously (although most mathematicians really don't care much about it). The theoretical CS community shouldn't make the same mistake with the IOI.

    These contests can certainly have wonderful effects, challenging and inspiring bright kids and bringing them into contact with other. On the other hand, we shouldn't discount the negative effects: some kids who don't do well can feel discouraged and give up, and some kids who do well can become arrogant and overconfident.

    ReplyDelete
  6. I knew a bunch of IMO people in high school/college. (No, I never made the US team, but I did get to go to the summer training session once.) Some went on to be mathematicians of varying success, but several got off the train and went into business (Wall Street type stuff) or programming. Many seemed to suffer math burnout at some point in college -- even the ones that eventually became mathematicians.

    An IMO medal clearly means you're smart, no denying that. But I've heard the complaint that it demonstrates more about one's training than one's creativity. After all, in a contest, you're given a problem that you know you're supposed to solve in a very limited amount of time. In research, patience and the ability to choose problems are in my opinion more important than raw brain-power, never mind other contest-untested skills such as the ability to work well with others.

    So if I see an IMO medal on a grad application, I know the person is smart. But that's certainly not the only way to determine whether a person is smart. And smart is only one variable in research success.

    ReplyDelete
  7. An important aspect of these contests is not just the (small number of) international winners; it is the much larger number of people who get turned on and challenged by the various contests that are used to select representatives within each country.

    Personally, if it hadn't been for math contests in high school it is not clear that I would thought of choosing my current career. They led me to become a math undergrad. Later, I was turned on to CS theory in my last undergrad semester because its discrete problems seemed to have more of what I liked about those high school math contest problems. (My attraction to CS seems fairly common: Canada didn't send teams to the IMO at the time but 3 of the top 5 on the Canadian Math Olympiad ended up as CS profs.)

    Of course not everyone with an ability to solve puzzles for which a solution is known have ability in open-ended research. Conversely, there are many others with an ability in research but no patience for solving puzzles. Time limits make any such connection worse. However, though the use of such contests as methods of selecting talent may be questionable, this is a matter of good PR for the field and we shouldn't underestimate its value.

    ReplyDelete
  8. One of the things needed to be a good researcher is smartness. A medal in IMO implies that you certainly have some level of smartness.

    That is where the correlation ends.

    ReplyDelete
  9. National competition problems and later IMO training stimulated my interested in math immensely when I was young. The IOI didn't have that effect as I already liked algorithmic problem solving when I heard about it.

    Participating in the IMO was fun but also gave me a serious reality check. I didn't medal, and when I saw how good the best were I understood that maybe math wasn't for me (especially as problem solving was and is my strongest side). Ultimately I got a PhD in theory.

    The aftermath: 4/6 of my IMO team now have PhDs, and the best of us dropped out of grad school after suffering from serious math burnout. He's now a medical doctor. 3/3 of my IOI team got PhDs in CS; two of us in theory.

    ReplyDelete
  10. Participating in the IMO was fun but also gave me a serious reality check. I didn't medal, and when I saw how good the best were I understood that maybe math wasn't for me (especially as problem solving was and is my strongest side). Ultimately I got a PhD in theory.

    From http://www.acm.org/crossroads/dayinlife/bios/richard_karp.html:

    "As an undergraduate at Harvard I took classes with a future Nobel Prize winner and a future Fields Medal winner. I concluded that I could not compete with them in pure mathematics, and pursued computer science instead (although that name for the subject had not been invented yet). Computer science has offered far more scope for my abilities than pure mathematics would have offered."

    ReplyDelete
  11. Doing good at Olympiads shows smartness, good training and familiarity with the techniques used. At least I feel this is so with IMO. I was myself a part of the INMO [Indian National Math. Olympiad]. With IOI I feel, its a little different. Theory CS algorithm problems mostly do have

    1. Very easy very inefficient solutions.
    2. Reasonably hard good solution.
    3. Very smart and very efficient.

    With IMO I see if u find the solution its either

    1. Very very messy
    2. Very elegant.

    In case you did (1) you would probably know that right away and would try finding (2). With IOI knowing between 2 and 3 requires some intuition. Its more the kind of thinking one does in research.


    For myself, I do not think doing good at IMO really means a lot regards being a good Math researcher. As far as IOI is concerned, and I repeat I just got familiar with them, I think it may mean that you have good research talent.

    ReplyDelete
  12. I took part in IOI from a small poor country - where we dont have any training camp or very good support.

    When i participated in IOI I really envied the others very much - they have the proper background thats needed - while I was mostly trying to find something in the darkness.

    Sometime it really hurts to see people - to get proper support and turn out to be very successful. While I just never had them. :(

    ReplyDelete