Posted by: jonkatz | October 22, 2009

Top 10 theory schools?

(Is this topic overdone? Why, I don’t think we’ve discussed this issue in at least a year…)

I was asked recently to list the top 10 theory departments in the US.* For the purposes of the ranking, I mainly considered the question What are the top schools a graduate student in theory should consider attending? After some discussion with colleagues, we came up with the following 9 (note this is unordered):
MIT
Cornell
Berkeley
CMU
GA Tech
Princeton
UT Austin
UCSD
U Washington

We had a hard time choosing the 10th. Not that there aren’t other good theory schools, just that the next 5-7 in our ranking were all roughly in the same equivalence class. (I won’t tell you what those 5-7 were; I’ll let you guess them in the comments.)

Thoughts?

* Yes, this really is how the US News and World Report rankings are done, at least at the graduate level.

About these ads

Responses

  1. Stanford?

  2. Columbia?

  3. UMD?

  4. Why not just tell your client the top 9 and that the next half a dozen are roughly a tie? Any reasonable client should find that more useful than arbitrarily picking one.

  5. NYU?

  6. I agree about Stanford; they seem to have only 1 theorist these days, who is already overwhelmed with students. They continue to finish near the top of USnews theory rankings though. Why is this?

  7. Our knee-jerk reaction was to include Stanford in the top 9, at least until we thought about it a bit… That’s probably how they end up in the top 10 of the rankings. These things take a long time to change, because it’s easy for people to just use the same list as last year without thinking about it too hard .

  8. I would put Harvard before UCSD.

  9. Chicago?

  10. I am not sure that I agree with the opinion that Stanford has only one theorist. It all depends on your definition of CS theory. In my book, all the people listed under “faculty” at http://theory.stanford.edu/people/ are theorists.

    As idle speculation over a glass of good wine, I’d be interested in hearing how many of the theory departments mentioned so far would make a top 10 list worldwide, if theory is interpreted at least as covering both volume A and B TCS.

  11. In my book, all the people listed under “faculty” at http://theory.stanford.edu/people/ are theorists.

    I’ll just make two comments:
    1) We discounted senior professors who are no longer active in taking grad students. So, e.g., Knuth did not count for Stanford (and this also explains why Harvard was not a lock for the top 9).

    2) We also did not count people whose primary appointment was in another dept. (Admittedly, this may have been a mistake.) So, e.g., we did not count Ashish Goel for Stanford.

  12. I would agree about:

    MIT (Silvio, Shafi, Ron, Michel, …)
    Cornell (Rafael, Eva, Jon, Bobby,…)
    Berkeley (Luca, Christos, Umesh,…)
    CMU (Venkat, Manuel, Avrim, Ryan,…)
    Princeton (Boaz, Sanjeev, Moses, Bernard,..)

    The others are a bit flakier:
    GA Tech (Santosh, Chris, Vijay, Sasha, …)
    UT Austin (Adam, David, Brent)
    UCSD (Mihir, 1/4 Russell, Daniele, maybe Hovav)
    U Washington (Anna, Paul, Anup)

    I would say at least he following schools are VERY comparable to above:
    Stamford (Dan, Serge, Tim, Amin,…)
    NYU (Subhash, Assaf, Yevgeniy, Richard, …)
    Harvard (Salil, Michael(s), Leslie)
    Columbia (Mihalis, Rocco, Tal)

    I would say there are top 5, and then top 10 following them.

  13. I admit to be slightly peeved at not seeing Harvard on your list. (Don’t worry, just jokingly peeved, not really peeved. And thanks to others who correctly mentioned us.)

    But it is nice that there is seems to be a growing number of high quality programs — somehow, I don’t remember having the impression that there were so many when I was a grad student. Maybe that’s just an age thing.

  14. I was under the impression that U Chicago was pretty good in theory also – is that not so?

  15. One of the good things to come from this post is that my own personal list of 9 (or 10) has been slightly modified by some email discussion that this post generated.

    Michael, which school would you take out of the top 9 to make room for Harvard? (No, I don’t really expect you to answer that…) ;-)

  16. I could be wrong, but I would think that Stanford (Serge, Tim, Ashish, Amin) would be in the top 9.

  17. I could be wrong, but I would think that Stanford (Serge, Tim, Ashish, Amin) would be in the top 9.

    Once again, we did not count faculty unless their primary appointment was in CS.

  18. “Once again, we did not count faculty unless their primary appointment was in CS.”

    Which doesn’t make sense considering that econ/cs is a hot topic and obviously not all those people are in CS. Should really just count people who publish in CS.

    Seems that Stanford > UCSD.

    Until recently they had Rajeev, who was a super powerhouse. Just because they haven’t replaced him yet (impossible) doesn’t mean they shouldn’t be in the top five, which they would be if he were still there.

    Not to be rude, but I am not aware of anything that Serge P has done … Why not mention Dan Boneh instead? Isn’t he in CS (and isn’t this a crypto blog)?

  19. Rajeev had a series of great theory results and students in the 90s, but more recently, he had been doing (also excellent) work in more applied fields, and advising a more applied batch of students.

    But even if we count Rajeev, the theory group is small… Consider the other top theory schools. Since there is large deviation in what people count as “theory”, I’ll just count people who still actively publish in STOC/FOCS/SODA:

    MIT: Scott, Erik, Costis, Michel, Shafi, Piotr, Jon Kelner, Tom Leighton, Silvio.

    CMU: Avrim, Ryan, Venkat, Anupam, Gary Miller, R. Ravi, Alan Frieze

    Berkeley: Christos, Satish, Alistair, Luca, Umesh, Elchanan

    Princeton: Sanjeev, Boaz, Moses, Bernard, Avi

    Cornell: Bobby, Jon, Eva, David, Rafael

    It just seems difficult to place Stanford in this group. Certainly the Stanford theory group has a storied history, but the current group doesn’t measure up. Of course Tim and Dan are world class, so going to Stanford specifically to work with them is a reasonable thing to do. But I wouldn’t advise a student who didn’t know exactly what they wanted to do to go to Stanford over the other top schools.

  20. A brief foray into the web (namely, here: http://theory.cs.uchicago.edu/faculty.html) to answer a previous anonymous poster’s question:

    Chicago: Razborov, Mulmuley, Babai, J. Simon, Kurtz.

    Although they don’t necessarily work on the currently hot topics, these are some pretty big names who still do interesting work. Am I wrong here?

    Also at TTI-Chicago (which is somehow loosely affiliated with the University of Chicago, it’s a little unclear, but it’s on the page pointed to above): Chuzhoy, Y. Makarychev, Anastasios Sidiropoulos (who all work on approximation algorithms/inapproximability), Lance Fortnow (adjunct).

  21. What about Brown? Upfal, Klein, Mathieu (aka Kenyon), Tamassia, Preparata, Savage, Lysynskaya.

  22. Michel, Tom Leighton and Jon Kelner are in applied math…

  23. How about such a list of crypto school? While theory schools have been discussed and ranked a lot before, I can’t say the same about crypto.

  24. How about such a list of crypto schools?

    The problem is that there are fewer than 10 schools having more than 1 cryptographer. So you can put all school having more than 1 cryptographer in the top 10, and then it comes down to comparing individual people (which I am not going to do).

  25. I think the takeaway message is how the rankings are actually done, so it is wise not to pay too much attention to them while selecting a grad school.

  26. I think UMD also has a pretty good theory faculty: Aravind, Samir, Jon himself and also Bill (who is at least a great theory promoter). This list is comparable to, if not better than, UT Austin, UCSD and U Washington!

  27. CMU: +Guy Blelloch (papers from last 2 years: FOCS, SODA x 2, ICALP x 2, ESA x 2, SOCG, SPAA x 4).

  28. I think UMD also has a pretty good theory faculty: Aravind, Samir, Jon himself and also Bill (who is at least a great theory promoter). This list is comparable to, if not better than, UT Austin, UCSD and U Washington!

    If you really want to make comparisons like this, see that U Washington has produced more than 20 FOCS/STOC papers in the last 3 years. What about these other schools?

  29. “If you really want to make comparisons like this, see that U Washington has produced more than 20 FOCS/STOC papers in the last 3 years. What about these other schools?”

    Yes, FOCS/STOC papers may be a good measure. But if you subtract Guruswami’s contributions, who left for CMU, U Washington do not have more than 10 in past 3-4 years; most of them are Anup’s.

    I would suggest you include SODA, Crypto, COLT as well in counting, because STOC/FOCS do not represent all areas in cs-theory.

  30. “I would suggest you include SODA, Crypto, COLT as well in counting, because STOC/FOCS do not represent all areas in cs-theory.”

    SCG ?

  31. Its a little silly to rank “theory” schools, both since theory groups are so small and change so quickly, and because there is no such thing as “theory”. Do you want to study complexity theory? It would be a mistake to go to Cornell. How about learning theory? Don’t go to MIT. Game theory? You shouldn’t go to Princeton. Quantum computation? Don’t go to CMU.

  32. “There is no such thing as theory”

    Totally agree. Also most of the papers in STOC/FOCS contains only incremental improvement and read by AT MOST 10 people including the reviewers. Agreed these papers may be technically hard, but of course they would be forgotten as soon as they are published.

    There may be exceptions.. but they are only exceptions. It is sad that this community gives so much emphasis on quick conference publication and encourages vile rat-race.

  33. If you want to discount Guruswami and add Anup, it’s still about 20 since 2007. Look at Beame, Lee, Karlin, Rao, plus a number of student papers.

  34. Its a little silly to rank “theory” schools…

    Part of the point of the post was that this is true, to some extent, once you get past the top 7 (or 9, if you want to be generous — I have changed my mind on the ranking since I wrote the post). Also, students who already know exactly what they want to do, and have a particular advisor in mind, are free to ignore the rankings.

    I disagree strongly in general, however — both with regard to distinguishing the top few schools as well as for making finer distinctions among the next tier. Having multiple theory faculty, in diverse areas, means more choice when it comes to advisors, more theory courses to choose from, more students to interact with, more seminars to attend, and a more conducive environment for doing theory. And I would rank a department with fewer (or weaker) faculty but a “theory-friendly” environment (more courses, more invited speakers, better support from the dept., etc.) above a department with more (or stronger) faculty with a bad theory environment.

  35. Where is Brown????

  36. “Where is Brown????”

    Umm.. in Providence, RI!
    Definitely not in the above lists!

  37. ‘Where is Brown????”

    Is it even in the same league as the schools in Jon’s list. I can’t think of more than 2-3 active theoreticians there. In addition to faculy, you also got to look at alumni. I can’t seem to recollect any noteworthy Brown theory alumni.

  38. If I were to applying to grad school today my choices would be, grouped by equivalence classes:

    MIT

    Cornell
    CMU

    Harvard
    GA Tech
    UCSD
    Berkeley
    Princeton

    with a whole bunch of schools tied in the next group.

  39. I don’t get how UCSD is in the list if UCLA is not!! Faculty: Rafail Ostrovsky, Amit Sahai, Eli Gafni, Adam Meyerson, Yuval Ishai (visitng, past 2.5 years),….

    UCLA has published about 14 stoc/focs papers not counting the ones by visiting faculty only AND (more importantly) not counting even CRYPTO/EUROCRYPT papers (where the rate is about double). The environment is extremely conducive to research, dept has good funding, tons of graduate students to work with, and so many excellent courses to choose from (with several good courses by Benny Sudakov who is in Math). I do not see a single metric where UCLA is doing not as well as some of the other top theory schools discussed up there… any comments?

  40. Come to think of it can we assert a power law distribution on theory department ranking? each group seems to have about 2.5 as many members as the one before it, with group number four having, by my count, about 12 members.

  41. I would really like to have a comment from you on this jon.

    Except for Dick Lipton, Eiric and Vijay, who do you think is active in theory at Gatech.

  42. Except for Dick Lipton, Eiric and Vijay, who do you think is active in theory at Gatech.

    Subhash, Dana, Santosh, Apostolico, Nina, Boldyreva, Asaf Shapira….

  43. At Gatech there are also Randall, Tetali, Mihail, Vempala, Balcan, Peikert, and Boldyreva. They all have students and publish papers regularly. There are a whole bunch of theory-active people in the ISYE and math departments, too. (e.g. Cook and Tovey in ISYE and Basu in Math).

  44. BTW subhash is not at Gatech

    But yes – to anon 3 posts above; there are theory active ppl at Gatech

  45. i wouldn’t count Boldyreva as a ‘theory person’ but the other people in your list are already enough to give Gatech a high ranking

  46. Can I add a Canadian perspective?

    Toronto: Cook, Borodin, Rackoff, Ellen, Corneil, and a number of young very active faculty like Pitassi, Molloy, Magen, …

    Take a look at Lance’s recent post:

    http://blog.computationalcomplexity.org/2010/04/post-on-post-post.html

    now, where would you put Toronto?

  47. Hack again?!

  48. Gosh, I am simply astonished as to how we are obsessed with producing a total ordering!!!! Why?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 40 other followers

%d bloggers like this: