Wednesday, December 10, 2008

How was New York Theory Day?


Most years in the FALL there is a THEORY DAY at NYU and in the SPRING there is a THEORY DAY at Columbia. They now call this IBM/NYU/Columbia Theory Day. The website did not say which numbered theory day, but the 2004 webpage for Theory day said it was the 25th one. If they have had these every semester since then... well, you can do the math.
  1. I was GOING TO post about content of the talks. But the abstracts of the talks do a better job, so I refer you to those. Should I have stayed home and just read the abstracts? NO. Seeing someone give a talk on something does provide extra insight.
  2. What does one get out of such things? It is good to know what is going on in theory, especially in parts of theory that you are NOT working on.
  3. Why is it good? I could say you might switch areas OR you might spot a connection to your area and make a contribution OR you might get a paper out of it. While all of these are true, just KNOWING stuff is important. One tangible aspect of that is, if you are on a Program Committee you will have a better idea of the papers not in your area. Also, it helps you follow talks at the next theory day, or some other venue where their are talks not in your area.
  4. I don't expect to follow that much of the talk. But I do expect (and this happened) to get introduced to an area and get some references that I may read later.
  5. Talks are an hour long. If it's a relatively new field (e.g., on-line Ad slot scheduleing) this is good. If it's a survey talk (Joe Mitchell's talk was) this is good. If it's on a classical field that you are not familiar with and they are proving the very latest results, then a full hour is a bit much. But this is just from my viewpoint of wanting to be introduced to a field. wanting to be introduced to a field.
  6. Most interesting thing I learned: Joe Mitchell, Comp Geom from SUNY Stonybrook, has had some of his work actually used by real people in the real world. (That may be a post later.) Since I am often skeptical of the practicality of theory, I was happy to hear this.
  7. Oddest thing I learned: NYU and Brooklyn Poly-Tech are merging in some fashion. Nobody quite knows the details or what this means yet. I'm hoping it means that theory day will one day be at Brooklyn Poly-Tech which will make my train ride to theory day 15 minutes shorter.
  8. New York Theory Day is usually announced about a month before it happens. This is not really enough time to plan. In fact, I have missed Columbia Theory day in the past because I had other plans by the time it was announced.


  1. Since I am often skeptical of the practicality of theory, I was happy to hear this.

    There are numerous applications of theory, is just that most of them not make it to CCC. Here are some theoreticians, off the top of my head, whose research is being applied in the real world:

    Mitzenmacher: CISCO, Digital Fountain.

    Valiant: Load balancing networks.

    Arge, Vitter, Aggarwal: I/O model, algorithms for ladar surveys.

    Prokop, Leiserson, Bender, Farach-Colton: Cache oblivous algorithms.

    Dumitrescu, Thorup: Dynamic shortest paths.

    Cormode, Muthukrishnan: Data streams.

    Numerous graph drawing researchers, whose work is incorporated into commercial software (Tom Sawyer Inc).

    Kurt Mehlhorn: The LEDA library.

    Peter Sanders: his recent work in algorithms for information retrieval.

    Karger: Algorithms for P2P discovery (CAN).

    Rivest, Shamir, Adleman: RSA.

    Johnson, Chvatal: TSP.

    Karp: Any one of his numerous graph algorithms, pattern matchers, etc.

    Ferragina, Manzini, Grossi: compression algorithms.

    Rabin: Crypto, pattern matching.

  2. I have to admit, I also found the "Since I am often skeptical of the practicality of theory..." comment struck a funny nerve.

    If a theorist wants to do "practical" work, I think there's plenty of it out there. My understanding is that many (most?) theorists really don't care about making an impact on practice.

    So I'm not skeptical about the practicality of theory; I fear that, as an area, we've devalued it -- a point I try to make whenever I can.

    By the way, since the list you presented seems a bit excessively male-oriented, I thought I'd point out some names that popped right into my mind include:

    Cynthia Dwork: privacy/spam-fighting.

    Joan Feigenbaum: security/trust management.

    Monika Rauch-Henzinger: web algorithms.

    Edith Cohen: network sampling/summarization.

    Heck, let's throw in Anja Feldmann (she even has STOC/FOCS/SPAA papers!) and Jennifer Rexford (who I wouldn't call a theorist, but who knows practical theory) from networking.

    Finally, I'd certainly add Andrei Broder to the list of theorists whose research is applied in the real world -- Andrei's always struck me as one of the most practically-minded theorists around. (He was a bad influence on me that way.)

  3. In Cryptograpby don't forget:

    Bellare, Rogaway, Krawczyk, Boneh, and Tsudik among others

  4. This is anon 1. The list was not meant to be exhaustive, but I certainly welcome as many additions as possible. I think it is a valuable resource to have handy the next time the question comes up at an NSF budget allocation exercise.

  5. If a theorist wants to do practical work, I think there's plenty of it out there.