A Good Problem to Have

Last year's enrollment for CS 124 was 53.  So far, current enrollment for this year:  119. 

I imagine a few are still just taking a look and might drop.  But a doubling is looking possible.

This would be the largest CS 124 class since I started teaching it in 1999. 

Faculty Applications

An anonymous commenter asked how we evaluate faculty applications.  While it's a little late, it's a valid question, so here are some high-level thoughts.  Here I'm speaking only for myself, of course. 



First, I should point out that ideally, we're not reading your application from scratch -- we already know you.  We've seen you give a talk we like, or enjoyed one of your papers, or otherwise formed a (positive) impression.  The most important things you can do when applying come well before you write up your application.  If you're not taking advantage of opportunities to make yourself known in the community as a graduate student, you're not doing your job.  [Obviously, we don't only look at applications of people we already know.  But that just makes our job harder, and makes it harder for you to get picked out of the crowd.]


After that, it's not exactly rocket science.  I'm looking for a strong record, and the first things I'm looking for are good publications and good letters.  Applicants on the first pass are usually sorted into 3 basic categories:  invite for an interview, decline, or study further.  The publications and letters are the best guide for what pile you'll go into.

Once the pack is cut down, more details will come into play.  Some of us will probably read your papers to get a better idea your work.  Natural more detailed questions come up:  How interesting is your work?  How well do you fit our department needs?  What teaching experience do you have?  Is Harvard a place where we think you would be successful?  (For example, what other areas of Harvard might serve as possible points of collaboration?)

The interview helps us answer these questions further.  At the end of the day, what we're deciding is if we want you as a member of our department.  Research quality is a primary issue, and usually the primary issue.  But at this point, hopefully all of the people we're looking at have high-quality research records, with results that we collectively find compelling.  So the secondary issues I mentioned -- are you a good fit for us, are we a good fit for you? -- do matter.      

In the end, I don't think there's too much you can do to "strategize" your application -- because the main issues are to have a good work record, get people who can write you good letters, and be an interesting person who seems like they'd make a good colleague.  I expect that's not surprising anyone.  Though I'm sure since I wrote this a bit hurriedly, someone will point out where I've not described things suitably carefully or in enough detail. 

Collective Coordination of Conferences?

Around this time of year, I get a number of messages from students:  I want to take your class, but there's a conflict with this other class I want to take, what can be done...  Sometimes a solution can be worked out, sometimes not.  It's not an easy issue to deal with.  In Computer Science, we take a look at our own schedule of classes, and try to make sure there aren't any particularly bad time conflicts among our own classes, although inevitably there are some hopefully minor ones.  Then we try to look at other big classes in related areas -- try not to have our intro classes the same time as the intro economics, physics, statistics courses, etc.  Of course we also try to let them know when our big intro courses are, so they don't reschedule classes into those time slots as well.  In the end I think we do a reasonably good job.

That was a long-winded roundabout to where I wanted to get to, which is conference scheduling.  It's something that I think is becoming increasingly broken -- at least for theory conferences* -- due to the fact that there is (as far as I know) minimal coordination going on with respect to the calendar, and there's an ever-increasing number of conferences and workshops.  The near-overlap of ITCS and SODA is one obvious example.  The nearly-overlapping SPAA and PODC deadlines are another.**  I'm sure one can come up with hosts of others, and that's excluding the issue of trying to coordinate with other adjacent fields.  (For many years, INFOCOM and SODA deadlines, as I recall, were within a couple of days of each other -- and July 4th!  Not friendly, especially not family friendly.) 

I'm not claiming we want full centralization of conference scheduling.  But I do think there should be a lot more of it than we have.  A lot of aspects of the conference calendar -- dates, how many conferences we have, where they're located -- don't make a lot of sense to me, and I think that's because they don't make a lot sense.  I don't know how we arrange for a body to try to look at where we're at and figure out how to make it globally better.  But I wish someone would!   

* I haven't noticed this so much for other areas -- in networking, SIGCOMM, INFOCOM, NSDI, IMC, and even Allerton have always seemed reasonably spread out to me, but perhaps I just haven't noticed the problem.

** I've thought SPAA and PODC should have some sort of "merge" for almost 20 years now.  You're different communities?  Fine.  Then arrange a permanent co-location agreement.  It would be better for both conferences.  

January Flying By...

I'm enjoying a relatively snow-free January, but despite the extra time I've had on my hands from not having to shovel, I've had little time for blogging.  Reasons abound.

January is always busy, as we have graduate student admissions to deal with, and we're doing faculty searches this year.  Lots of applications to read.  As part of my Administrative position, I've had various other administration (read: promotion cases) to deal with.  The paperwork buck stops with me, so I'm busy making sure all the i's get dotted, t's crossed.  I've also had things to do for other Harvard-wide committees, which somehow landed on this month.

Besides that, there's been a fair amount of other writing.  Another NSF proposal should be going in next week.  Several new papers are coming into focus;  I may have 1 (or more) submissions for ISIT and EC, both of which have early February deadlines.  Hopefully when they're finished I'll have something to say about them here.

The MINE paper has actually been taking up a fair bit of time.  Lots of people are contacting us about it;  just getting through the e-mail is actually a noticeable chunk of the week.  The response is more than I expected;  the large majority of it seems positive.  

Outside work has also been taking up a good deal of time while I don't have to teach.  I testified at a trial recently, and was happy that the timing didn't interfere with the school semester.

Next week classes start.  Things seem swamped until Feb 6.  Post-EC deadline, I'll take a deep breath, and, with luck, then I'll be able to get a handle on what 2012 should look like.   

ITCS, Day 2

I stopped a while by ITCS, before having to deal with other meetings.

I saw fellow blogger Claire Mathieu, who told me my post on day 1 was negative.  To be clear, I didn't mean to come across as negative -- I did say the talks were all great, the arrangements were going well, etc.  Indeed, I'd argue my main question -- why aren't more people there -- should be taken as a positive statement about the conference.  But it was pointed out to me that I should point out that more senior people were around today (I guess Sunday people were busy with family or football), and that the lecture room for the talks -- which can hold about 100 people -- has been pretty full the whole time.  In at least one session today, there's were plenty of people sitting on the floor or standing in the back.  Even at larger FOCS/STOC conferences, there are plenty of talks that don't seem to get 100 people to come watch, so let's add that as a positive commentary for ITCS. 

Umesh Vazirani approached me and suggested the following proposal:  double the size of STOC, cancel FOCS, and make ICS the "second", smaller theory conference.  Both conferences could have substantial co-location with other conferences to ensure large-scale attendance.  His reasoning is that we should be accepting more papers in the theory conferences, we should have one substantially larger meeting, and that FOCS is at a bad time in the year (whereas STOC can be nicely in the summer and ICS in January, good times for academics;  January, in particular, is a good time for things like a program for graduating PhDs/finishing postdocs to help them get their names out to find postdocs/jobs).  I told him that not only did I think it was a worthwhile proposal, but that I had blogged about a similar idea before -- which, looking back at the post, was also inspired by Umesh!  So I guess I'm on record already as supporting this general approach. 

[UPDATE:  Umesh wanted me to make clear this is not meant to be a concrete proposal, but as a food for thought conversation -- the main point, of course, being "What do we want from our conferences?" and "How do we get there?"  Accepting more papers, and having something in January where students on the job market could present themselves, sound like two things a number of people think positively about.  What one names the conference -- ITCS or move FOCS to January -- is arguably a secondary point.]

Claire suggested that no such big change was possible within our community, which runs (generally) as a democracy (not sure I entirely agree with that), and democracies have trouble implementing such drastic changes.  She wondered what could be done with incremental changes.  I'm not sure.  We joked that we should just move both of STOC/FOCS a week closer together each year until they collided and then we could do away with one of them.  I don't find Umesh's idea (I figure constantly referring to it Umesh's idea should add support for it) exceptionally drastic, though it would be a change.  What do you all think?

