Monday, March 05, 2012

Making a Midterm is No Fun

I think one of most challenging parts of teaching a course is setting up exams. 

There are a lot of constraints:

You want to cover, as reasonably as possible, all the material.
You want to target somewhere around the median of the class;  not too hard, not too easy. 
You don't want there to be any severe typos or other problems with problem;  you can't have a problem without a solution or is otherwise confusing.  
There are a limited number of good problems readily available;  making up new problems is challenging.  (Again, you don't want errors...)
You have to make it all do-able in 90 minutes.  
And so on....

I look forward to reaching a point where I don't think it's worth giving exams to students.  (I don't in my grad classes.)  For my undergrad class, I still think it's necessary. 

Saturday, March 03, 2012

Inaccessible

The major reason for my lack of blog posts recently is that I was cut off from the Internet for a week.*  Surprisingly, the experience was not so bad.  I actually enjoyed being offline, and even the pain of coming back was not as bad as I had thought -- it only took about a day to catch up with e-mail.  Much e-mail was junk that needed no attention, a good bit was time-sensitive stuff that simply moved on happily without me, and a smallish fraction was actually important and time-consuming.  Of course, there was an inherent bias, since many people knew I'd be away.  I can't remember the last time I was off the Internet for a week -- but it has been a long time.  There are plenty of days that I go without watching TV, or even driving my car, but a day without the Internet is in itself a fairly rare event.

On the trip back I used GogoInflight and simultaneously had a great and frustrating experience.  Since I had a stopover, I went with a 24-hour package.  My first short flight, on a relatively small plane, had service and all went very well.  Internet on a plane is indeed useful (particularly when you have a week of e-mail to catch up on).  However, my much longer second leg on a much bigger plane didn't have the service, making the purchase something of a waste.  I don't blame Gogo, I blame American Airlines...

And for those with stopovers in Dallas, always remember to bring your CAT5 cable.  Somehow, the terminal there I frequent has free WIRED Internet access, but only if you know to bring your own cable to connect your laptop.  On the plus side, I've never had problem getting a seat at the Internet table, since nobody else seems to travel with the required cord.  It makes me happy that Boston is one of those friendly airports with free wireless.

The other reason for the lack of blog posts has been the need to catch up.  When were those reviews due again?....  What's that next conference deadline?.... When's my midterm?....  Back to it.

*OK, technically, not true.  However, cruise ship rates for Internet access are a fairly ridiculous 65 cents a minute (with smallish discounts for bulk time).  It didn't seem worthwhile. 

Sunday, February 26, 2012

Technology Diffusion (Guest Post from Zhenming Liu)

My student, Zhenming Liu, writes about some of his recent work:

Sharon Goldberg and I recently submitted a paper about technology diffusion in the context of communication networks. There has been lots of work in this area in the networking literature; while networking researchers and practitioners usually know what technology they want to deploy in the network (e.g. Secure BGP, QoS, IPv6, etc.), they often don't know how to get the economically-motivated nodes in the network to adopt it. What sort of utility models could capture an economically-motivated node's decision to adopt a communication technology? Some assumptions Sharon has found in the literature (and used in her own work) include:
  • A node's utility depends on the number of other nodes it can communicate with using the new technology. This is sometimes known as Metcalfe's Law.
  • Two nodes can communicate with each other only if there is a path between them such that every node on the path has deployed the new technology.
Thus, unlike existing works on viral marketing in social networks -- where a node's utility function depends only on its immediate neighbors-- in our setting, node utility is non-local. We considered the following question:

Given a communication network $G(V, E)$, we assume that node $u$ activates (i.e., deploys the new technology) if it is adjacent to a connected component of active nodes in $G$ of size exceeding node $u$’s threshold $\theta(u)$. Our goal is to find an efficient algorithm that determines the smallest seedset of early adopter nodes, that once activated, causes a cascade that eventually causes all other nodes in the networks to activate as well.

We designed an approximation algorithm that returns a seedset which is at most $O(r\ell \log |V|)$ larger than the optimal seedset, where $r$ is the graph diameter and each node's threshold can take on one of at most $\ell$ possible values.
  1. We seem to have the first tractable model that considers cascade effects with non-local influence in a graph; in the social network literature, the influences are local, while the networking literature considers non-local influences, but thus far has not developed any approximation algorithms.
  2. Our algorithm substantially deviates from the greedy strategies we see in almost all influence maximization papers for social networks today. After reading lots of papers in this area and writing some ourselves (e.g. this and this), my colleagues and I started to suspect that a “computational dichotomy” exists among these problems: either the problem is deadly hard or greedy algorithms already work well. Our new result demonstrates that this is not the case, at least when influence is non-local.
  3. Finally, our randomized algorithm makes use of a linear program, which is quite surprising because the problem seems highly non-linear; we managed to linearize the process by first carefully restricting our search space, while paying the price of only constant approximation loss.
I hope this paper will lead to more work on diffusion processes with non-local influences; studying other relevant models, or developing more efficient algorithms would both be interesting.

Thursday, February 16, 2012

Advantages of a Bigger Class

I'm several weeks into the super-sized class this semester.  Mostly, I find it's going fine -- indeed, there are some advantages, I'm finding, to the larger class size.

1)  Student participation.  While I'm sure the fraction of students attending is probably about the same, with a bigger class, the room actually feels full.  And, when I ask a question, there are more students who will answer.  I think the interactive aspect of the class is much higher this year.  (Related bonus:  sounds like more laughing when I tell a joke.)
2)  More creativity.  This is mostly due to my teaching staff.  With a larger teaching staff, we've optimized our resources a bit (e.g.: not every TA teaches a section every week, freeing them to do other things;  one-person jobs like prepping section notes have to be done less frequently per person).  So now we have special post-homework-go-over-the-problems sections, a new Web site, and Piazza.  Thanks team.

The advantages, so far, outweigh the downsides.
1)  Grading.  I historically grade the first programming assignment on my own, and help grade the midterm/final.  I haven't had to do any of that yet.  I'm not looking forward to it...
2)  Student interest.  More students want to meet with me, have lunch, and so on than in previous years.  Normally, I would put this in the positive column.  But since the semester started I've been soooo busy that I just end up feeling guilty telling students yes... but later in the semester.

I'm curious to see if the increase in students will hold for next year.  But if it does I think I can find the positive.

Wednesday, February 15, 2012

Using Piazza

My TAs forced me to "get with the program" and use Piazza as our mechanism for student questions.  In the past I've simply used a central e-mail address that got forwarded to all the TAs (and me);  questions sent there would be answered by a TA (or me) and we all would see the reply.

Piazza offers some additional bulletin-board+ functionality on top of that framework -- things like being able to type things in Latex, easily see what questions are left open, etc.  It seems useful enough;  it's definitely better than past bulletin-board-style offerings I've seen.  Honestly, though, for me the primary benefit is that it lessens the amount entering my mail spool -- it's more organized having these questions all in one place, with formatting.  I'll have to see what the students think during and at the end of the semester. 

At the moment I'd recommend it, which is not something I thought I'd say -- like I said, I've eschewed such tools in the past.  On the other hand, I'm not clear on their eventual business model -- I don't think I'd pay for using it as a service.  Perhaps the plan is just to get us so used to it that the idea of not using it is painful enough that we decide to pay.  We'll see if I reach that point over the semester.

Tuesday, February 14, 2012

A Systems Complaint

I think of myself as a person who works both in systems and theory.  And I've found that's often a challenging position.  I've been vocal before that I think theory conferences, to their detriment, downplay experimental work -- most algorithms papers don't actually implement algorithms.  Today it's time for a complaint about the systems culture.

