Friday, July 22, 2011


Early in the week, I was excited to find out that, apparently, it was perfectly appropriate for us professors to call (at least, already graduated) students assholes, publicly, because if it's good enough for Larry Summers, it's good enough for me.  (Or see here as well.)  That seemed very cool to me.

But now it seems the Winklevosses are asking for redress from Drew Faust, so the question of whether I can go around openly insulting students' character without worrying about whether anyone at Harvard will care is, for now, at least somewhat open.

(Further commentary, including some people at Harvard pointing out the inappropriateness of it all, can be found at Shots in the Dark, in temporal order here, here, here.)

Beyond Worst Case Analysis -- Preparing a Talk

A few months ago, Tim Roughgarden mailed me to say was putting together a little workshop on the theme of Beyond Worst Case Analysis, and would I like to be one of the plenary speakers?  It sounded like an interesting topic, one I've certainly spoken off the cuff about on this blog from time to time.  And I enjoy any reasonably good excuse to get out to the Bay Area.  So I agreed.

The workshop announcement is here.  As you might imagine, what Tim DID NOT tell me at the time was that the other speakers were Avrim Blum, Bernard Chazelle, Uri Feige, Richard Karp, Dan Spielman, and Shang-Hua Teng.  That would have given me pause, to say the least.  Now I get to spend the summer thinking about how I'm going to give a talk that could still be deemed interesting in the company of this group of scholars.  No pressure, no pressure...

(Tim also failed to mention that he had actually taught a course on this whole subject.  Which, I should say, looks like a great course -- I'd love to swipe his notes and teach it myself some time.  Again, the bar here is higher than I had expected... let that be a lesson to everyone if Tim comes asking you for something...)

I will hopefully blog more on this topic as I prepare the talk, in order to get ideas and feedback from the community at large.  I figure that's one way to improve my talk.  Also, now that I've said I'm going to do that, hopefully it will get me working on the talk sooner rather than later.  (It's amazing how fast the summer goes by, and you fail to get done all the wonderful things you had planned to do over the summer...) 

But even now, you can help me out.  What directions or issues do you see in the theme of Beyond Worst Case Analysis, and what would you like to see in a talk on the subject?

(And if you get a chance, come to the workshop!)

Monday, July 18, 2011

Rabin's 80th Birthday Celebration