ITCS, Day 1

I spent much of today at ITCS (Innovations in Computer Science) 2012, over at MIT.  Justin gave an excellent talk on our work (with Graham Cormode) on Practical Verified Computation with Streaming Interactive Proofs.

Overall, the talks seemed quite good -- the first session started with another great talk, by best student award winner paper Andrew Drucker, about High Confidence Predictions under Adversarial Uncertainty.  The bulk of the talk covered this aspect of his work from his abstract:

Letting N_t denote the number of 1s among the first t bits of x, we say that x is "eps-weakly sparse" if lim inf (N_t/t) <= eps. Our main result is a randomized algorithm that, given any eps-weakly sparse sequence x, predicts a 0 of x with success probability as close as desired to 1 - \eps. Thus we can perform this task with essentially the same success probability as under the much stronger assumption that each bit of x takes the value 1 independently with probability eps.

That's a neat result.  The rest of the session was very good as well. 

Also the location, food, etc. all worked well.  

Now for the bad news.  Attendance at ITCS is much lower than expected.  Last I had heard, pre-registration was below 100.  For a conference that is in a major theory city, that claims to (from the call for papers):

seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or cross-interdisciplinary areas, or introducing new techniques or new applications of known techniques).

I find this outcome very disappointing.

There seemed to be a reasonable number of locals from Harvard and MIT, but not from schools further out but within striking distance.  The recent math meeting in Boston perhaps let a few people stay over to attend -- I'm not sure how many did, but it didn't seem like many.  And there was a particularly noticeable lack of more senior people.   