I think many systems people appreciate good and useful theoretical results.  However, they have I think some unusual expectations abut what is good and useful, in that it has to be something they can absorb in the space of a few pages*.  (Really, in the space of the paper you submit, but given that you have to actually produce some implementation results for a systems paper, you really only have a couple of pages to get your theory across.)  For example, I was fairly disturbed when I got back reviews for a paper (some time back now...) sent to a systems conference with significant theoretical content that included comments like (edited to protect the conference):
While the program chairs were eventually able to locate reviewers who knew enough about the previous work in the area to understand and verify your work, this indicates to me that the XXXX audience will have a difficult time understanding this paper.   (The average XXXX attendee will not be familiar with Celebrated20YearOldTheoryResult, much less the more recent work you build on.)
Another review stated:
It is reasonable (though a bit of a stretch) to assume a XXXX reader is familiar with MAJOR20+YEAROLDAREAOFTHEORY and Celebrated20YearOldTheoryResult. It is less reasonable to assume the reader is familiar with [major paper cited several times in our submission], and not at all reasonable to assume the reader is familiar with [other work under submission and on the arxiv], an unpublished manuscript by the authors. Yet I found that this paper was not sufficiently self-contained to understand it without referring to those prior works.
Of course, this was a challenging paper, and in fact in the paper we were quite clear that we were building on lots of previous work.  We tended to state things in the form of, "It is known that X holds [citation], and using that we do..."  So if they didn't believe us, they could go look it up (though, admittedly, it's not easy stuff).  We had expected that they would take our word on background material;  as the reviews state, they did verify we were accurate in our use of the prior work, and that we had clearly cited it. 