Big announcement:  We'll be having an 80th birthday conference celebration for Michael Rabin at Harvard at the end of August.  Lots of great talks by big-name CS people!  (And I'll be there too.)  The web site has all the relevant information -- schedule, directions, hotel, etc.  KEY POINT:  We need you to register in advance.  (Otherwise we won't have a head-count for food, etc.) All of us at Harvard hope you'll be able to come.  See you there!   

Formal announcement below:

On August 29-30, 2011, there will be a conference in celebration of Michael Rabin's 80th birthday at the Harvard School of Engineering and Applied Sciences.    The speakers include Yonatan Aumann, Michael Ben-Or, Richard Karp, Dick Lipton, Silvio Micali, Michael Mitzenmacher, David Parkes, Tal Rabin, Ron Rivest, Dana Scott, Madhu Sudan, Salil Vadhan, Moshe Vardi, and Avi Wigderson.

The conference is open to the public, but registration is required by August 25.  For more information, see the conference website at

Tuesday, July 12, 2011

SODA in Japan

I hadn't even noticed SODA was in Japan before submitting.  I just figured wherever it was I'd be willing to go, as January in Boston is a fine time to be elsewhere.  And if needed I can send a student instead...

My only past time in Japan was for ISIT back in 2003.  I remember it was a maddeningly long flight (made somewhat bearable by distracting myself with whatever was the new Harry Potter book at the time), followed by a 2 hour long wait to get through customs, followed by a 2 hour train ride to Yokohama.  I was not a happy camper when I got to the hotel.  Which, once I got there, was absolutely amazing;  a bath in the deep Japanese-style tub and some food and the grumpiness passed.  And then it was a great conference;  hanging out with an old friend and his colleague over breakfast we managed to produce a paper (which eventually ended up being this journal version -- my first and likely only paper that will appear in IEEE Design and Test.)  One day we took off and did some great sightseeing, where I depended greatly on the lead of others, not having grokked how to get around with signs in a language I didn't understand at all. 

So if I get a paper in I suppose I'll cope with the long flight and go.  Of course with 600 or so submissions it's a roll of the dice;  we'll see how it goes.

Best of luck to everyone working until the deadline....

Saturday, July 09, 2011

Using Google Scholar for More Than Your h-Index

The comments from the last post (thanks, David Andersen) spurred me to mention the following.

I do check Google Scholar for my own work fairly regularly.  Not to keep continuously updated on my h-index (though, I suppose, that's a side benefit).  But I've found it very useful to look at who is citing my work.  For older areas of research where I'm (at least temporarily) inactive, it's useful to keep track on what's gone on since I've been paying close attention.  For areas where I'm still doing research, it's helpful to know what's out there -- so I can cite it, I can see where the area is going, and I can know who is working in the area.  Keeping up to date this way can also suggest new research problems or collaborations.  Being able to access the citation graph so easily is, I think, very helpful.

I do the same thing using full-text search for myself on the arXiv, and I even Google myself on the Web.  (I've found blog posts mentioning me or this blog that I wouldn't otherwise have known about that way.)

So no, I don't think it's egotistical to check yourself on Google scholar.  I think it's just a good research practice to keep tabs on who is citing your work.

Friday, July 08, 2011

h-index != impact

Suresh and Daniel Lemire (in Google+ posts) have pointed to the following paragraph from this blog:
The sad thing is that young people have now been terrified by the Impact and H factors, and I can’t give them much hope. When I published my first paper in 1967 (J. Chem. Soc. (now the RSC), Chemical Communications) I did it because I had a piece of science I was excited about and wanted to tell the world about. That ethos has gone. It’s now “I have to publish X first author-papers in Y journals with impact factors great than Z”.
As a service to those young people, I'd like to make clear that, at least at my institution, the “I have to publish X first author-papers in Y journals with impact factors great than Z” approach is not actually suitable, and you should focus on the "I had a piece of science I was excited about and wanted to tell the world about" approach. 

I'm not being naive.  Citation counts certainly arise in promotion and tenure cases.  They're a piece of information, and we look at them.  But just as your GRE score won't get you into (one of the top-tier) graduate schools,  your h-index is not going to get you tenure (or a grant, or an award, or...)

When you come up for promotion, we ask for letters.  Some letters will mention your citation counts or your h-index as a way of providing evidence that you've done interesting and important work, and that's all well and good.  Then, what we look for, is an explanation from the scientist as to why they think your work is interesting and important.  Arguably, the best way to get your letter-writers to write a good case for why your work is interesting and important is to do work that you're excited and want to tell the world about.  Because if you are excited and go tell the world, repeatedly and with energy, the word will get out, and get to the ears of those scientists who are going to write your letters.

Of course, even ignoring those employment-relate aspects, doing science you're excited about is just more fun.

I wonder if the author of this blog post is correct in the characterization of young people, as the idea is a bit foreign to me.  In theory, of course, we have some great role models;  I don't think Les Valiant, Jon Kleinberg, David Karger, Cynthia Dwork, and so on spend their time worrying about their h-index.  They just want to do cool stuff (and, as far as I've known them, always have -- it's not a "now-that-they're senior" thing).  But just in case, let's make sure the correlation/causation message gets out right:

cool work, excitement, and enthusiasm tends to yield high citation counts and maybe h-indexes
citations are not how we define or even measure cool work, excitement, and enthusiasm

Wednesday, July 06, 2011

Various Goings On

I've not been a Facebook user, but I was invited to join Google+, so I set up a picture and am waiting to see what it's all about.  I'm afraid that for the most part I'm not so interested in a wall where people tell me what's going on with them, nor do I see the point in writing to groups of people I know to update them on my life this way, but perhaps over time I'll be converted to this way of socializing.  Until then, I guess I'll keep writing blog posts if I feel I have something to say (which, admittedly, has been less often these days).

600+ abstracts submitted to SODA.  I wonder what the over/under is on how many will actually be papers a week from now.  I'm expecting about a 10% drop, but wouldn't even be surprised to see it go down to 500 or so.   That suggests about a 25+% acceptance rate.  I'm not sure what message there is to take out of that.  But given that 500 seems to be the total of accepted papers for SODA, STOC, FOCS, ESA, ICALP, and maybe another conference or two after that (SPAA, PODC?), it seems like theory is (still) producing too many papers, or has too few venues to publish them in.  Larger conferences, or perhaps a large clearing-house conference, anyone?  (Would SODA be that much different if it accepted, say, 250 papers?  Discuss.) 

While I think svn is great for collaborations, I've really found the merging functionality has negligible utility.  I'm a novice user, but it seems whenever there's a conflict, the fastest way to deal with it is still to pick a winner, diff for differences, and glue together by hand.  I think the bottleneck is when there's a conflict, I want to work out differences with my colleague, and the whole point is that we're working at different times and places.  So the benefit of working separately seamlessly gets lost. 

I still think everyone should be reading Claire's blog, which covers a really nice mix of topics, many of which could potentially lead to interesting community discussions.  

Friday, July 01, 2011

Odd SODA Rules, and Other Conference Paper Complaints

Suresh points out we have some strange new SODA submission rules this year: 

Full submissions should begin with the title of the paper, each author's name, affiliation, and e-mail address, followed by a succinct statement of the problems considered, the main results, an explanation of their significance, and a comparison to past research, all of which should be easily understood by non-specialists. More technical developments follow as appropriate. Use 11-point or larger font in single column format, with one-inch or wider margins all around. The submission, excluding title page and bibliography, must not exceed 10 pages (authors should feel free to send submissions that are significantly shorter than 10 pages.) If 10 pages are insufficient to include a full proof of the results, then a complete full version of the paper (reiterating the material in the 10-page abstract) must be appended to the submission after the bibliography. The length of the appended paper is not limited, and it will be read at the discretion of the committee. A detailed proof in the appended complete version is not a substitute for establishing the main ideas of the validity of the result within the 10-page abstract.

This is totally bizarre.  11-point single column-format?  Then an appended paper beyond the abstract?

I wish I was submitting a paper on my own.  I'd just submit a standard opening abstract and my "10-page paper" would be, "Hey, I've just told you what I'm going to prove, why don't you go read my real paper, which is attached to this?"  Because, really, I'm not clear on what the point of all this is.

Having recently finished an ICALP paper and having worked today on an ESA paper, I didn't think it was possible to choose a worse format that 10 or 12 pages in LNCS format, which gives you just enough space to say, "Here, I've done something interesting, but if you want any details, go read it on the arXiv."  And I suppose this isn't really worse.  [Really, can't we all just protest the bizarre LNCS format?  Or fine, keep the format, but paper limits should be 20 pages.]  It's just strange.

Most other conference I'm involved with outside of theory have the sensible approach that you submit something that looks pretty much like what your final paper is supposed to look like.  You may only have a 5 page limit (double column, 10 point font, which I think is still well over 12 pages in LNCS format), but the reviewers sees what the paper will be.  Some conference even give a page or two extra for the final version, so you can actually address reviewer comments.  (Of course, those conferences also make a point of giving detailed reviewer comments, in some cases even having shepherds for the final papers.)   

Theory conferences are messed up with this whole page limit/paper format thing.  Someone should figure out a simpler, more coherent system.  It seems like it would be hard to come up a system that was any more random and arbitrary.