I have expressed my reservations on this conference previously (see here, here, and here).  Specifically, I'd much rather see FOCS and/or STOC expand into a larger conference, where more of the theory community attends, than have yet another conference.  Moreover, some of the nice innovative things they're doing at ITCS this year --  having a "graduating bits" session for finishing PhDs and postdocs going on the job market and having a "community building" activity at dinner -- would, I think, be much more effective at a larger theory conference.  I understand such activities are effective in other communities that have a large annual meeting (like ISIT, for example). 

I also think ITCS got off on the wrong foot being placed in China for the first two years.  I understand that was an interesting opportunity, and lots of theory people got paid trips to China.  But I think an outcome is people have a mindset that this is a conference where you go only if you have a paper or you are a local.  I believe the hope was that having it at MIT would encourage a larger participation from the theory community, and I think from that standpoint the conference was not successful.  (Perhaps it's larger than it was in China, and I'm sure some people will disagree with me, but I don't view a 100-person conference in the Boston area meant for the general theory community as a success.)

I think it's a big question of where ITCS goes from here, and I think it's a question the larger community (not just the people attending this year) need to be involved in.  The quality of the work reinforces in my mind that the papers should go somewhere, preferably in my mind to a larger FOCS, STOC, or SODA;  or, possibly, to a larger and better attended ITCS.  Or perhaps people are happy with the current model, and my concerns are unwarranted.  Let me know.   

Chernoff-Hoeffding Bounds for Markov Chains

We (Kai-Min Chung, Henry Lam, Zhenming Liu and myself) have a STACS paper on Chernoff-Hoeffding bounds for Markov chains (arxiv version here).  Such bounds are used, for example, to say the amount of time a Markov chain spends in each state is close to its expectation (given by the stationary distribution) with high probability after a suitable amount of time.  Since successive states in a Markov chain are dependent, this sort of result does not trivially follow from regular Chenroff-Hoeffding bounds.  Such bounds for Markov chains is a reasonably old subject; I recall the state of the art being a paper by Nabil Kahale (Large Deviation Bounds for Markov Chains, available online) back around when I was in graduate school.

So what's new in our work?  Our paper gives Chernoff-Hoeffding bounds for general nonreversible finite-state Markov chains based on the standard L_1 mixing-time of the chain.  Previous bounds seem to focus on reversible Markov chains (although some of these bounds can be generalized using a technique called, coincidentally, reversibilization, a term which seems to date back to a 1991 paper by James Fill), and are based on the arguably less-easy-to-use spectral expansion of the chain.  Along the way, we also give a simplified proof for Chernoff-Hoeffding bounds based on the spectral expansion of the chain.

But some things I think are also nice about the paper is it utilizes elementary techniques, is (relatively) easy to read, has clean result statements, and provides a survey-like context for this area.  If you happen to need a tail bound for your Markov chain process, I hope you'll take a look.

Pointer, to Cash for Citations

I'm disturbed to find that nobody is offering to pay me large sums just to have me affiliated with them for the purposes of raising their citation count.  What am I doing wrong?

I'm referring to the cash-for-citation article I found by way of Crooked Timber;  here's what they refer to as the "liberated Science article" describing the issue in full detail.  Always nice to know what the going rates are for this sort of thing.