But apparently (and I didn't get the memo on this), "self-containedness" is considered important for systems conferences.  Which, interestingly, goes against most work in theory, where you're often trying to build on a substantial chain of previous work.

I find this worrisome for work spanning the systems/theory divide, and will plan to fight this attitude on whatever systems PCs I am on.  I think it's great that systems people are interested in and like to use theory.  But if they want to apply something more complex than, say, a Bloom filter (a truly wonderful data structure, easily described completely in 2-3 paragraphs), the community might have to accept that, yes, to fully grok the interesting stuff in our paper, they'll either have to accept our word for what's in the past papers, or find and trust reviewers who can vouch for what's in past papers, or go read the papers themselves.  Not everything can be adequately spelled out in complete detail starting from a blank slate in a 10 page paper.  

Perhaps one could argue that this was an isolated incident, and certainly I know there are (plenty of) people in systems who do not think this way.  But I do think it's representative of (a non-trivial part) of the culture.  

I find the idea that a paper that involves theory that goes beyond what you, or even your community, has yet to experience is automatically out of scope a disturbing framework, and I find the expectation that I should be able to get you up to speed on a complex area in a few pages so that the paper is "self-contained" unreasonable.  

*I've heard some people more disparagingly say that you have to make them think they've understood it, not actually understand it.

Friday, February 10, 2012

Class Size Incentives

There's an interesting story in today's Crimson about a possible rise in "limited enrollment" classes at Harvard.  (See this older Crimson article as well.)  There may, of course, be didactic reasons for limiting the number of students in a class, but there seems to be an impression that there's something else behind this.  A somewhat harsh quote from Harry Lewis:
“My sense is that it’s increasingly thought to be a matter of professorial prerogative to say, ‘to make a better teaching experience for me, I’m not going to teach these students who are paying $50,000 a year to come to Harvard’—and it doesn’t seem right to me,” Lewis said.
Clearly Harry has a point.  On the other hand, from the faculty point of view, Harvard (and from what I know, many other schools) don't generally incentivize teaching larger classes -- which, I can tell you (since my class size doubled from last year), is indeed more work.  If you're not tenured, there may be some incentive to teach a larger class sometime early on -- it shows you're a team player, useful to the department/college, etc.  Past tenure, I'm not sure there's a direct incentive -- although plenty of faculty enjoy teaching, and are happy to teach larger classes at least once in a while.  Without such incentives, isn't limited enrollment understandable (as long as nobody stops you)?

Should a university offer incentives for teaching larger classes?  Perhaps some additional time on teaching leave?  Or direct monetary compensation?  What is the "social contract" between faculty and students regarding when class size should be limited?  Or the less social contract between faculty and their employers, the universities?  How are these questions affected (if at all) by the newly developing paradigm of classes of 100,000+ online?

Challenging questions, I think.

Thursday, February 09, 2012

Citation Circles on FSP

Sorry I haven't blogged much.  Life's been busy. 

But here's an interesting post by FemaleScienceProfessor discussing the appearance of "citation circles", people forming groups to cite each other (when possible) in order to get their citation numbers up.  On the Web, the equivalent is link farms, designed to get one's ranking up in Web search.  It makes me wonder if other methods for improving one's search rank are showing up or already commonly in play by people who try to work their citation count numbers upwards.  And whether methods for finding link farms used by search engines could (and should?) be used to correct citation counts in some way.

Saturday, January 28, 2012

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. 

Thursday, January 26, 2012

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. 

Wednesday, January 25, 2012

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.  

Friday, January 20, 2012

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.   

Monday, January 09, 2012

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?

Sunday, January 08, 2012

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.   

Saturday, January 07, 2012

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.

Monday, January 02, 2012

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.

Friday, December 30, 2011

New Year's Thanks

There are many things I'm thankful for this year.  Perhaps most notably, the new year marks the halfway point of my 3-year stint as "Area Dean for Computer Science".  Not that I'm counting.  I'm very thankful for that.

Strangely, though, despite the additional job, looking back on the year, it's been very enjoyable, research-wise.  That's not due to me.  So, importantly, it's time to thank some people.

First off, I thank my students.  Justin, Zhenming, and (now-ex-student-but-collaborator-who-I-still-call-student) Giorgos are all doing really interesting and exciting things.  They've been teaching me all sorts of new stuff, and have put up with my increasingly random availability as various non-essential Area Dean type meetings jump in the way.  Having multiple students all making great progress on entirely different areas makes the job really, really fun.  

Thanks to Michael Goodrich, who called me up about two years ago (has it been that long?  I had to go back and check) and wondered if I could help him on a project where he wanted to use cuckoo hashing.  And since then, he's continued to keep me busy research-wise, as we've jumped from trying to understand how to use cuckoo hashing in Oblivious RAM simulations to other practical uses of cuckoo hashing as well as other algorithmic and data structures problems.  He's an idea factory, and I get to come along for the ride. 

Similar thanks to George Varghese, who regularly provokes me into networking research.  I always have to listen closely when talking to George because there's usually some insight he has, often I think not yet fully formed in his own mind yet, that when you see it will leave you with an AHA moment.  (Sometimes, then, George mistakenly attributes the idea to me, even though my understanding comes from listening to him.)  Also, both Michael and George have been really, really patient with me this year.

I of course thank the MIC/MINE group, who I've already been thanking all week.  And John Byers, who has worked with me on more papers than anyone now, and is still willing to keep coming back.

I'd like to thank all the CS faculty at Harvard.  When I travel around, and people ask me if it's hard being Area Dean, and how much do I have to do, I have to explain that it's not really that hard.  There's some basic handling of paperwork and e-mail.  Other than that, as a group we have lunch on Fridays to talk about things we have to do.  I then sometimes have to ask people to do things so things actually get done (because I can't do everything myself).  Then people do them, and as a group we're all very happy.  When I try to explain this, sometimes other people look at me like I'm totally insane, which I've come to interpret as meaning that this is not the way it works everywhere.  I've got a great group of colleagues, so I can still sneak in some research time here and there.

I also tremendously thank Tristen Dixey, the Area Administrator for CS and EE.  She's the one that actually runs the place (thank goodness).  Seriously, I'd be lost without Tristen.  Many are the requests sent to me where my response is, "Let me check with Tristen on that."  Because she knows what to do.

Thanks to all my other co-authors, and anyone else I'm forgetting to thank.
 
Finally, I thank the NSF, as well as currently Google and Yahoo, for sponsoring my research.  I especially have to thank the NSF;  while I can't say I think they're perfect, I can say that I think they're wonderful.  They've funded me as a faculty member for over a decade now, and my students and I couldn't do the research I like to do without them. 

I also, more privately, thank my family, for putting up with my working habits. 

Happy new year to all.

(Just 18 more months...)

Thursday, December 29, 2011

Cross-Cultural Learning Curve: Sending a Paper to Science

We decided to submit our paper on MIC and MINE to Science it's a venue that my co-authors were familiar with and very interested in applying to.  I was happy to go along.  Moreover, it seemed like the right venue, as we wanted to reach a large audience of people who might be able to use the approach. 

Sending a paper into Science feels very different than sending to a FOCS/STOC/SODA or SIGCOMM conference, or to a CS journal.  I think there are many reasons for this.  (And I'm trying not to offer judgment, one way or another -- but rather to describe the experience.)

1.  There's a feeling that there's not really a second shot.  If you submit a paper to a major CS conference, and it doesn't get in, you revise as needed and can try for the next one.  (Some papers get submitted 3, 4, or more times before getting in.)  For a journal like Science, they'll only review a small fraction of submitted papers, and if your paper doesn't make it in, you're not going to get a second shot there;  you'll have to find another, arguably less desirable venue.  (SIGCOMM can feel more that way, more than FOCS/STOC, but definitely not to the same extreme.)
2.  Perhaps correspondingly, there's a greater focus on polish of the final form before submission.  The article should be ready for publication in the journal, which has a high standard in terms of the appearance of the articles, so there's a sense that it should look good.  This means much more time is spent on writing (and re-writing, and re-writing), on trying to figure what the perfect graphic is, on making that graphic look awesome, and other aspects of the presentation.  On the whole, CS papers are, shall we say, much less presentation focused.
3.  The paper will (likely) be read by a much broader (and larger) audience.  This again changes how one thinks about presentation.
4.  For many fields, a Science article is extremely important, much more valued for a student author than even a FOCS/STOC/SIGCOMM paper.  (I realize that, in computer science, venues like Science and Nature have not historically been given an especially high importance.)
5.  Journals like Science have very strict rules regarding various things.  For example, we were not supposed to publish the work in another venue (like a conference) before hand.  Once the paper was accepted, there was an "embargo" -- we weren't supposed to talk about it before publication without permission, and we could not announce the paper had been accepted.  In CS, we have the arxiv and other online repositories that are used widely by theoreticians;  even in areas where double-blind conference submissions are the norm, such rules are not taken anywhere nearly as seriously as by Science, as far as I can tell.

I've also been truly surprised by the amount of reaction the paper has generated.  Sure, I had been told that getting a paper in Science is a big deal, but it's another thing to sort of see it in action.  (I haven't seen this big a reaction since -- well, since Giorgos, John, and I put the Groupon paper up on the arxiv.  But that was very unusual, and this reaction has I think been bigger.)  There's definitely a human interest angle that is a part of that -- brothers working together on science makes a more readable news story -- but also there was much more effort behind the scenes.  There's the sense that an article in Science is really a big chance to get your work noticed, so you prepare for that as well.   

If I had to describe it in one word, I'd say publishing in Science feels much more "intense" than usual CS publications.  The competitive aspect -- that some people in CS feel is very important (the "conferences are quality control" argument) and others do not -- feels like it's taken one level up here.  Maybe the stakes are bigger.  As an outsider, I was both amazed by and bemused by some aspects of the process.  Even having been through it, I don't feel qualified to offer a grounded opinion as to which is better for the scientific enterprise, though I certainly feel it's an interesting issue to discuss.

Tuesday, December 27, 2011

Some of The Fun of Collaborating...The Other People

One of the things I enjoy most about working in algorithms is the breadth of work I get to do.  And while I've worked on a variety of things, almost all have been squarely in Computer Science.  (If one counts information theory as EE then perhaps not, but CS/EE at the level I work on them are nearly equivalent from my point of view.)  But at Harvard there are plenty of opportunities to work with people outside of computer science, and my work on MIC and MINE was my biggest cross-cultural collaboration at Harvard.  In particular, the other co-primary-advisor on the work was Pardis Sabeti, who works in systems biology at Harvard -- here's the link to her lab page.

Pardis is no stranger to mathematical thinking -- some of her work that she's most well known for is in designing statistical tests to detect mutations at the very short time scale of humans over the last 10,000 years, with the goal being to identify parts of the genome that have undergone natural selection in response to diseases.  So while my take was a bit more CS/math focused (what can we prove? how fast/complex is our algorithm?) and hers what a bit more biology/statistics focused (what is this telling us about the data?  what data sets can we apply this too?) the lines were pretty blurry.  But it did mean  I got to pick up a little biology and public health on the way.  Who knew that natural selection could be so readily found in humans?  Or that the graph of weight vs. income by country has some really unusual characteristics (weight goes up with national income up to some point, but then goes down again;  the outliers are the US, and Pacific island nations)?  And that you can find genes that are strongly tied to susceptibility to certain viral diseases?

I must admit, it is a bit intimidating when talking to a colleague about your other projects, and I'm explaining cuckoo hashing and Groupon, while she's discussing flying off for the Nth time this year to Africa for her project on how genes are changing in response to Ebola and Lassa viruses.  But it's just encouraged me to keep looking for these sorts of broadening opportunities.  Maybe someday I'll find a project I too can work on that will help us understand viruses and diseases.  (Hint, Pardis, hint!)     

The primary student collaborators were David and Yakir Reshef.  David was a student at MIT when he took my graduate class Algorithms at the End of the Wire, which covers information theory as one of the units.  He had already been working with Pardis on data mining problems and ended up working on an early version of MINE as his project for the class.  I told him he should continue the project and I'd be happy to help out.  It's always nice when class projects turn into papers -- something I try to encourage.  This one turned out better than most. 

David continued working with his brother Yakir (along with me and Pardis).  David and Yakir are both cross-cultural people;  Yakir is currently a Fulbright scholar in the Department of Applied Math and Computer Science at Weizmann, after getting his BA in math at Harvard -- but is currently applying to MD/PhD programs.  David is getting his MD/PhD here at Harvard-MIT Health Sciences and Technology Program, after having spent the last few years at Oxford on a Marshall doing graduate work in statistics.  So between them they definitely provided plenty of glue between me and Pardis.  Both of them pushed me to learn a bunch of statistics along the way.  I'm not sure I was the best student, but I read a bunch of statistics papers for this work, to know what work was out there on these sorts of problems.  

Others also came into the project, the most notable for me being Hilary Finucane -- who I wrote multiple papers with when she was a Harvard undergrad, and who was simultaneously busy obtaining her MSc in theoretical computer science at Weizmann.  And who is now engaged to Yakir (they were a couple together back at Harvard) .  With two brothers and a fiancee in the mix, the paper was a friendly, family-oriented affair.  I also got to meet and work with Eric Lander, who was one of the leaders in sequencing the human genome, and quickly found out how amazing he is.  

Like many of my collaborations these days, the work would have been impossible without Skype -- at various points on the project, we had to set up meetings between Boston, Oxford, and Israel, which generally meant at least one group was awake at an unusual hour.  But that sort of group commitment helped keep the energy up for the project over the long haul.

The work on MIC and MINE was a multi-year project, and was definitely more effort than most papers I am involved with.  On the other hand, because it was a great team to work with, I enjoyed the process.   I got to work with a bunch of people with different backgrounds and experiences, all of whom are immensely talented;  they pushed me to learn new things so I could keep up.  I'm glad the work ended up being published in a prestigious journal -- especially because the students deserve the payoff.  But even if it hadn't, it would have been a successful collaboration for me.

Monday, December 26, 2011

Wasted Hour(s)

Last night I was running some code for a queuing simulation related to some research I'm doing.  This is the Nth time I've used this code;  I wrote up the basic simulator back in grad school for some of my thesis work (on the power of two choices), and every once in a couple years or so, some project pops up where what I want is some variant of it.  So I copy whatever version is lying around, tweak it for the new problem, and off I go.

Today when I was putting together the table the numbers just didn't look right to me.  I re-checked the theory and it was clearly telling me that output X should be less than output Y, but that wasn't how the numbers were coming out.  Something was wrong somewhere. 

After staring at the code a while, and running a few unhelpful tests, I decided to go back to square 1, and just run the code in the "old" configuration, where I knew exactly what I should get.  And I didn't get it. 

That helped tell me where to look.  Sure enough, a couple minutes later, I found the "bad" line of code;  last project, I must have wanted to look at queues with constant service times instead of exponential service times, and I had just changed that line;  now I needed it changed back.  And all is well with the world again. 

I'm sure there are some lessons in there somewhere -- about documenting code, about setting things up as parameters instead of hard-wiring things in, all that good stuff one should do but doesn't always.  It catches up to you sooner or later.  Meanwhile, the code is back to running, and in about 24 hours I'll hopefully have the table I need.