My Biased Coin

A Good Problem to Have

2012-01-28T21:31:00.000-05:00

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

2012-01-26T19:35:00.000-05:00

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?

2012-01-25T18:34:00.000-05:00

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...

2012-01-20T15:58:00.000-05:00

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

2012-01-09T14:54:00.003-05:00

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

2012-01-08T23:25:00.000-05:00

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

2012-01-07T18:43:00.000-05:00

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

2012-01-02T23:59:00.002-05:00

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.

New Year's Thanks

2011-12-30T15:51:00.000-05:00

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...)

Cross-Cultural Learning Curve: Sending a Paper to Science

2011-12-29T11:23:00.002-05:00

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.

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

2011-12-27T18:17:00.000-05:00

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.

Wasted Hour(s)

2011-12-26T23:24:00.000-05:00

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.

MIC and MINE, a short description

2011-12-22T22:54:00.004-05:00

I thought I should give a brief description of MIC and MINE, the topic of our Science paper. Although you're probably better off, if you're interested, looking at our website, http://www.exploredata.net/. Not only does it have a brief description of the algorithm, but now we have a link that gives access to the paper (if you couldn't access it previously) available on this page, thanks to the people at Science.

Our starting point was figuring out what to do with large, multidimensional data sets. If you're given a bunch of data, how do you start to figure out what might be interesting? A natural approach is to calculate some measure on each pair of variables which serves as a proxy for how interesting they are -- where interesting, to us, means that the variables appear dependent in some way. Once you have this, you can pull out the top-scoring pairs and take a closer look.

What properties would we like our measure to have?

First, we would like it to be general, in the sense that it should pick up as diverse a collection of possible associations between variables as possible. The well-known Pearson correlation coefficient, for example, does not have this property -- as you can see from this Wikipedia picture

it's great at picking up linear relationships, but other relationships (periodic sine waves, parabolas, exponential functions, circular associations) it's not so good at.

Second, we would like it to be what we call equitable. By this we mean that scores should degrade with noise at (roughly) the same rate. If you start with a line and start with a sine wave, and add an equivalent amount of noise to both of them in the same way, the resulting scores should be about the same; otherwise the method would give preference to some types of relationships over others.

I should point out that the goal behind these properties is to allow exploration -- the point is you don't know what sort of patterns in the data you should be looking for. If you do know, you're probably better off using a specific tests. If you're looking for linear relationships, Pearson is great -- and there are a large variety of powerful tests that have been developed for specific types of relationships over the years.

Our suggested measure, MIC (maximal information coefficient), is based on mutual information, but is different from it. Our intuition is that if a relationship exists between two variables, then a grid can be drawn on the scatterplot that partitions the data in a way that corresponds to that relationship. Suppose we have a grid, with x rows and y columns; then this grid induces a probability distribution, where the probability associated with a box on the grid is proportional to the number of data points it contains. Let I_G be the mutual information of the grid. We aim to maximize I_G/ log min(x,y) -- this is the MIC score. (We bound x, y values to avoid trivial cases like every point having its own box; see the paper for more details.) MIC values are between 0 and 1, and we can approximately compute MIC values heuristically. Our work shows via a mix of proofs and experiments that MIC appears to have the properties of generality and equitability we desire.

Based on the approach we use to find MIC, we suggest several other possible useful measures, and we refer to the collection as MINE (maximal information-based nonparametric exploration) statistics. For example, MIC - Pearson^2 turns out to be a useful measure for specifically finding nonlinear relationships. When MIC is high (close to 1) and Pearson is low (close to 0), there is a relationship that MIC has found but it is not a linear one; for linear patterns, both MIC and Pearson are high, and so this measure is close to 0. Other measures we have measure things like deviations from monotonicity -- useful for finding periodic relationships.

Should MIC/MINE prove useful, I believe there's lots of theoretical questions left to consider. The approach is currently essentially heuristic, although we do prove a fair number of things about it. Proving more about its properties would be useful, as well as improving the complexity to compute the relevant measures.

Next up: more about the experience of working on this project.

Congratulations to Hanspeter Pfister

2011-12-18T12:04:00.001-05:00

Despite our really very good track record for the last decade or so, there are some people out there who remain under the misimpression that it's impossible to get tenure at Harvard.

So I'm very happy to announce that Hanspeter Pfister has achieved the impossible, and is now a tenured Harvard Professor.

Hanspeter works in graphics and visualization, doing the usual sort of things like replacing your face in videos and designing 3-d printers that work like a Star Trek replicator. But he has also developed a large number of collaborations with domain scientists, finding interesting and important visualization problems in things like diagnosing heart disease and mapping the brain.

We're all happy he'll be staying around. Hooray for Hanspeter!

This Week, I Am A Scientist

2011-12-16T07:39:00.000-05:00

This week, I am a scientist; I know this, because I have an article in Science.

It's nice to have something to point to that my parents can understand. I don't mean they'll understand the paper, but they'll understand that getting a paper in Science is important, more so than my papers that appear other places. And because they're probably reading this, I will also point them to the Globe article appearing today about the work, even though the article rightly focuses on the cool and unusual fact that the lead authors are two brothers, David and Yakir Reshef.

I had been planning to write one or more posts about the paper -- both the technical stuff and the great fun I've been having working with David, Yakir, my long-time colleague Hilary Finucane, the truly amazing systems biology professor Pardis Sabeti, and others on this project. (See Pardis's Wikipedia page or this site to see how Pardis rocks!) But between Science's "news embargo" policies and my own end-of-semester busy-ness, I blew it. I'll try to have them out next week. But for now, for those of you who might be interested, here's the link to the project web page, and here's the abstract:

Detecting Novel Associations in Large Data Sets

Abstract: Identifying interesting relationships between pairs of variables in large data sets is increasingly important. Here, we present a measure of dependence for two-variable relationships: the maximal information coefficient (MIC). MIC captures a wide range of associations both functional and not, and for functional relationships provides a score that roughly equals the coefficient of determination (R2) of the data relative to the regression function. MIC belongs to a larger class of maximal information-based nonparametric exploration (MINE) statistics for identifying and classifying relationships. We apply MIC and MINE to data sets in global health, gene expression, major-league baseball, and the human gut microbiota and identify known and novel relationships.

Consulting

2011-12-15T21:47:00.000-05:00

As I've probably mentioned, I generally enjoy my consulting work. Besides the obvious remunerative aspects, consulting provides challenges, insights, and experiences that are quite different from academic work.

On the other hand, taking red-eyes and having to get up at 4 am for a 6 am flight to a meeting in another city -- both of which I had to do this week -- I could happily do without.

Grading

2011-12-14T23:19:00.000-05:00

Some folks at the NSDI meeting were nice enough to say that it was nice that I was blogging again. Sadly, I've been under-the-gun busy for the last several weeks, but it was a reminder that I should be getting back to this now and again.

One thing that's taken my time the last week is grading. I was teaching my graduate course this semester, on randomized algorithms and probabilistic analysis, using my book as the base. Unfortunately, I teach this course at most every other year, which means it's hard if not impossible to find a suitable TA. (As for my own students, Zhenming is on an internship this semester; Justin's on fellowship and essentially required not to TA. Also, both have been extremely busy this semester doing really great work, so why would I want them to TA instead of doing their research now anyway?) So this year I didn't have one. Which means I graded things myself.

It's been a while since I've graded a whole course. I do grade exams (with the TAs) and one full assignment (myself) every year in my undergraduate class. But grading every week is really at least as bad as having to do homework every week. I'd say worse; very little interesting thinking involved, just a lot of reading, checking, and moving papers or files around in a time-consuming fashion. Somehow, though, I don't think the students sympathize.

I think I remember one graduate class in Berkeley where a student (or maybe a group of students) were required to take on the grading every assignment. I like that plan. In fact, right now I like any plan that doesn't involve me grading the next time I teach this class. One plan is of course no/minimal homework, or homework without grades. However, I do believe students learn by doing homework, and I've found that in most circumstances a grade is the motivator that makes them get the homework done, so I'll have to find a plan that involves grading somehow.

Plane Work

2011-12-06T16:18:00.000-05:00

I dislike flying, but I have a few flights coming up.

I find that engaging in "real thinking" about problems while on a plane is generally beyond me. (I'm jealous of all of you that somehow manage this.) Similarly (or Even) writing code takes more focus than I can manage on a plane. But I do try to make my plane time useful.

Luckily, it's the end of the semester, so I think I'll be bringing the last homeworks and final exams to grade on board this time around.

Reviewing (conference) papers is something I manage on plane flights. I'm sure that says something about the level of my reviews. On the plane my goal isn't to read the paper in same depth that I'd read a paper I'm trying to understand for my research; it's to assign a score (sort) and write down useful comments. (Which, I guess, is my goal for conference reviews off the plane as well. And why I wouldn't do journal reviews on planes.) If you get a review you don't like, I suppose now you can always assume you can assign the blame to the fact that I was on a long plane flight. But I don't think I'll have any reviews this month.

Reviewing proposals is even better than reviewing conference papers on a plane. I often get foreign governments sending me proposals to review for them, and they often pay some nominal amount. If I know I have a flight coming up, I sometimes say yes. It makes me feel like I'm doing something useful on the flight, and even getting paid for it.

When all that fails, I try to read a mindless book. (It's always good to have one on hand for those interminable periods where your electronic devices must be turned off.) I slipped up and started reading V is for Vengeance at home. (I think I've read all the Kinsey Millhone books from A, but I started at around H, and can't recall if I found all the earlier ones. I wonder what she'll do after Z?) I've been saving Mockingjay for a plane flight though. (I try to read what my kids read. So I'm also quite familiar with Percy Jackson.) I've read most of Robert Parker's books in the air.

Finally, sometimes, I fall asleep. I've gotten reasonably good at sleeping on flights. Then I don't get the work I thought I'd get done on the plane done. But it definitely feels like a good use for the time.

The End (of the Semester) is Nigh

2011-12-03T10:36:00.000-05:00

If you've missed it (which probably means you're not a theorist and/or a blog-reader), you should check out the (entertaining) controversies of the last week or two, starting with Oded's guest post on the decline of intellectual values in Theoretical Computer Science, and then whether a lowering of the matrix multiplication exponent counts as a "breakthrough" (see follow-up blog posts here, here, and here).

I've enjoyed watching them develop, but have been happy to let them go on without putting a big target on my back. I've also been too busy getting through my last lectures, making up a final exam, trying to get some grant proposals ready on ridiculous deadlines, and dealing with administrative issues like prepping slides for an end-of-semester faculty retreat. Occasionally I try to fit in meeting with students and (last of all) working on research. I know the end of the semester is a mad rush for students, finishing projects and papers and getting ready for exams. Sadly, I feel the same way this year. Another week or two and it will be all over, and like the students I think I'm ready to let things go for a couple of weeks of holiday time.

But probably I'll stay up late after the kids are in bed and try to do some of that research stuff. There are some fun problems that have been waiting for attention most of the semester, and I'd like to see what happens if I'm finally able to give them some.

Letters of Recommendation Time. Ugh.

2011-12-01T14:58:00.000-05:00

I don't mind writing letters of recommendation for students. It's part of the job. It's a good thing to do.

I just mind dealing with the new e-application sites. I'd rather hand my letter off to an admin and have them send it. The good old days...

To see what I'm talking about, I'm now a huge non-fan of Embark -- here's their "help page", which explains that I may have to wait 5+ minutes for my pdf to upload, without really explaining why

Round Two Reviewing : An Exercise in Conditional Probabilities

2011-11-21T10:38:00.000-05:00

We're in "round 2" of reviews for NSDI, and it's brought up a problem for me I've noticed before. I worry that, subconsciously, I'm inclined to give papers I read on the second round a higher score, since I'm swayed by the fact that they've in fact made it to the second round.

I wonder if anyone in the PC world has done any testing of this to see if it's a real phenomenon. Are second round reviews on a set of papers statistically different from the first round of reviews? I would bet yes, even controlling for the fact that the papers made it to the second round. In particular, I'd suspect it's much harder for people to give a score of 1 (=reject) to a second round paper.

One could imagine attempting to test for this by sticking a few obvious rejects from the first round into the second round reviews. Indeed, perhaps one should make this part of the process: randomly select a few clear rejects to go into round two, and announce that you're doing this to the PC. Then they might not feel so averse to assigning a score of 1 in the second round.

One joy in the second round reviews is once you submit a review you get to see the first round reviews. So far, I feel I've been calling them fairly; when I haven't liked a second round paper, the first round reviews seem to confirm my opinion. So perhaps (with some effort) I'm keeping my subconscious at bay successfully, and not conditioning on the fact that it's a round 2 review.

Public University Budgets

2011-11-16T20:11:00.000-05:00

Another topic that arose in conversations during my visit to Wisconsin was the issue of budgets, and in particular the large-scale cuts that many of the best US public school are having to deal with. It's not hard to find information on this. My first search on Google yielded this article about what's going on in Wisconsin (taking choice quotes, not the full article; it's from June).

Wis. Gov. signs budget cutting education $1.85B

Democrats assailed the budget as an attack on middle class values since it cuts funding for public schools by $800 million, reduces funding to the UW system by $250 million and cuts tax credits for poor people.

It also reduces the amount schools can collect from property taxes and other revenue combined, which translates into another education cut of about $800 million. While schools are seeing deep cuts, Walker's budget extends tax breaks to manufacturers, multistate corporations and investors.

"As a state, we can choose to take the easy road and push off the tough decisions and pass the buck to future generations, or we can step up to the plate and make the tough decisions today," Walker said in prepared remarks. "Our budget chooses to fix our problems now, so that our children and our grandchildren don't face the same challenges we face today."

I'm sure the children and grandchildren he talks about, who will have to face the new challenge of increased global competition with an increasingly better educated non-Wisconsin population instead of the challenges being faced today, will be very appreciative.

Public universities generally have been faring quite badly in the current financial crisis. I have a deep pro-education bias, unsurprisingly, so I find this depressing. But also, in my mind, it's just not sound financial sense. I believe these cuts today will yield a corresponding decline in Wisconsin's economy tomorrow, for some appropriate notion of tomorrow. A dollar spent on education should be worth... well, I don't know how much it should be worth, but my guess is the multiplier on the dollar is pretty high. I'd like more information to back that up. If you know of any studies that demonstrate the payoff for education -- the sort of thing all of us in the education field should have on hand when discussions like this come up -- please leave them in the comments. It would be nice to have a collection handy.

Yes, We Are Hiring (2012)

2011-11-15T14:30:00.000-05:00

Harvard CS will be hiring this year.

One tenure-track position is geared toward systems, very broadly defined.

A second tenure-track position is in Applied Math, where we're aiming for a "discrete applied math" person. The right CS theory person could fit just fine. And if we see great CS theory people who really want to be in CS rather than AM, we should be able to find a way to make that work.

Here's the link to the ad for both. Here's the URL: https://www.seas.harvard.edu/csjobs. And the ad text follows. Spread the word!

Tenure-Track Positions in Computer Science and Applied Mathematics

The Harvard School of Engineering and Applied Sciences (SEAS) seeks applicants for positions at the level of tenure-track assistant professor in the fields of Computer Science and Applied Math/Computer Science, with an expected start date of July 1, 2012.

Candidates are required to have a PhD or an equivalent terminal degree, or to be able to certify that they will receive the degree within one year of the expected start date. In addition, we seek candidates who have an outstanding research record and a strong commitment to undergraduate teaching and graduate training.

Position 1: Computer Science. We welcome outstanding applicants in all areas of computer science. We are particularly interested in systems, broadly defined, including compilers, programming languages, distributed systems, databases, networking, and operating systems. Applicants will apply online at http://academicpositions.harvard.edu/postings/3825.

Position 2: Applied Math/Computer Science. We welcome outstanding applicants in all areas of applied mathematics or theoretical computer science. We are particularly interested in topics at the boundary or intersection of these fields, including optimization, applied probability, scientific computing, combinatorics and graph theory, approximation algorithms, and numerical analysis. Applicants will apply on-line at http://academicpositions.harvard.edu/postings/3824.

In terms of applications, areas of interest include computational science, engineering, or the social sciences. We encourage applications from candidates whose research examines computational issues raised by very large data sets or massively parallel processing.

The Computer Science and Applied Mathematics programs at Harvard University benefit from outstanding undergraduate and graduate students, an excellent location, significant industrial collaboration, and substantial support from the Harvard School of Engineering and Applied Sciences. Information about Harvard's current faculty, research, and educational programs is available at http://www.seas.harvard.edu.

Required documents include a CV, a statement of research and teaching interests, up to three representative papers, and names and contact information for at least three references.

Applications will be reviewed as they are received. The review of applications will begin on December 15, 2011, and applicants are strongly encouraged to submit applications by that date; however, applications will continue to be accepted at least until January 15, 2012.

Harvard is an Equal Opportunity/ Affirmative Action Employer. Applications from women and minority candidates are strongly encouraged.

Public Salary Information

2011-11-14T13:12:00.000-05:00

While visiting Wisconsin last week (enjoying very pleasant company and conversation), various issues came up.

For one, I was reminded (or recalled) that as a public university, University of Wisconsin-Madison salaries are available online. I can understand why salaries of elected public officials, and the people they hire, should be public information. Transparency in politics is a valuable thing.

But I don't see that professor's salaries should be public. Perhaps this is merely a personal bias; I wouldn't want MY salary to be public information.** I also don't use Facebook, so perhaps I'm just a 20th century privacy-desiring relic. Perhaps more reasonably, I don't see university faculty as political employees, and therefore think they -- as well as the university -- should enjoy the same privacy for salary information that other employers and employees enjoy.

Perhaps, however, I'm just wrong, and transparency of salary information is good for all. I'm willing to entertain that thought. Certainly I think the Taulbee survey that aggregates salary information is useful and good information, for both universities and faculty, as I think there's a shortage of accurate comparative salary information for faculty positions (as compared to other jobs), and the Taulbee survey provides an important information baseline. Is it so far to go from there to individual's salaries?

How do those of you at schools where your salary information is public information feel about this? And the rest of you?

** Although perhaps in some sense it is. I don't believe my NSF grant budgets are publicly accessible information, but at some point, I was informed by my university that a Freedom of Information Act request had been made for one of my funded proposals. (I don't know why, though I have some suppositions.) The university filed paperwork to hopefully make sure that personal information, including my salary, would be redacted.

CAEC: First Cambridge Area Economics and Computation Day

2011-11-10T21:40:00.000-05:00

Giorgos suggested I remind people about CAEC, which will be next week (November 18).
Still time to sign up and register.

Here's the link.

Programming for Non-Programming Exercises

2011-11-09T12:02:00.000-05:00

One of the exercises I assigned last week proved interesting:

Consider n points on a circle, labeled clockwise from 0 to n-1. Initially a wolf begins at 0 and there is a sheep at each of the remaining n-1 points. The wolf takes a random walk on the circle; at each step, it moves with probability 1/2 to one neighbor and with probability 1/2 to the other neighbor. (0 and n-1 are neighbors.) The first time the wolf visits any point it eats the sheep that is there. (The wolf can return to points with no sheep.) Which sheep is most likely to be the last eaten?

If you haven't seen it before, you might try it; don't put the answer in the comments, though, since I'll use the problem again.

While grading the assignment, I found a number of students had simulated the process, figured out the answer from the simulations, and then used that knowledge to prove the desired result. The problem didn't ask for them to do it, but they did it themselves.

That was great (and I told them so). That's how solving research problems often works for me. I have to understand what's going on, and in many cases, that understanding comes about by simulating a process to figure out how things behave. Then I go back and try to prove what I think I'm seeing in the simulations.

My worry, though, is that the students that did it this way were primarily the "non-theorists" in the class, who did it because they knew they didn't know the answer, and thought it was easier to code to figure it out. And that the "theorists" in the class correspondingly thought they knew the answer (rightly or wrongly) and went ahead with the calculations without doing a simulation. That's not necessarily a bad thing, certainly not for this problem (which is easy enough), but I'd also like for the theorists to also get into a mindset of doing simulations in this sort of setting, both as a tool to gain insight before trying to prove things and as a check on their proofs.

I think they're probably getting the lesson from other, harder exercises I give. Still, it was nice that a number of people in the class went that direction (and thought to write it down in their assignment).

A Tale of Talks

2011-11-07T22:57:00.000-05:00

A bunch of talks today.

Carla Gomes gave a talk at CRCS (Harvard's Center for Research on Computation and Society) to talk about her work on computational sustainability -- interdisciplinary research with "the overall goal of developing computational models, methods, and tools to help manage the balance between environmental, economic, and societal needs for sustainable development." How to use optimization, machine learning, and math and computation more generally to help with problems in "the real world", like designing paths for animal migration or designing control systems for energy-efficient buildings. Fun stuff.

Then I had to take Harvard's M2 shuttle over to the Medical School Area for the Broad Institute's annual retreat. Some students who I have been working with on a project spanning systems biology, computer science, and statistics were giving a 15-minute presentation of their results. (More on the work at some later date.) The scale there is a bit larger than I'm used to; I think over 1000 people were listening to the talk, which might well make it the most seen presentation of my work (even if we sum over multiple presentations of the same talk). Happily, the students really nailed it, both in the presentations and the follow-up Q and A.

Then the shuttle back for Mark Zuckerberg's Q and A session at Harvard. I don't think I've seen him speak before, and he's actually much more well spoken than one might expect if you saw The Social Network. He was entertaining and captivating, and I'm sure inspired many of our students. It was a full room -- you needed to get a ticket to get in. I understand recruiting sessions with students are taking place sometime after. If there are good writeups I'll link to one here later.

I also have my own talks to work on. I'll be giving two talks at U. of Wisconsin this week. One "old" talk on cuckoo hashing, and one "new" talk on verification using streaming interactive proofs. Come on by if you're in the area. (Of course, I suspect if you're in the area, you're probably a student or faculty member of U. of Wisconsin.)

Funny E-mail of the Day

2011-11-04T11:16:00.000-04:00

I've having some issues getting straight answers over e-mail from an administrator in some Harvard office I'm dealing with. This morning, I found the following e-mail in my inbox:

Dear Mmichael,
To be clear,

Sent from my iPad

Well, now, this is entirely the problem, isn't it?

This Week, We Were Doing Security

2011-11-02T13:48:00.000-04:00

If you look on Yelp's engineering blog (http://engineeringblog.yelp.com/2011/10/output-filtering-failure.html), you'll see Yelp's VP of Engineering, Michael Stoppelman, crediting our team (myself, John Byers, and Giorgos Zervas) for finding a privacy ``leak'' in their system that occurred on the mobile version of the Yelp site, m.yelp.com. Their post describes the issue from their point of view. We'd like to elaborate a bit further by presenting how things appeared from our end.

Before beginning, though, we should say that Yelp's team responded in what seems to us to be an exemplary fashion. After we contacted them, Michael Stoppelman and members of the engineering staff listened to our presentation and description of the vulnerability seriously, and, as they describe in their blog post, took immediate action to correct the problem. While it would be fun to have a security horror story to tell (right around Halloween) of a big company not taking the leakage of user information, or us as researchers, seriously, that absolutely was not the case here. Indeed, when we expressed that we should make the issue public after the problem was fixed, both to transparently inform their users and to possibly help prevent a similar problem on other web sites, they agreed to write a blog post about it, and let us read the copy in advance to make changes or offer suggestions -- and except for making sure Harvard, Yale, and Boston University were all credited, we didn't have any to add.

As people may know from our previous work, we have been studying sites such as Yelp, as they provide an interesting case study as a social network that provides economic information in the form of reviews. As part of our research and data collection, Giorgos was looking at their various interfaces, including the Yelp mobile web site. To be clear, he was not ``hacking'' the site in any way, just interacting with it via a standard browser and normal HTTP requests. He found that when he checked a restaurant for reviews, and subsequently clicked on the button asking for more reviews, entire reviewer records were leaked in JSON format, in the manner described in Yelp's blog post. While this data was present in HTTP replies, and was visible to an HTTP logger such as Firebug for Firefox, or via the built-in logger for Chrome, ordinary users accessing the site from a device such as an iPhone would not observe sensitive information, as client-side Javascript displayed only the non-sensitive information (such as the review text, date, and the user's handle). This example shows the importance of having multiple redundant layers of security when handling personally identifiable information; in the Yelp post, they describe the redundancies they have added to prevent such leakage in the future.

While there was no financial information involved, it seemed to us to be a severe hole, in that personally identifiable information was being sent in the clear in response to a normal and seemingly not infrequent user request. We spent some time verifying what we saw, checking that we were not mistaken and that the vulnerability could potentially leak information at scale. When we were fully convinced the problem was both real and significant, we contacted Yelp.

We did have concerns as we went; we have heard stories of some businesses blaming the messenger when approached with significant security issues. We were pleased that Yelp responded by thanking us rather than blaming us. In our minds, this was a very positive interaction between university researchers and an Internet business.

Giving credit where credit is due, Giorgos deserves the lauds for finding the problem and thereby protecting a lot of user data.

Lisa Randall on the Daily Show

2011-10-27T08:08:00.000-04:00

Last night's Daily Show (link to full episode) was on fire.

The first segment was focused on SCIENCE! The part with Aasaf Mandvi was simultaneously hysterical and very, very, very sad.

The last segment had guest Lisa Randall -- Harvard physicist and author of the new book Knocking on Heaven's Door: How Physics and Scientific Thinking Illuminate the Universe and the Modern Worldas well as the old book Warped Passages: Unraveling the Mysteries of the Universe's Hidden Dimensions -- talking about science also. While I understand Lisa has many tremendous accomplishments, appearing on the Daily Show is the one I am jealous of.

Students are Awesome(ly Productive Right Now)

2011-10-26T15:05:00.000-04:00

What's the use of a blog if you can't brag about your students? And my students have all been doing great stuff, so I'm excited to let others know about their work. In random order...

Zhenming Liu's paper Information Dissemination via Random Walks in d-Dimensional Space will be appearing in SODA 2012. It looks at a very natural random walk diffusion question that hadn't been solved. Here's the arxiv version, and a slightly edited down abstract:

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the $d$-dimensional space $\{-n, ..., n\}^d$ at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al.'s work, which solved the problem for $d \leq 2$. We present tight bounds up to polylogarithmic factors for the case $d \geq 3$.

Justin Thaler's paper on Practical Verified Computation with Streaming Interactive Proof was accepted to ITCS 2012. I think part of its "innovation" is how well Justin puts together the theory with the implementation, showing how practical this line of work could be. Here's the arxiv version, and again a slightly edited down abstract:

When delegating computation to a service provider, as in cloud computing, we seek some reassurance that the output is correct and complete. Yet recomputing the output as a check is inefficient and expensive, and it may not even be feasible to store all the data locally. We are therefore interested in proof systems which allow a service provider to prove the correctness of its output to a streaming (sublinear space) user, who cannot store the full input or perform the full computation herself. Our approach is two-fold. First, we describe a carefully chosen instantiation of one of the most efficient general-purpose constructions for arbitrary computations (streaming or otherwise), due to Goldwasser, Kalai, and Rothblum. This requires several new insights to make the methodology more practical. Our experimental results demonstrate that a practical general-purpose protocol for verifiable computation may be significantly closer to reality than previously realized. Second, we describe techniques that achieve genuine scalability for protocols fine-tuned for specific important problems in streaming and database processing.

Finally, Giorgos Zervas's work on Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications, which I've already discussed on the blog since it got so much press play, was also just accepted to WSDM. Giorgos is no longer my student, but working with me and Joan Feigenbaum as a postdoc, so I'll count him in the mix.

An Exceptional Exponential Embedding

2011-10-25T01:07:00.000-04:00

This week in class I get to teach one of my favorite probability arguments, which makes use of a very unusual embedding. Here's a short description (for the longer description, see the book or the original paper, where the idea is ascribed to Rubin).

The setting is balls and bins with feedback: I have two bins, and I'm repeatedly randomly throwing balls into the bins one at at time. When there are x balls in bin 1 and y balls in bin 2, the probability the ball I throw lands in bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p). Initially both bins start with one ball. The goal is to show that when p is greater than 1, at some point, one bin gets all the remaining balls thrown. That is, when there's positive feedback, so the more balls you have the more likely it is that you'll get the next one in a super-linear fashion, eventually the system becomes winner-take-all.

We use the following "exponential embedding". Consider the following process for bin 1. At time 0, we associated an an exponentially distributed random variable X_1 with mean 1 = 1/1^p with the bin. The "time" that bin 1 receives its next ball is X_1. Now it has two balls. We then associate an exponentially distributed random variable X_2 with mean 1/2^p with the bin. And so on.

Do the same thing with bin 2, using random variables Y_1, Y_2, ...

Now, at any point in time, due to the properties of the exponential distribution -- namely, it's memoryless, and the minimum of two exponentials with mean a_1 and a_2 will be the first with probability proportional to 1/a_1 and the second with probability 1/a_2 -- if the loads in the bins are x for bin 1 and y for bin 2, then the next ball will fall into bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p). That is, this exponential process is equivalent to the initial balls and bins process.

Now let X = sum X_i and Y = sum Y_i. The infinite sums converge with probability 1 and are unequal with probability 1. So suppose X < Y. Then at some finite "time" in our exponential embedding, bin 1 receives an infinite number of balls while bin 2 just has a finite number of balls, and similarly if Y < X. So eventually, one bin will be the "winner" and take all the remaining balls.

In my mind, that's a beautiful proof.

ITCS Review

2011-10-22T00:45:00.000-04:00

The list of accepted papers for ITCS (Innovations in Theoretical Computer Science) is up.

Some thoughts:

1) I have expressed reservations in the past about ITCS, based on the idea that it was creating another conference similar to FOCS and STOC, where instead we should be "fixing" FOCS and STOC, for example by expanding it. I suppose my reservations this year are muted. While the titles don't suggest to me that ITCS is necessarily a home for more "innovative" papers than FOCS/STOC, there seems to be no inclination to expand these conferences, so why not have yet another conference where 40 very good papers can go? (Indeed, why not make it a bit larger? I'm not sure how many submissions there were; hopefully someone can confirm, but I'd guess the acceptance rate was roughly 20-25%?)
2) Another issue was ITCS was in China it's first two years, making it seem a bit "exclusive". (Not to Chinese researchers, of course; and not to authors, who were given funds for the trip. But it is a far distance to go for others.) This year, it will be at MIT, which hopefully will attract people from up and down the East Coast (weather permitting), and help it build up a longer term audience.
3) 5 out of the 40 papers have Quantum in the title. Should this be telling us something?
4) Talk I'm most looking forward to: Compressed Matrix Multiplication by Rasmus Pagh. (I've already read and enjoyed the paper.) But I'm also looking forward to seeing Algorithms on Evolving Graphs, if only based on the title.

An Apple a Day

2011-10-20T11:30:00.000-04:00

Reviewing papers for a conference is a slow, time-consuming process. Suppose you had 20 reviews due and about 4 weeks to do them. What's your approach?

I take the tortoise approach. I first try to do a quick pass over all the papers to at least have some idea of the topics and themes I'll be dealing with in the papers. This lets me find papers that, at least on a fast first reading, seem unusually good or unusually bad, and lets me see if any papers are sufficiently related that they should be compared to each other implicitly or explicitly when I do my reviews. But then, I try to set aside time to do one review a day, more or less. I'll enter the review, press the button, and put it up for others to see. I won't go back and revise things until the first round is over unless another paper I'm reading or another review I see makes me rethink substantially. At the end, I'll go back and check that my scores seem consistent, given that I've seen my full set of papers. Slow forward progress, with an eventual finish line.

Doing a paper a day does mean I limit the time I put into each review. While there's some variance, I almost never let myself go down a rabbit hole with a paper. That's not always a good thing; sometimes, finding a bug in a proof or a similar serious flaw in a paper takes several hours of careful thought, and unless I pick up that's there a problem right away, I often miss it while going on to the next review. (This is just one good reason for why we have multiple reviewers!)

Perhaps another reason this is not always a good strategy: I'm told it's noticed that my reviews are actually done on time, and apparently this leads to people asking me to be on PCs.

John Byers on WBUR

2011-10-18T15:24:00.000-04:00

Listening to my co-author, John Byers, streamed live on WBUR, discussing our work on Groupon. Ben Edelman is another participant in the show.

Here's the link.

Listen

2011-10-12T16:01:00.000-04:00

A colleague outside theory (but inside computer science) recently brought up an interesting question with me that seemed like a possible research-level issue. We had some back and forth, trying to figure out what we each meant (naturally, our "vocabularies" are a bit different in how we describe the problem), what the actual question was, and if there was a direction to go. After a couple of rounds of this, he thanked me. Paraphrasing: "I appreciate your patience. My experience is other theorists are often immediately dismissive to these sorts of questions."

I was taken aback. First, I'm not sure patient is a word commonly used to describe me. Second, this colleague is a first-rate genius (with the track record to prove it). Who wouldn't listen to what they have to say? Quite frankly, I was happy they were interested in talking to me!

But it's been gnawing at me. If a high-powered colleague outside theory has this impression of theory and theorists, how do we appear to others? Was this an isolated opinion, or a common feeling?

I know 20 years ago, back when I was in graduate school, the theory/systems divide was quite large, at least at Berkeley. There seemed to be minimal communication among the faculty groups. Indeed, in part that was one reason that, at the time, the LogP paper seemed like such a big deal; Dick Karp had successfully crossed over and worked with the systems side to build a model for parallel computation! It was, sadly, notable, if only because such collaborative work had seemed so rare.

I've generally felt that while this theory/systems divide was still much larger than I might personally like that there had been a lot of progress since my grad student days. I feel I can point to a significant number of examples. But perhaps I'm holding the unusual opinion. Maybe there's still not enough listening going on, in at least one direction.

Reading Confidence Men

2011-10-10T08:46:00.000-04:00

My current spare time reading* is Confidence Men, Ron Suskind's book on Wall Street and the Presidency. Without "taking sides" with regard to Larry Summers, I have to admit enjoying reading this paragraph:

"It all boils down to the classic Larry Summers problem: he can frame arguments with such force and conviction that people think he knows more than he does. Instead of looking at a record pockmarked with bad decisions, people see his extemporaneous brilliance and let themselves be dazzled. Summers's long career has come to look, more and more, like one long demonstration of the difference between wisdom and smarts."

In Summers's defense(?), there are lots of people who would fit this description...

* As a parent who tries to read what my kids are reading, my future spare time reading looks to be the similarly political but less timely Mockingjayand the new-to-me series Artemis Fowl. Recommendations for 8-10 year-old readings welcome.

Submissions, A Comparison

2011-10-09T08:22:00.000-04:00

I just got my set of NSDI papers to review, and have been looking them over.

One thing that immediately strikes me as I give them a first quick pass is how nice it is that the submissions are 14 double-column pages. The authors have space to present a meaningful introduction and a reasonably full description of and comparison with related work. They can include (detailed) pseudocode as well as description of their algorithms. They have space for a full page (or more) of graphs for their experimental results, and even more space to actually explain them. The papers actually make sense, in that they're written in sequential order without having to flip over to "appendices" to find results. The phrase "this will appear in the full paper" appears rarely -- not at all in most papers. The papers are, as a consequence, a pleasure to read. (Well, I can't vouch for the actual content yet, but you get what I mean.)

As a reviewer, it's also nice that if I tell the authors they've left out something that I think is important, I'll generally have confidence they'll have space to put it in if the paper is accepted, and that it's a reasonable complaint to make, in that they ostensibly had space to cover my issue. (There are some papers which fill the 14 pages and perhaps won't have something obvious that could be removed, but experience suggests they'll be rare.)

So I wonder again why theory conferences have 10-page single-column submission formats ("appendices allowed"!), or, even worse, for conferences like ICALP and ESA, they have final page counts of 10-12 pages in the over-1/2-blank-page LNCS format. (Really, it's just about enough space for an abstract, introduction, and pointer to your arxiv version.) Interestingly, for my accepted SODA papers this year -- which went with 10 page submissions, "full versions" attached on the back, but had 20 pages for accepted papers -- both sets of co-authors didn't want to bother when the final submission deadline came around to filling the 20 pages, figuring people could just be pointed to the arxiv (or eventual final journal) version. Why create yet another version of the paper according to arbitrary page limitations? I certainly couldn't suggest a good reason.

On the theory side, as I've maintained for years, we're doing something wrong with our submissions, with artificial page limits creating more mindless work for authors and making decisions more arbitrary than they need to be.

Goodbye to Steve Jobs

2011-10-06T18:34:00.000-04:00

My Mac laptop froze today. It was an unusual occurrence; I turned the machine off, and for a minute it wouldn't turn back on again. I was in a panic.

Then it went back to normal.

After the fact, I was wondering if my machine was having its own minute of silence. Then I had the morbid idea -- what if Steve Jobs had the power to arrange for all Mac products and iProducts to stop working when he died? It would be a disaster for so many of us -- not just the loss of individual data, but the loss of the platforms and devices he made reality, that so many of us use and love.

Steve Jobs may be gone, but his legacy lives on.

New York Times

2011-10-01T23:58:00.001-04:00

Our work on daily deals is mentioned and linked to in Sunday's New York Times (front page). (John Byers even got a quote in!) It was also mentioned in this week's print edition of Time magazine. (Behind a paywall, so here's a jpeg.)

Sadly, the name Mitzenmacher doesn't appear on these items. ("...researchers from Boston University and Harvard..." seems to be a common phrase), so I continue to toil happily in relative obscurity.

My brother points out that this is all just an example of why print media is disappearing. He says most anyone who might have seriously cared about our work would have heard about it two weeks ago on the Internet. The print media is just getting to it now? They're two weeks behind.

Allerton Part 2 : Venue Change?

2011-09-29T12:37:00.000-04:00

Yesterday, I thought the best talks I saw were by Devavrat Shah and Dina Katabi.

Dev was talking about how to track where rumors start. The model is you have a graph of nodes that have been infected (by a rumor, or disease, or whatever), and based on the the shape of that graph, you want to figure out where the process started. To get a picture of what I mean, suppose you were looking at a grid graph, and the infected area looked roughly like a circle. You'd expect the infection started somewhere near the middle of the circle. They've placed this in a mathematical framework (a distribution for the time to cross an edge, starting with tree graphs, etc.) that allows for analyzing these sorts of processes. This seems to be the arxiv version of the work.

Dina talked about 802.11n+, which they describe as "a fully distributed random access protocol for MIMO networks. 802.11n+ allows nodes that differ in the number of antennas to contend not just for time, but also for the degrees of freedom provided by multiple antennas." By making use of nulling and alignment, they can extend 802.11 so that instead of competing for time slots, multiple antenna systems can compete for degrees of freedom within a time slot, allowing those devices with multiple antennas to take full advantage (and in particular allowing them to overlap transmissions with devices with fewer antennas). I would have heard about it earlier, I guess, if I had gone to SIGCOMM this year. The project page is here.

There's a whole session this morning on "mean field analysis" and games. Mean field analysis (in my loose interpretation) means pretend your system gets big and turn it into a differential equation -- apparently a useful way to tackle various large-scale distributed agent/learning systems. It's what I used to study load-balancing systems way back for my thesis (and still find an occasional uses for today). Interesting to see it used for another set of problems. Ramesh Johari's student (I didn't catch which one) gave a talk on a really interesting model of dynamic auctions with learning where you could gain some real insight using a mean-field analysis. (How much should agents in an auction "overbid" when they're learning their value for winning an auction? It depends on how much they think they'll gain in the future based on what they learn about their true value.) This seems to be a preliminary version of the work.

Now for the "negative" -- something I'm going to suggest to the Allerton folks. It's time, I think, to find a different location. The Allerton conference center is very beautiful, but it's not suitable, in many respects, for this event any more. I was told there were about 330 registered attendees from outside UIUC, plus an additional 120 or so from UIUC. It's a bit hard to turn that into a true count; many (most?) UIUC people probably drop by 1 day, most attendees probably 1.5-2 days of the three. But Allerton really wasn't designed for a crowd that large. If you're not in one of the "big rooms", and people want to come to your talk, many times they can't get in. For example, the social network session was remarkably popular; the room could seat 40 people, and there were about 20+ people crowded around and outside the doorway -- which was not only not ideal, but it was also disruptive, as the open door meant a lot of noise in the room. Actually, the acoustics aren't particularly good in any of the rooms, even the big ones. Attendance in the early am is very low, in part I think because people staying "in town" have a non-trivial drive to get to Allerton.

When the event was smaller, like 200-250 people, everyone coped with these problems. It's really not working now.

I can understand there's an attachment to the Allerton center -- and how could it be the "Allerton conference" (next year is it's 50th year!) if it wasn't at Allerton? But this has been an issue for years, and only seems to get worse. There must be a conference venue on or near UIUC campus that would work as well -- at the very least, my opinion is it's time to look....

And now, back to the airport...

Allerton 2011

2011-09-28T15:03:00.000-04:00

I woke up at an absurdly early hour this morning to get on a plane and go to the Allerton conference. I'm giving a talk this afternoon on Invertible Bloom Lookup Tables (arxiv link) (joint work with Michael Goodrich). It's a "lookup table", not a Bloom filter, because you want to be able to store key-value pairs; you query for a key, and get back a value. It's invertible, because besides being able to do lookups, you can "invert" the data structure and get back all the key-value pairs it contains (with high probability, assuming you haven't overloaded the structure). This paper is really on the theory, but if you want to see a cool use for IBLTs, there's a paper by Eppstein, Goodrich, Uyeda, and Varghese from this year's SIGCOMM (Efficient Set Reconciliation) with a compelling application.

Allerton is a different sort of conference, as I've discussed before (like here and here, among others). A mix of invited and submitted papers, a wide diversity of topics, lots of parallel sessions. It seems absurdly crowded this year -- I had to park in the ancillary parking because the lot was full, and the rooms where the talks are held all seem to be bursting. (The conference, unfortunately, really has outgrown the space where the conference is held.) I'm guessing well over 300 registered; I'll have to check. The conference gives me a chance to catch up with colleagues who are more on the EE/networking side; I've seen other CS theorists here in years past, but I haven't noticed anyone yet.

If you're here, maybe come by my talk this afternoon, or say hi if you see me hanging around.

Set Competition

2011-09-27T21:46:00.000-04:00

As an applied probability exercise, I had my class compute empirically the probability of a game failing on the nth round for the game of Set. (See my previous post about this; here failure means there's no set on the nth round, and they were asked to implement the "choose a random set" strategy if there was more than one.) They were also supposed to try to calculate the probability of using all 81 cards in sets through the course of the game -- what we might call a perfect game.

Some students explored a bit and noted that changing from the random strategy could significantly increase the probability of a perfect game. So I think the next time I decide to use this assignment, I'll turn it into a competition. Students will have to develop a strategy that maximizes the probability of achieving a perfect game. Prizes will go to the best strategy (which hopefully could be easily determined after a few billion runs or so -- I suppose I'll have to introduce some sort of computational limits on the strategy to ensure that many runs can be done in a suitable time frame), and the best "succinct" strategy -- that is, the best strategy that can be described in English in at most a few reasonable sentences.

It's also interesting to think about optimal strategies in the offline case, where the permutation determining how the cards will be dealt out is given in advance. I keep thinking maybe there's a way to effectively calculate whether a perfect game can be found for a given permutation, and then thinking there can't be. (Though, admittedly, I haven't thought a lot yet.) So maybe it makes sense to run the competition for both the online and offline versions of the problem.

Beyond Worst Case Analysis Workshop

2011-09-21T23:53:00.000-04:00

I'm just off a plane coming home from the Beyond Worst Case Analysis Workshop at Stanford. It went really well, and I really enjoyed it.

I think a variety of things made it work. First, and I apologize to Tim Roughgarden for saying it, but the execution was superb -- someone should make him organize more things. Great room, great food, great staff on hand (thanks to Lynda Harris for being incredibly helpful), and a great collection of speakers. Also, an excellent location. Stanford is relatively easy to get to with 2 major airports nearby (but avoid the cabs -- it's now over $100 to take a cab from SFO!), and the location guarantees an audience of Stanford, Microsoft, and Google folks. (While not everyone was there all the time, I understand well over 100 people were registered.)

To the content. It was a great program -- apparently the talks will be on the web later, so you may want to check them out if you weren't there. My favorites would have to be Dan Spielman's talk on smoothed analysis (perhaps because Dan just always gives great talks), and Kevin Leyton-Brown's talk on statistical methods (using learning theory) to predict an algorithm's performance on new instances. (Can you predict the running time of your satisfiability algorithm accurately before running it on a specific instance very quickly just by taking a careful look at the problem? The answer seems to be -- yes you can!)

There was a panel that focused on questions like "Where could we point students to work on these sorts of problems. What are the currently most glaring examples of algorithms whose properties are poorly explained by existing theoretical models, where there might be hope for progress?" and "To what extent can "real-world data" be modeled? Is it important to model accurately the properties of "real-world data"?" While the panel ended up being fairly uncontroversial -- I'm afraid no fights or even major disagreement broke out -- I found it very interesting to listen to the others on the panel give their opinions and insights on these questions.

I think people got into the spirit of the workshop. Kevin, an AI person by trade, found it amazing that theorists were getting together to talk about heuristics and experiments. (Kevin's talk was followed by Dick Karp talking about his work on tuning and validating heuristic algorithms -- though of course not all talks were on that theme.) It will be interesting to see if this workshop inspires any specific new research -- but even if not, it was well organized, well put together for content, and well worth the trip.

My talk slides are here.

Guest Post on NYCE (Giorgos Zervas)

2011-09-20T09:25:00.002-04:00

GUEST POST by GIORGOS ZERVAS

I was at NYCE 2011 this past Friday. It was a thoroughly enjoyable and productive experience. I feel like I got a conference's worth for the cost of and time commitment of a long commute.

The day started with three hour-long plenary talks, followed by lunch and a poster session, followed by an hour of 10 minute talks, and concluded with two more plenary talks. (And all of that for about $20.)

It turns out a lot can be squeezed into 10 minutes. Halfway into the first speaker's talk, with 5 minutes left on the clock, I was almost convinced he was running out of time. Everyone worked great around the time constraint to succinctly deliver their talks.

The plenary talk roster was varied and exciting (at least by one other account). I particularly enjoyed Jonathan Levin's talk on eBay experiments (pdf of the paper) in part because I was least familiar with it, and in part because I think I can use his key method. Here's the gist: instead of relying on random observations look for experiments that have been conducted on your behalf by market participants. To use his eBay example, auctions have a bunch of parameters: the item, its starting price, its reserve price, and so on. Quite often it turns out you can find sets of auctions ("experiments") that are identical in all but one parameter. This allows you to directly quantify the effect of the varying parameter. To say I wish I'd thought of this is an understatement -- I am trying to convince myself that I actually didn't. (I didn't.)

Of interest -- likely to myself only -- was the passing mention of Swoopo in two plenary talks. Their sudden demise still puzzles me. While writing our Swoopo paper they were running about 200 auctions a day. A few months after EC'10 when I checked again they were running about one hundred. They were responding to reduced demand but why were "entertainment shoppers" driven away? The business model certainly did not die as others have successfully taken Swoopo's place. One possibility is that the barrier to entry in this type business is low. Around Swoopo's peak there were people making money off penny-auction scripts they'd sell for a few hundred bucks. Hundreds of clones sprung. Buy a script and some hosting, run auctions, and ship directly from Amazon. In an interesting parallel the daily deals business also seems to have a very low barrier to entry judging from the hundreds of Groupon clones. I am still kicking myself for stopping data collection after our Swoopo paper was done.

Back to NYCE itself, if there is one thing I'd maybe have wanted to see more of is student talks (especially of the 10 minute variety). I guess the poster session made up for this but as someone with a poster to present I didn't have to chance to walk around and see others'. Which reminds me, thanks to everyone who stopped by my poster, and to the organizers for putting everything together!

Travels and Teaching

2011-09-16T09:47:00.000-04:00

I'll be at the Beyond Worst Case Analysis workshop next week, and Allerton the week after. For each, I'll have to miss a class. I also have some other travels that may involve missing classes this semester as well -- I'll be missing more class than usual this semester, but they're for good reasons.

I'll have Justin and Giorgos cover a lecture for me (thanks, guys!), but next week I'm doing an experiment: I'm substituting videos for my class. I've pointed them to 2005 MSRI workshop Models of Real-World Random Networks, and having them watch some talks. One is my survey talk on power laws, so it's still "me" teaching, but then I have a few impressive "guest lecturers" from the workshop to cover the rest; all the talks focus on power laws in some way. I've even put together an "in-class" exercise for them to do on the subject -- out of class, of course.

I wonder if this is a good approach or not. I'll have to ask the students. It's not ideal, but either is cancelling class. Has anyone else started using videos as a solution to the missed lecture problem? Are there ways to make it a more useful experience?

By the way, looking back, that 2005 MSRI workshop had a bunch of interesting talks. Worth checking out sometime if you're interested in the area. I looked younger then.

Reminder : Giorgos has a poster at the New York Computer Science and Economics Day today. Go check it out!

This Week, I Am Part of an Internet Meme

2011-09-15T08:21:00.000-04:00

My frequent co-authors John Byers, Giorgos Zervas, and I posted an extended version of a current submission to the arxiv (as people do), which showed up last Friday or thereabouts. Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications discusses some analysis we did on daily deal sites (Groupon, LivingSocial), including interactions between daily deal sites and social network sites (Facebook, Yelp).

The work got a plug Monday on the MIT Technology Review. They naturally focused on our most "controversial" finding, and I quote them:

"A Groupon deal might boost sales but, it can also lower a merchant's reputation as measured by Yelp ratings, say computer scientists who have analyzed the link between daily deals and online reviews."

Apparently, many people are interested in statements of that form, especially business types, and that's where the fun started. We got some e-mails from people who work for firms that use statistical analyses in planning marketing efforts who had seen the article (and wanted our not-yet-released data set). We noticed the review article was getting tweeted. We started tracking a tweet feed to find out where else it was showing up. (As a very partial list, Business Insider, Chicago Tribune, The Independent, Search Engine Journal.) Monday we were worried that people might try to actually call us up and talk with us, but fortunately, that hasn't happened. Instead of feeling pressured, we've just been able to enjoy watching.

It's amusing to see how these things spread through the Internet. A lot of sites are just cutting and pasting from the MIT Tech Review. I know this because, in what I personally find to be the most amusing of mistakes, they refer to Giorgos as "Georgia Zervas". Giorgos does seem to have multiple name spellings (he also uses Georgios), but Georgia is not quite right. (It is, however, my new nickname for him*.) Georgia Zervas, according to Google, has popped up almost 200 times in the last 3 days.

We weren't really expecting this. I think part of the reason we didn't expect much reaction is pre-summer we put up a placeholder with some initial data: A Month in the Life of Groupon. This didn't seem to get much notice. Indeed, we had submitted it to NetEcon, and were essentially told by reviewers the paper was too boring. I must admit I disagreed, then and now, with the reviewers. But, to be fair, that version of the paper didn't contain the data sets and analysis for LivingSocial, the Facebook Likes, and the Yelp reviews; it just had Groupon data (though we made clear this was an "appetizer" and more was to come). John actually completely disagrees with me. I quote: "For the record, I agree with the NetEcon reject decision. They should be applauded for making us do more work." My take was the bar for a workshop paper was too high if this wasn't sufficiently interesting. Giorgos wonders if by John's logic we're hoping the paper gets rejected again.

Also, we didn't get nearly the same sort of attention for our previous similar-in-spirit work analyzing penny auction sites like Swoopo (entitled Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank). Daily deal sites are MUCH bigger, and I suppose the results for Swoopo are a bit harder to summarize for mass consumption.

Anyhow, Giorgos will be at the New York Computer Science and Economics Day this Friday with a poster on the subject. Stop by and talk with him! (Giorgos recently completed his PhD at BU, and is doing a Simons postdoctoral fellowship with Joan Feigenbaum, while also hanging out some with me at Harvard as an affiliate of our Center for Research on Computation and Society.)

* Don't worry Giorgos. I'm kidding. Sort of.

SODA Accepts -- The Count

2011-09-14T02:38:00.000-04:00

People in various have been noting the SODA accepts, but nobody has been talking about the numbers. I count 138 papers accepted. I can't find now how many submissions there were; I recall it was over 600 abstracts, but I think it cut down to 520-540 or so. So this seems like just over 25%.

Is that a good number? Too many? Too few?

I admit, I have trouble believing that there weren't at least 40, 50, maybe 100 of those rejected submitted papers that were of sufficient quality that it would have been just fine to have them in. I could be wrong -- I wasn't on the committee -- but I'd guess there was more good stuff out there.

For those papers that were rejected, where will they go? ICALP and ESA deadlines are pretty far off; there aren't a lot of good homes for algorithmic papers until then. (STOC/FOCS may not be appropriate; other conferences and workshops have, I think, weaker reputations that may make them less desirable, especially for up-and-coming students and younger faculty.) It seems like there's a hole in our schedule. Rather than fill it with yet another conference, wouldn't the community be better off accepting more?

Rabin's Birthday Celebration

2011-09-13T00:23:00.000-04:00

While I was not blogging, we spent the few days before the semester started with an 80th birthday workshop for Michael Rabin. Impressively, we were able to pull it off despite the best efforts of Hurricane Irene, thanks to the many speakers who made an extra effort to get there, well beyond the call of duty. Because some speakers couldn't make it (flight cancellations), and we were worried about storm cleanup, we postponed the start until Monday afternoon, but other than that, it went fantastically well. (A credit to the organization of Les Valiant!)

Richard Lipton described it all in this blog post, so I don't have to. (The only negative thing in his post is that he refers to me as Mitz -- clearly because it's the easiest way of distinguishing me from the guest of honor, he doesn't call me that regularly -- which feels strange to me as I haven't been called that regularly since middle school.)

If any coding theory people are reading this, I thought I'd point out that the slides for my talk (as well as the slides for many of the other talks), which was on coding theory, are available here. In particular my talk is about how Michael Rabin's JACM paper on the Information Dispersal Algorithm was remarkably prescient, setting up some basic ideas and foundations for both the later work in LDPC codes and network coding. While the paper is far from unknown (Google scholar has it at well over 1000 citations), I'm not sure how widely appreciated the paper is in the coding theory circles; it was a pleasure for me to go back and reread it with new eyes to prepare for this talk.

Blogging Again?

2011-09-12T10:15:00.000-04:00

My thoughts that I would blog more over the summer, during academic "down time", turned out more of a fiction than I would have thought. The summer proved remarkably busy, with plenty of research, administration, consulting (the economy must be coming back?), and, more enjoyably, time with the kids. The blog was low priority.

With the school year starting, I actually feel I have things to say, so we'll try again.

Classes have started, and Harvard's continuing growth in CS, well, it continues. Our intro CS course ended up with about 500 students last year; this year, we've currently got 650 enrolled. Our 2nd semester programming course designed primarily for majors has gone from 70 to 110 enrolled. Most importantly for me, our intro theory course (the Turing machine class) went from about 55 to 75. My algorithms and data structures class tends to be just a few less than that 2nd semester, so I'll have to plan for a jump up. (My biggest year was 90, back in the (last) bubble days; I'm not sure we'll ever get back there, as students have more class choices now.)

Really, we're trying to put more resources early in the pipeline to attract students to the intro course -- and we seem to be in a healthy positive feedback loop, which is (over time) pushing all the numbers up in later courses. Apparently tech is popular again.

I'm teaching randomized algorithms and probabilistic analysis, a graduate course that splits 1/2 grad and 1/2 undergrad. Currently I have 23 students, which is a nice and healthy but not earth-shattering number.

It's exciting to come back and see these numbers continuing to go up. No wonder we're #2 on Newsweek's Schools for Computer Geeks. (And no, we don't take that seriously.) Besides giving some evidence that we're on the right track, it should make the case for hiring more in CS easier to make.

SIGCOMM Webcast

2011-08-16T10:20:00.002-04:00

Got a note from the ACM that SIGCOMM is being live Webcast the next few days. (I'm not in Toronto for it -- hello to everyone who is!)

A simple click and I'm listening to SIGCOMM talks. Fun.

The link is http://www.weyond.com/sigcomm/webcast/

Listen in as you can.

Fun Links, via Google+

2011-08-01T21:03:00.000-04:00

One fun aspect of being on Google+ is occasionally a link comes along worth further notice.

The first, from David Karger, is a link to a report (by Democrats, says David) refuting a previous report (by Republicans) that had argued that the NSF was wasting a bunch of money on frivolous research. The link is here. Jon Kleinberg was one of the listed "frivolous" projects -- apparently studying pictures on social networks isn't considered important by those with an agenda -- and he has a brief response in the report.

The second is an editorial by S. Keshav, about the "hyper-critical attitude of paper reviewers", spurred by the fact that CCR had no technical articles, because all the submissions were rejected. I certainly have something to say on the issue (having, for example, recently had a conference rejection where 3 knowledgeable reviewers said the paper should be accepted, one unknowledgeable reviewer said the paper was too theoretically challenging for the systems audience, and apparently decided to take an uninformed stand at the PC meeting...). But rather than tell a long story here, I'll just point you to the editorial....

Tact

2011-07-22T18:37:00.000-04:00

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

2011-07-22T13:10:00.000-04:00

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!)

Rabin's 80th Birthday Celebration

2011-07-18T16:09:00.000-04:00

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 https://www.events.harvard.edu/web/4352.

SODA in Japan

2011-07-12T15:00:00.000-04:00

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....

Using Google Scholar for More Than Your h-Index

2011-07-09T11:27:00.000-04:00

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.

h-index != impact

2011-07-08T13:27:00.002-04:00

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
but
citations are not how we define or even measure cool work, excitement, and enthusiasm

Various Goings On

2011-07-06T21:58:00.000-04:00

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.

Odd SODA Rules, and Other Conference Paper Complaints

2011-07-01T20:01:00.000-04:00

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.

UC Budget Woes

2011-06-29T15:50:00.000-04:00

The new California budget call for $650 million in cuts to the UC systems -- I understand $500 million had already been planned, they added $150 million on top of that, and may add more later if the revenue numbers don't pan out.

I'll admit that as a long-time CA resident (that's where I grew up), and a UC Berkeley alum (for grad school), it pains me to hear this. I'm very sympathetic to statements such as this one quoted in this San Francisco Chronicle piece:

"Some students don't even call the increases "tuition" anymore, but tax increases. They say state lawmakers are deceptive in claiming to have passed the budget without raising taxes."

I grew up in a California where we really believed we were a shining vanguard for the rest of the nation -- and the UC system was a very big part of that. By the time I left California I, at least, didn't have that feeling about the state any more. And these cuts, of course, are painful to hear.

I don't mean to make it sound like the UCs are dead -- they have too many brilliant faculty to count, and will continue to attract many top students. But it seems to me they are being weakened, perhaps (and I hope not) even crippled longer term. I hope that this is just a historical blip, and California's greatness -- including vibrant, powerful, and more healthy UC and CSU systems -- will be on full display the rest of the century.

Addendum:

Michael Goodrich (who I've had the pleasure of working with lately) has suggested that all this points to (high) double-digit percentage increases in UC tuition coming up. He pointed me to several news bits from the UC news site on the cuts generally and tuition specifically, including this, this, and this, and pointed me to the UC Regents site, where you can find things like the minutes to their meetings.

Probability Assignments Using Set

2011-06-24T15:55:00.000-04:00

I'm gearing up for teaching my graduate course on randomized algorithms and probabilistic analysis next semester. It's been a while since I've taught it, and I'm somewhat uncertain what to do with the course, precisely since I wrote the textbook. Me lecturing from the textbook is boring, both for me and for them, but of course the textbook contains exactly what I think is important.

Somehow I'll have to have them read the textbook offline and try to do more online learning in class. I'm working through creating some programming exercises based on the game Set. (Amazon picture below.)

Set is a great card came (wikipedia entry, or the Set web site). As it says in Wikipedia, "The deck consists of 81 cards varying in four features: number (one, two, or three); symbol (diamond, squiggle, oval); shading (solid, striped, or open); and color (red, green, or purple)." You turn over 12 cards, and look for a set, which is three cards so that for each feature, EITHER all cards are the same in that feature, or they are different. So below is an example of a set. (different in each feature). If they cards were all green, it would still be a set -- they can be all the same in some features, and all the same in others, and still be a set.

<p>&amp;amp;lt;br&amp;amp;gt;&amp;amp;lt;br&amp;amp;gt;</p>

The first player to find a set picks it up, and replacement cards are dealt in to get you back to 12 cards. The player with the most cards at the end of the game wins. My eldest had already seen the game in school, and after a few months, she and I now are pretty competitively matched. I'd put it up there with Mastermind as a good mental exercise game for kids.

So the reason I thought about Set for my class is that the game instructions say that the odds of not getting a set with 12 cards dealt out is 33 to 1. (When this happens, or you can't find one, you can deal another card out; with 15 cards, the claim is more than 2500:1.) But when you play the game, it seems you don't find a set much more often. While my daughters and I are probably missing some sets some of the time, it's also clear that conditional probability is coming into play here. At any point in the game, there aren't 12 random cards on the table. Most clearly, suppose I deal 12 cards, find a set, and replace the 3 cards. What's left isn't 12 random cards; it's 9 cards left after a set was removed, and 3 cards remaining from the deck.**

This seems like a nice way to introduce conditional probability in a concrete but perhaps subtle way. And it seems like there are plenty of other related questions one can ask as well. (What's the probability of not finding a set on the kth turn, given a set has been found in the first k-1 turns...) Feel free to suggest exercises. (Apparently the largest number of cards without a set is 20. I wonder if there's a short proof of that without just doing exhaustive search.)

At the very least, it will be a good excuse to get a couple of boxes of Set for the office.

Have to go. My daughter just asked to play a game of Set...

** Of course I'm not the first to have noticed this. Peter Norvig posted on it as well.

New Books Worth Looking At

2011-06-19T20:49:00.000-04:00

New books are coming out all the time, but here are two big ones that stick out in my mind (perhaps because I've seen the authors recently). [Feel free to mention others worth noting in the comments.]

Recently available (I saw copies at FCRC) is The Design of Approximation Algorithms (Amazon link) by Williamson and Shmoys. Here's a link to the book page. (All books have web pages now, don't you know.) An up-to-the-moment books on approximation algorithms by two well-known experts.

Coming soon is The Nature of Computation (Amazon link) by Cristopher Moore and Stephen Mertens. Here's a link to the book page. About 1000 pages of introduction to computer science (with some statistical physics, and maybe some other physics, mixed in), with lots of problems. I've seen a preview of the text and it looks like an interesting read. (I'm curious if people will use it for courses -- if you have or are considering it, let me know.)

NSF Changing Broader Impacts

2011-06-17T08:32:00.000-04:00

The NSF is changing its description of its merit criteria -- specifically, what the Broader Impacts criteria will be. The details are still being worked out, and comments are being collected until July 14. More information can be found on this NSF page.

The current draft text states:

Collectively, NSF projects should help to advance a broad set of important national goals, including:

Increased economic competitiveness of the United States.
Development of a globally competitive STEM workforce.
Increased participation of women, persons with disabilities, and underrepresented minorities in STEM.
Increased partnerships between academia and industry.
Improved pre-K–12 STEM education and teacher development.
Improved undergraduate STEM education.
Increased public scientific literacy and public engagement with science and technology.
Increased national security.
Enhanced infrastructure for research and education, including facilities, instrumentation, networks and partnerships.

This list is much more concrete than how I normally think of the current NSF Broader Impact statement. However, it still seems rather vague and open-ended. Most proposals can easily claim to help enhance increased economic competitiveness or development of a globally competitive STEM workforce. Perhaps that is for the best: proposals will have to make a compelling case that their work has broader impact, but there can be many ways to accomplish that.

It does seem, though, that this list isn't particularly theory-friendly. Cryptographers can point to national security; my algorithmic work can certainly point to academia-industry partnerships and economic competitiveness. But more complexity-related proposals, or algorithmic proposals with less clear immediate practical applications -- where do they fit in? Should it be a national goal to support more theoretical research with long-term and unclear payoffs? (I think so, particularly as that sort of research is generally relatively very cheap and has potential for huge benefits.) How would you place such research in the above Broader Impact context, or should a new bullet be added? What else would you add?

Dr. Georgios Zervas

2011-06-16T20:25:00.000-04:00

Congratulations to Georgios (alternatively, Giorgos), who defended his thesis today.* (There's still some paperwork to get in, but we drank the champagne afterward, so I'm calling it official.) He gave a great presentation covering some of our old work (on analyzing Swoopo, and efficient keyword value computation) plus some of our work-to-be on studying Groupon. (We've put an appetizer up on arxiv; now that this defense is done, we can finish preparing the main course this summer.) I hope to have the chance to swipe the slides and his jokes and give the talk myself sometime; however, if you'd like an interesting talk on data-driven e-commerce analysis, you should of course just invite him to present it instead.

Three cheers for Dr. Georgios Zervas.

*Giorgos is co-advised by me and John Byers.

NY Times on Computing

2011-06-13T14:40:00.000-04:00

A couple of days ago there was a NY Times article on computing being cool (again), including a shout-out to Harvard's own CS 50 and of course the Social Network.

Matt Welsh has a take on it, but please also look for my comment (#7) if you read it. The issue seems worthy of further discussion -- yes, learning how to make something useful quickly is a really exciting aspect of computer science, but it's not what defines computer science as a field -- which may be taken up here later (or in comments at Matt's blog).

2012 PCs

2011-06-12T14:21:00.000-04:00

In an effort to return to normalcy, I find myself agreeing to serve on PCs again this year.

NSDI 2012 call for papers is up. Dina Katabi and Steve Gribble went with the old "The PC meeting will be in Boston" ploy -- very clever, made it hard to say no. They also politely asked that I avoid referring to them as stupid or misguided, and I'm expecting that to be an easy requirement to fulfill. Please send interesting papers, so I have something entertaining to read.

I will, finally, be on an ISIT PC, for ISIT 2012. No information up yet that I know of. But it will be held in Cambridge, MA, a little over a year from now. So it rates to be a HUGE conference. (ISIT is normally in the 700-800+ range, as I recall, so I wouldn't be surprised to see it hit 1000+ here.)

For balance, it might be nice to serve on a (CS) theory PC later in the year. (I was recently asked by one, but the timeline overlapped directly with ISIT, so I declined.) Or not -- I'm sure I'll have papers to push around here at Harvard.

ITCS

2011-06-08T16:42:00.000-04:00

I was asked to post the call for papers for the (renamed) Innovations in Theoretical Computer Science conference. (I'm glad they finally changed the name -- see previous posts here and here.)

This year the conference is moving out of China, where it was well-funded and the logistics were taken care of, to the US. I think this will be a defining year for the conference, as it tries to set out what it should be. The question I continue to have is how it should distinguish itself from and/or relate to FOCS/STOC/SODA. There seems to be a significant bloc in the theory community that is against making these well-established conferences any bigger; to me, this says that we don't need yet-another-conference with the same type of papers unless it's different somehow. So submit and help decide what the identity of ITCS will be.

FCRC Continued

2011-06-07T12:19:00.000-04:00

I've been enjoying FCRC; of course, I like large conferences where lots of people show, as long as they're run well. Rooms have been pretty full at the talks, and lots of people around to talk to. I still don't understand why people object to the idea of making FOCS/STOC larger (and instead seem to prefer to create new conferences and workshops), but if that's the way the theory community wants it, I'd argue that more conference co-location is a good way to go.

I thought Les Valiant gave an excellent Turing lecture -- I'm sure it will be online soon. He provided a clear scientific challenge -- understanding how evolution could have accomplished so much in so little time (just several billion years) -- and made the case the computational complexity (and in particular learning theory) would be a necessary tool in developing an understanding to this problem. I thought especially he did an excellent job gearing the talk to a general computer science audience, limiting the technical discussion and giving a broad overview of the importance of complexity theory, particularly as it might apply in this setting.

Naturally, my favorite session so far has been the "randomized algorithms" session (1A) for STOC, including The Power of Simple Tabulation Hashing (Patrascu/Thorup), Tight Bounds for Randomized Load Balancing (Lenzen/Wattenhofer), and Social Networks Spread Rumors in Sublogarithmic Time (Doerr/Fouz/Friedrich). The first paper shows that tabulation hashing, while only being 3-wise independent, can provide strong theoretical bounds (and excellent practical performance) for most of the natural application of hashing. The second paper looks at parallel load balancing strategies, and shows that many of the lower bounds proven years ago can be beaten by loosening assumptions that led to the lower bounds in quite natural ways. The third paper considered randomized rumor spreading in social network graphs, including the surprising result that taking care not to (randomly) send a message to the same neighbor in consecutive rounds changes the asymptotic behavior (to just barely sublogarithmic) in this setting. All three of the talks were well-presented, making getting up for an 8:30 session worthwhile.

I'd have to say that the STOC poster session -- done for the first time -- seemed to be a successful experiment. There were plenty of people around talking to the poster presenters, so much so that that it didn't seem to wrap up until more like 11 instead of the scheduled 10:30. Hopefully students who presented will comment on how they liked the experience -- either on this blog, or, more directly, with e-mail to the organizers -- and let them know if they found it valuable. I think getting students to present their work in this way will encourage and benefit them greatly and thereby strengthen the field.

Harvard CS Hires (2011 Edition)

2011-06-06T01:01:00.000-04:00

At FCRC, I'm getting asked a lot about hiring. Our hiring season still isn't quite yet finished, but I'm going to go ahead and announce three new faculty who will be joining Harvard. (At least, that's what they've told me!)

On the theory side, Jelani Nelson will be joining us, though in a delayed fashion, as he'll be postdoc-ing first. I know this was reported in a comment on Lance's blog some time ago (before he formally accepted our offer, in fact), so I'm glad to be able to confirm it's correct.

Ryan Adams, who works in machine learning and computational statistics, will also be joining us, and we're thrilled to have hired someone in this increasingly key (and highly competitive) area. Ryan was a student of David MacKay, for whom I've previously expressed worship (most recently here).

On the systems side, Eddie Kohler, well known for his work on the Click router as well as many other systems projects, will be joining us. Non-systems people may know him as the writer of HotCRP, the best conference management software available today. (Yes, I've said it!)

More seriously, we're very excited that all three of these outstanding researchers will be coming to Harvard, allowing us to broaden the department's scope and capabilities significantly. While I'd like to take all the credit (and am totally fine with anyone who wants to give it to me), the real credit goes to David Parkes, who led the search committee this year, and of course all the rest of the highly overworked search committee members.

FCRC : Awards Banquet

2011-06-05T11:55:00.000-04:00

I got to FCRC a little early to attend the ACM Awards Reception and Banquet. (Les Valiant nicely put my name on a list.) For more on the awards you can also go the ACM award page. They have a nice little award booklet they gave out at the reception, but it looks like last year's is still up on the page -- I imagine they'll update it soon. They also had copies of the latest Communications of the ACM out, which is sporting a cover with an extremely nice picture of Les on it.

It was a very nice and extremely well-run event. It was black-tie optional, and I was one of the half in a regular tie. It's odd to see that many computer scientists I know in a tux -- certainly not something I've ever seen before! It was at the Fairmont, in a suitably-large-sized space, and with much better food than I was expecting (and after flying all day, I was suitably hungry to enjoy it). While there were a lot of awards to go through, they kept it moving along quite quickly, so it didn't drag on at all. (I'd like to thank the award-winners, for keeping their speeches both short and entertaining.) The theory highlights were of course Les for the Turing Award, but also Craig Gentry received the Grace Murray Hopper Award for his work on fully homomorphic encryption, and Kurt Melhorn received the Paris Kanellakis Theory and Practice Award for his work leading to LEDA. Bryan Parno, a Harvard undergrad and CMU grad student, received the Doctoral Dissertation Award. On the systems side, Frans Kaashoek received the ACM-Infosys Foundation Award. And of course there were the new ACM Fellows.

Thanks to everyone involved.

Justin's Poster at FCRC

2011-06-01T13:26:00.000-04:00

Justin Thaler, a student I'm advising (or, quite arguably, the other way around), will be at the poster session for STOC, ready to talk about a bunch of his currently-under-submission work on streaming interactive proofs, including the most recent, Practical Verified Computation with Streaming Interactive Proofs (with me and Graham Cormode). Justin has been working for some time on streaming problems with the following motivation: you're gathering a big data set that you're going to store, and compute on, on the cloud. How do you trust that the cloud is going to give you the right answer? A natural theorists' answer is via an interactive proof, and here the natural limitation is to a streaming verifier: a verifier that sees all the data initially, forwarding it to the cloud, but can't store it all due to limited memory, including later when the prover (the cloud) wants to prove that it's done the computation correctly.

We didn't initiate these models, to be sure. There's now been a chain of work, including the "annotations" paper by Chakrabarti, Cormode, and McGregor, which was a primary motivator. For Justin's other theoretical work, see the arxiv version of his ESA paper (with me and Cormode, journal version under submission) and this paper of his with Cormode and Yi (under submission).

Some time ago I challenged Justin to figure out if this work on streaming verifiers was "practical" for real-world cloud settings, and if not, why not. The outcome (so far) is the Practical Verified Computation with Streaming Interactive Proofs paper. We're not the only ones to have noticed that perhaps interactive proofs are ready for deployment in these kinds of real-world systems. Apparently, there was a recent HotOS paper, Toward Practical and Unconditional Verification of Remote Computations, on the same theme, by real-live honest-to-goodness systems people. I'll avoid (biased) comparisons, and leave that to others.

But I can highlight some of what Justin's done. He's considered and implemented both special-purpose "building-block" functions, like self-joins (or F_2 computations), and a fully general approach for arbitrary computations based on the "Muggles" protocol (interactive proofs with polynomial time provers). He's considered and implemented both non-interactive protocols, where the prover sends a single message that includes both the answer and the verification, and interactive protocols, where the prover and verifier have a multi-round conversation to verify the result. Along the way he's had to come up with several "engineering" improvements (with some strong theoretical foundations) to make things practical, including a clever use of FFTs for the non-interactive protocols that seems new, and adopting the approach of linearizing polynomials from previous work on interactive proofs to improve efficiency to these protocols.

Our experience, I think, shows that with some significant engineering, interactive proof systems in the streaming verifier setting are ready for real systems. So if you get a chance stop by and ask Justin more about the work. He's eager to talk about it!

Deletion Channel Pointer : Kanoria and Montanari

2011-05-30T11:53:00.000-04:00

For those half a dozen of us in the world who care about the deletion channel (and perhaps I'm overcounting), I'm a bit late in pointing to the now available extended version of the Kanoria and Montanari paper from ISIT last year. It follows a path laid out by my student Adam Kirsch by looking at an information theoretic characterization of the channel, but then uses a perturbation analysis to get the right degree distribution and very tight bounds as the deletion probability goes to 0. There's still plenty we don't understand about the deletion channel, but this paper moves us forward nicely.

Practical Uses of Induction

2011-05-26T23:23:00.002-04:00

See! Who says this stuff isn't useful....

Annual Facing the Reviews

2011-05-25T14:38:00.000-04:00

Teaching reviews for spring (Algorithms and Data Structures) came in today; time to face the music once again.

Actually, this year, my numbers were up substantially; still room to improve, of course, but unlike the last two years, they didn't make me cringe. If it seems surprising that my teaching numbers would go up when I'm now busy being Area Dean, it seems clear that the credit actually goes to the class. This was easily the best class of students I've had in several years -- a really strong bunch. I think the delta in scores reflect their capabilities more than anything else.

It's always interesting to see the contradictions embedded in the responses. This year, I decided to take advantage of the opportunity to ask specific questions, and asked the class if they preferred the written assignments or programming assignments (and why), and which lecture they would want to see removed/not want to see removed. It was almost 50-50 for the written/programming assignments, with a slight edge to written assignments. And it seems like for every person who really liked the primality testing/RSA lectures, or the least common ancestor/suffix tree lectures, or the lecture on heuristics, there's another who would remove the exact same things. This is entirely consistent with feedback I've gotten directly over the years. You can't please everyone. (Sorry, that should be "I can't please everyone." I shouldn't speak for you.)

A number of students commented on how valuable the material was. The negative version of this is that the course is "CS broccoli" ("you really ought to take it, but you probably won't enjoy it much"), but the positive version is much more pleasant -- the class really shapes how you think about problems, and is IMPORTANT knowledge for CS majors. I made a point this semester of really emphasizing the point that correctness is a design consideration that can be traded off with other performance metrics like time and space, and multiple students commented specifically on finding that idea exciting.

On the downside, I'm still intimidating to some students (on the other hand, several others took me up on my open invitation to go to lunch with them this semester), the exams are too hard, and they want more feedback. And there are too many math majors coming in and messing up the curve.

How is this last problem handled elsewhere? It's almost tempting to have a CS theory course for CS majors and a harder course for math majors. Is it fair to have an "honors track" within the class for the math types and modify the grading curve accordingly?

If you're from the class and you've stumbled on this -- congratulations on making it through. Even if your grade wasn't as high as you might have liked, please don't let it get you down. As you move on how you do on problem sets and timed tests is less important; it's what you can accomplish with the knowledge you've gained. So accomplish something great, and come back and show off to me -- I'll be eager to see it!

NSF Bows to Blog Pressure (Tongue-in-Cheek)

2011-05-20T20:15:00.000-04:00

As some of you may recall, I accused the NSF of being "misguided" in changing its graduate fellowship policy to effectively disallow teaching.

So I was please to get home tonight and see that some students had forwarded me the following e-mail from the NSF:

Dear Colleague:

The purpose of this memorandum is to inform you of recent developments
in the NSF Graduate Research Fellowship Program (GRFP). There was a
recent change in policy that NSF has decided to reconsider. In
particular, the policy concerns what can be expected of Fellows during
the three years they receive NSF funding (on tenure). NSF has decided
to reinstate the previous policy with respect to this issue while
further study is conducted to inform this and other GRFP policies.
The policy that will be in effect during the 2011-2012 Fellowship Year
is an updated version of the one described in the 2009 Guide (NSF
09-62), which is as follows:

Each Fellow is expected to devote full time to advanced scientific
study or work during tenure. However, because it is generally accepted
that teaching or similar activity constitutes a valuable part of the
education and training of many graduate students, a Fellow may
undertake a reasonable amount of such activities, without NSF
approval. It is expected that furtherance of the Fellow's educational
objectives and the gain of substantive teaching or other experience,
not service to the institution as such, will govern these activities.
Compensation for such activities is permitted based on the affiliated
institution’s policies and the general employment policies outlined in
this document.

You can refer to the 2011 Guide (NSF 11-031) at
http://www.nsf.gov/publications/pub_summ.jsp?ods_key=nsf11031 for
further information about teaching, research, and other work
activities during tenure years.

We apologize for confusion these changes may have caused, but look
forward to working with you to ensure the GRFP is as effective as
possible in helping to ensure the vitality of the U. S. scientific and
engineering workforce.

Sincerely,

The Graduate Research Fellowship Program Office
Division of Graduate Education
Directorate for Education & Human Resources
National Science Foundation

Now of course I wouldn't want to claim that this about-face was all due to my blog post. I'll just let you draw your own conclusions.

More seriously, I'm glad they're pausing and getting some more input on the issue. As I like to repeat often, the NSF is a wonderful institution, and it's nice to see them showing willingness to revisit this issue, given my opinion that their new policy was questionable in terms of its benefit to students. I imagine many institutions encompassing large bureaucracies would never manage to reconsider a decision like this, so it is to their credit.

Serving Non-Majors in CS Classes

2011-05-18T22:50:00.000-04:00

At the end of the year, I gave a short in-house presentation highlighting some aspects of the state of CS at Harvard. In gathering data, one thing that struck me -- and I highlighted in our presentation -- is that most of the students taking our classes are not majoring (or, in Harvard-speak, concentrating) in computer science.

This shouldn't have been a big surprise -- if you look at the number of concentrators and then do the math this pretty much had to have been the case -- but it was a surprise to me how large and widespread the effect was. Sure, our intro programming classes are filled with non-majors. That's not hard to figure out, given we had about 500 people taking our first semester intro programming class this year. We have LOTS more economics majors than CS majors in that class. But even in my Algorithms and Data Structures, which I think of as core CS, only about 1/2 the class was CS majors. (Lots of math, applied math, physics, as well as several from other majors.) In some of our classes that are designed more to be outreach classes, like our courses on visualization and user interfaces, only about 1/3 of the class is CS majors, and others are from all over the campus.

This is, I think a great thing. I'd like Harvard applied math, math, physics, engineering, government, statistics, sociology, economics, and English majors to leave Harvard with some strong foundations in CS. The question is, how should we in CS at Harvard think about it? One idea is that there's certainly room for us to attract more majors into CS at Harvard, and we're certainly working on that. But another idea is that we should be looking for opportunities to teach classes that are both good for our majors and can appeal broadly to others as well. Harvard offers something like minors (call "secondaries") which requires only a small number of classes; another measure of success for us would be if we can significantly increase the number of CS secondaries.

Along these lines, David Parkes will be offering his version of an undergraduate Econ-CS course for the first time next year. I expect it will be a very popular offering, for CS majors and others.

Daily Updates

2011-05-16T22:38:00.000-04:00

Getting slowly back into blogging, some happenings from the day.

I've gotten a couple of nice notes from students saying they learned a lot from my class this semester. To any students reading the blog, I encourage you to send such notes. It will make your prof feel maybe it's all worthwhile.

A colleague pointed me to a nice example of a real-world application of Bloom filters.

I hosted a large dinner at my house a while back as part of recruiting our new faculty. Now I'm being told that as Harvard is tax-exempt I was supposed to give the caterer a form with Harvard's tax-exempt status and I need to get them to refund the tax (or I won't get the tax reimbursed). It's not a big deal, but I just love university financial offices and their fun rules. (How I'm supposed to know this, I don't know. When we take a candidate to dinner, we don't get to claim tax-exempt status, but apparently for a meal catered in your home... sigh.) I'm sure it will get worked out.

Back to Blogging

2011-05-13T23:55:00.000-04:00

I've given my final, and have grades ready to submit. The semester is over!

Over the summer I may do some blogging again, as I may have time for it. I was noticing that on my calendar, I now have empty days ahead, something I haven't seen for a while. I'm looking forward to those.

To start off, I've just finishing registering for FCRC, and it seemed apropos to complain about how expensive it was. I'll be there about 4 days, for 2 overlapping conferences (that last 5 days), and it costs nearly $1000 in registration fees.

But then I looked at other conference prices. Int'l Symposium on Information Theory 2011 is $725. That does include several lunches, a banquet, etc., and it is a 5-day conference. SIGCOMM 2011 is $625, again with banquet, 3-day conference. Not sure about lunches.

FCRC still looks expensive, but perhaps not ridiculously so.

Harvard CS -- Growth in Women Majors

2011-04-20T07:14:00.000-04:00

Some good news for us. With the growth in our introductory course, more women are declaring Computer Science as their concentration. And we seem to be growing.

Crimson article here.

Harry Lewis Asking Tough Questions (Again)

2011-04-06T09:51:00.000-04:00

Harry Lewis is asking Harvard to confront the issue of some of Harvard's professors being involved in money-making opportunities, like working for Libyan dictators, that are embarassing to the university.

Boston Globe article here.

Harry's blog post here.

I heard Harry talk about the issue on my way into work on NPR's Morning Edition -- I don't have a link at the moment.

Did the NSF Just Do Something Really Stupid Misguided?

2011-04-05T00:25:00.007-04:00

To begin, as I always do when I write about the NSF, let me start by saying that I love the NSF, and I greatly appreciate all the research funding they give me. (And all the rest of all those scientists out there too. But mostly me.)

However I think they just did something really ~~stupid~~ misguided.

NSF Publication 11-031, the replacement guide for the NSF graduate research fellowship program, came out a few weeks ago. Down a ways under "Fellowship Responsibilities" (page 5) is the following text:

Fellows on Tenure are considered to be 1.0 FTE (full-time equivalent). Consequently, when on tenure, GRFP Institutions may not request that Fellows provide service, irrespective of whether payment is received (see Stipend Supplementation for additional details). The intent of this policy is to assure that Fellows are able to apply 100% of time and effort to their graduate studies and research. Fellows should use their Reserve or Forfeit Statuses for activities that require service (e.g., teaching or research assistantships or internships)....

So now you can't teach or do internships while on a fellowship. Maybe I could understand this... you shoudn't get "double-paid", of course. Though you used to be able to teach while on a fellowship and get a bit extra pay as a graduate student, and in my mind that's a good thing. Graduate students should learn to teach (or at least practice teaching, and hopefully they'll get better). Indeed many programs make it an explicit requirement! And learning how to juggle teaching and research is actually a skill graduate students should learn, at least if they're entertaining some notion of being a faculty member someday. (And even if not, both teaching and juggling teaching and research remain useful skills for a PhD.) I can understand NSF doesn't want universities abusing their fellowship winners by making them teach constantly (is this an actual problem, anywhere?), but there are other better solutions to the problem (like requiring someone at the NSF to approve the teaching, which some other fellowships do).

So this is ~~stupid~~ misguided. But probably really not so bad -- the student can always just defer the fellowship while teaching or doing an internship, right? (Of course, teaching alone might not cover tuition + stipend ... it doesn't at Harvard ... but let's ignore that...)

No, that's where they get REALLY ~~STUPID~~ MISGUIDED!

Look under Tenure Status (page 8):

Fellowship Tenure Status is granted in 12-month increments corresponding to a Fellowship Year (Summer or Fall Start) and may not be broken into smaller units spread across more than one year, except in cases of NSF-approved Medical or Military Deferral (see below). During Tenure Status, a Fellow will generally be required to Forfeit (lose) the Stipend Payments for the months the Fellow is engaged in activities that require service (time), such as internships, teaching and research assistantships, irrespective of whether the service provides payment.

So now, if you do get an internship and decide to take it -- oops, you'll have to forfeit your fellowship for that time. Same for teaching. (Not sure if they'll hold to that if teaching is a degree requirement, we'll have to see.) So they're actually creating a major disincentive to do things that I would like to tell my graduate students are useful -- like teaching, or doing an internship in a lab somewhere. Very nice.

I'm going to find out who to send a letter to at the NSF to explain my opinion. I hope many of you will send a letter on as well. (If I get an address, I'll post it.)

Or perhaps I'm just misinterpreting, and someone will explain it to me.

And hopefully, by the time I next submit a proposal, the very nice people at the NSF will have forgotten about this posting. (If anyone asks, Lance wrote this. Or Richard.)

On a happier note, just wanted to point out that Claire's April Fools post was the funniest (theoryCS) post I've seen in a while. (It's funny because it's true.)

More on Academic Communications

2011-04-02T15:01:00.000-04:00

UW Madison has responded to the Open Records Request regarding Professor Cronon (which I mentioned here). Here's a link to the Chancellor's message as well as the response from the UW-Madison legal counsel. Given the challenging situation the university finds themselves in, my impression (after a quick read of the documents) is that this is a reasoned response, attempting to uphold the principles of academic freedom while following the requirements of the law.

The issue of privacy of academic communications reminds me of the issues I've heard regarding evaluation letters (for promotions, including tenure cases) and confidentiality. For instance, I've had colleagues tell me they won't write promotion case letters for the UC's, because confidentiality is insufficiently protected there. Apparently candidates can request to see the contents of evaluation letters. I have written a letter to a UC for such a case, and their "Confidentiality Statement" was, I must say, uninspiring. In particular, I was told to put information regarding my relationship to the candidate "below the signature block"; apparently, when the candidate requests the contents of the letters, the letterhead, signature block, and information below the signature block is not revealed to protect the identity of the writer. That's clearly insufficient, I think, for any reasonable evaluation letter; it's hard to hide your relationship to someone in a well-written evaluation letters with that framework. I'm also not clear that it would protect confidentiality in various legal settings (but perhaps nothing would?). As I had only very nice things to say for the case in question I did not have any concerns, but if that wasn't the case, I might have had to think twice about writing, and I can understand why some would refuse to write letters to the UC on principle. (Perhaps someone from the UCs -- anonymously or otherwise -- would wish to comment on these policies.)

Now that I'm on the other side -- requesting letters as Area Dean -- I've seen that some people are very reluctant to write down honest appraisals of candidates, out of concern that information would be leaked somehow. It's a concern -- we do need open and forthcoming letters to help evaluate faculty accurately -- but it's clear that the issue of how that information is protected is one that will continue to challenge the academic community going forward.

Time (for those at state universities?) to switch e-mail accounts

2011-03-31T00:42:00.000-04:00

While I've successfully resisted urges to return to blogging, I wanted to point to something.

For those who might have missed this, I encourage you to go read William Cronon's newish blog Scholar as Citizen right away. William Cronon is a Professor at the University of Wisconsin - Madison who has had the Wisconsin Republican party issue a Freedom of Information Act request for his e-mail (specifically, those using a fairly wide array of common terms and some names), apparently in response to an editorial he wrote that they did not like. He set up the blog to discuss what he is going through.

He makes the case that this is an attack on academic freedom. I'm very inclined to agree (but of course you judge for yourself). And following "First they came..." principles I want people to know about it, so you can if you want find ways of expressing your opinions on the subject, to the people of Wisconsin or to the administration at your own university.

Or, I'd recommend getting a private e-mail account and using that for most of your e-mail.

On a (somewhat) lighter note, you might want to check Crooked Timber's post on "With Notably Rare Exceptions", which as they describe is an amusing phrase that comes from a rather unfortunate recent choice of words by Alan Greenspan. While several of the comments may make you laugh, for readers of this blog, the phrase to remember is (comment 40):

With notably rare exceptions, noise is Gaussian distributed.

Leslie Valiant Wins Turing Award

2011-03-09T07:00:00.002-05:00

About time!

Spring Semester Update

2011-02-21T22:41:00.000-05:00

I see it's been two months since my last post. I must admit, there are times I miss blogging. I've often felt I have something interesting to post about, but then I let the feeling pass, and I find I feel no worse the wear for letting it go. The world spins on, and I use the time for other things.** I still try to comment on other blogs when I feel I have something worthwhile to say. If you haven't seen it, Claire Mathieu has a blog now. But it seems like other blogs have slowed down significantly. Maybe the time for blogging is over. (Apropos, this pointer from Luca's blog.)

Spring semester is always my busier semester, and while being Area Dean has only made it worse, it would have been bad anyway. My undergraduate Algorithms and Data Structures class is in the spring -- around 55 students, with another 20 or so in the Extension school version. That class is always more work than my fall graduate class. Spring semester means graduate student admissions, and planning for the graduate student visit day. And there are interviews, as we're hiring this year, leading to multiple talks (and meetings with candidates) per week. Not coincidentally, it's also time to write letters for students, for internships/postdocs/jobs. As Area Dean, I'm also involved in various promotion paperwork, class planning issues, and budget exercises. Hiring and promotions remain my #1 priorities in the job, but other issues do seem to take time as well. I'm also happily managing a fairly full consulting schedule. Yep, busy semester.

It seems that spring must also be the time for submissions, because it seems I'm asked to review things a few times a week. I'm saying no much much more frequently, so please don't be offended if you get a no with no other response from me. At the same time, I still say yes enough that I think I'm definitely doing my fair share of reviewing...

Research continues -- mostly thanks to eager students and forgiving co-authors. Various things in the pipeline (some of which have already gone up on the arxiv). I went (for the first time) to the UCSD ITA (Information Theory and Applications) workshop. The highlight was a Scrabble game with expert Amit Chakrabarti (while I lost, I think he beat me by less than he originally expected; the benefit of low starting expectations...). And there were some good talks. Some are described over at An Ergodic Walk. Nicely, we made his list -- our paper On the Zero-Error Capacity Threshold for Deletion Channels is described as: "A nice piece of work on connecting zero-error capacity for deletion channels with longest common subsequences." This was a problem I had lying around as an open question, which some of the Harvard theory students adopted in their open question problem session; a couple months later, we have a (short) paper! (Though I think the paper probably introduces more questions than it answers...) I also think while there I got myself on the ISIT 2012 program committee; strangely, I've never even been asked to be on the ISIT PC, so when asked I found myself saying I'd be happy to do it. (Maybe the asker will have forgotten by the time they get home...)

And that, for now, is probably about all to report.

** One free time activity is introducing my kids to classic board games. I was shocked to find things like Clue, Risk, and Stratego are no longer standard games, but have been revamped, revised, or utterly removed from the shelves. Luckily, there's a nice Clue The Classic Edition available at Amazon, as well as a Risk Vintage Wood Book Edition. I got both and like them, though Risk is still a couple of years away, I think -- Clue is a bigger hit. I'm going to try the Stratego Vintage Wood Book Edition next.

End of Year Update from the Trenches (Area Dean News)

2010-12-18T11:00:00.001-05:00

I last posted on Lance's blog about two months ago, so it seems a good time for an update.

My class is (hooray!) finished. I've sent out grades to the students, and just have to record them in the system. (Last chance for students to complain.) This is my survey/seminar/project class, and (as is often the case) there were a number of projects this year that I think have potential to turn into papers. Some of the students will do it on their own, and some I'll try to help along. I admit I'm a bit hesitant to see the class reviews -- I feel I didn't put in as much time into the class as usual, because administration now sucks up more of my time. We'll see if the students felt the same. (Historically, "Area Deans" have not had teaching relief, but the position has changed some with it seems more responsibility now assigned to the role -- so I think of myself as a test case for whether someone can/should teach while doing the job.)

Much of my Area Dean time has gone toward hiring and reviews/promotions. On the down side, we've had to cope with one of our faculty members leaving (see Matt's blog -- my post and his -- if you're interested and weren't aware). On the plus side, this made our requests for targeted future hiring much more acceptable across the School of Engineering. (I'm not saying our future hiring plans weren't already largely supported, but our needs were really highlighted.) Obviously, besides the fact that we're currently running a search, there's not much I can publicly report on hiring right now -- but hopefully we'll have some interesting news going forward.

Other administrative duties have included doing my small bit to make sure our CS 50 Fair went smoothly. CS 50 is our intro course, taught by the ever-energetic David Malan, and had over 500 students this year. Students do final projects, and at the fair students set up their laptops, and amid popcorn, cupcakes, music, and balloons show their projects off to each other, to fellow students, and to anyone else who wants to come by (including companies who set up recruiting tables). With 500+ students, this year required three shifts over the day. Some writeups on the fair are here and here (with videos!), and many projects are available via links at the class web site. The fair, now it's in third year, has become quite the winter event. While all the credit for the great success of this event is David's, I viewed it as my job this year to help, by doing what I could to get administrative barriers out of David's way. (So I helped get the budget increased, for example. I'm the administrator as offensive lineman.)

Research-wise, I think I've successfully increased the pace from a few months ago. Various old items have now made it or are making it through the final stages of the pipeline. Some re-submissions have taken place. New projects are now going on. I'm definitely relying on co-authors and students to push me along -- the research has been a bit more "responsive" than "reflective" -- but I'm happy to be keeping up on research stuff too. I've also continued doing some side consulting -- some of it is research-oriented, and some of it isn't (some expert witness stuff).

Some fun, "educational" writing has recently come out. I have a chapter in Algorithms Unplugged, which is the English translation of the book Taschenbuch der Algorithmen. This is a version of my "dream book" of a computer science book geared for high school students, that I blogged about long ago (old post on it here with other links to other older posts). The editors asked me for a chapter for the English translation, and I took one I had written for the dream book, and they included it (with minor edits). I'm getting my copy soon -- the book, I hear, is about to be released -- and then I'll spring it on my kids to see how good it is. I also have a little writeup on Human-Guided Search in XRDS -- the ACM Magazine for Students, talking about some of our long-ago work on the subject.

So roughly 6 months down on my administrative stint. Again, not that I'm counting. The job is actually just fine -- thanks to both really supportive faculty, and a supportive Dean of the School of Engineering. I always have the feeling that everyone is trying to make this job easier for me, and they're doing a very good job of it.

Guest Post over at Computational Complexity Blog

2010-10-20T07:40:00.000-04:00

For those still receiving this feed, I have a guest post briefly describing some aspects of life as Area Dean over at the Computational Complexity blog.

Blog Retrospective

2010-08-31T07:48:00.000-04:00

I started blogging a little over 3 years ago, as something of an experiment. Lance had given up blogging, and I had been a reasonably frequent and opinionated commenter on his blog, enough so that people often asked when I would start my own. I hadn't planned on it, but Lance's stepping down (which, later, turned out to be temporary) felt like it had left a hole. I hoped that I might provide, in my own way, a community forum for discussing issues, and a connection point for the areas I'm interested in -- algorithms (or theory more broadly), networking, and information theory.

In the end I'm not sure how well I achieved the various goals. I don't feel this blog has ever become a strong authority (or hub, in Kleinberg's language) in the way that I might have liked. Commenting has been sparse with infrequent spikes; longer more detailed discussions seem rare. Perhaps this is just hard to do -- people have, on the whole, better things to do with their time. Or perhaps (probably?) it represents flaws in my posts. Certainly one wish I think I had going in is that my posts would be more technical, but technical posts take a great deal of time, and are, quite frankly, hard. I'm ever-impressed by what Dick Lipton is doing, in terms of technical depth, at his blog; it's a wonder to me.

On the other hand, I'm amazed and pleased to find that people read this blog, and have enjoyed the "behind-the-scenes" look at life and work as a professor. Everywhere I've gone in the last few years, there are people who tell me they've been reading it. I've never implemented tools to tell the size of my readership, but anecdotally it must be larger than I think. (The joy of low expectations.) It's opened the doors to lots of interesting discussions about research, the state of computer science, what being a professor is like, and a whole range of various things. And from what I can tell, it has given the different communities I was targeting a better idea of what each of them is like, in terms of culture and process. That perhaps hasn't always been a good thing, but overall I'll view it as a success.

I didn't realize when I began how much blogging would raise my "visibility", but that seems to have been a pleasant side effect. I'll admit, I'm glad to have been able to take advantage of that. Perhaps I'll be invited to give fewer talks now that I'm giving up the blog. Or fewer PCs. Maybe at this point that's not all bad. Or maybe stopping will force me to explore other positive ways of raising my visibility, perhaps by writing another book.

Overall, I've had a great deal of fun blogging, and that alone has made it worthwhile. Over the last several months, however, I've found blogging less enjoyable. Some of that must just be fatigue; I suppose I've been running out of things to write, making writing harder. But also there have been fewer comments, and -- as discussed in this post over at the Complexity blog -- there has been much more of an unpleasant tone in (anonymous) comments (across many blogs) of late. It's a sign for me that, as fun as this all has been, it's time for me to stop. My new position has provided a good excuse, but I probably would have stopped anyway.

Perhaps blogging has just been the latest Internet fad -- perhaps our social networks can't support the number and diversity of blogs that we have, and our attention is now moving elsewhere. (Like, back to work.) I'd like to think not. I think the latest P=NP? phenomenon is an excellent demonstration of the potential power and importance of blogs. (Again, Dick Lipton's blog was a wonder.) I hope that all the bloggers we have in our community keep going, that new bloggers come into the picture, and that we use blogging -- or whatever new tools come along -- to enhance communication within and across our communities. As an example, I've spent some time the past few days looking around at the CS Theory StackExchange Q and A site, prompted by Suresh's posts. I'm not quite sure what to make of it yet, but it's been fun to explore and seems to have interesting potential.

Thanks to all of you who have been reading, and especially to those of you who have been taking the time to provide thoughtful comments. I wouldn't have continued for as long as I did without you. I've enjoyed this experiment, and I'm gratified to think that some of you have enjoyed it to. I'm sure I'll still be around, offering my opinion at other places. And I hope when you see me around (physically), even though I'm not blogging, you'll consider trying to strike up a conversation with me; I'm sure we can find things to talk about, and, without the blog, I'll be missing this type of conversation.

Doing the Right Thing? (Quick Links Edition)

2010-08-28T23:59:00.000-04:00

From Shots in the Dark, a pointer to a new "feature" -- apparently, there's not a tweet system recording and listing books checked out from Harvard libraries. No, they're not putting names with it, just times. But who thought this was a bright idea? Seems like a clear potential privacy-violating nightmare with no upside that I can see. I'll have to find out who to call on Monday to complain and spread the word to other profs...

From the Crimson, Marc Hauser will be teaching his classes in the Harvard Extension School this year. Now, in some sense, this isn't a big deal; Marc's on leave from FAS, and the Extension School is separate from FAS. And trust me, he won't be getting any huge paycheck from the teaching; while the Extension school pays its teachers (naturally), I'm sure it's a small fraction of Marc's Harvard salary (which he may or may not be getting; I haven't heard confirmation one way or another whether he's on paid or unpaid leave). Given that he's been heralded as a great teacher for a number of years, arguably, why shouldn't he teach? But I admit, as someone who works with the Extension School, it's leaving me with an uncomfortable feeling that I'm still trying to process.

Anyone have gossip to tell about why the Crypto 2010 proceedings were put online, but then taken down (apparently once the link got publicized)?

Scott Aaronson answers some questions for MIT news about the P/NP proof. I won't opine on whether his bet was a right thing or not (his own blog has had plenty of discussion on that) -- what's wrong with the article is that it has multiple links to Deolalikar's paper that are now non-functioning. I understand that web-news links aren't going to be kept up to date in perpetuity, but you'd think for this fairly recent article and controversial topic someone might have updated accordingly. One thing I wonder -- given the unusual amount of press that this proof attempt was given, and the current consensus that it's incorrect and recovery isn't possible, how many people are left with the misinformation that this very important problem was solved?

Conference/Journal Versions -- Transactions on Networking

2010-08-25T09:20:00.000-04:00

I was recently asked to review a paper for Transactions on Networking, and noticed the following bit in the e-mail?

Please note that while this paper may have had a previous conference version, ToN does not mandate any specific differences between conference papers and their versions subsequently submitted to the journal.

Is this new??? Am I reading this right, that there's no mandated "30% new material", or some similar rule It's been a while since I've submitted to ToN, but I seem to recall being explicitly asked by reviewers or editors from ToN before what "new material" there was in the paper over the conference version. I'd be interested to know if this was an actual policy change -- it's one I've called for before, but didn't expect to see implemented anywhere.

Just curious if anyone can share any insight....

Various Quick Pointers, Redux

2010-08-23T22:52:00.000-04:00

There were many interesting things at the CRA Snowbird conference for CS chairs (which I missed...), but I haven't heard any blog-level discussion of their call to move up the schedule for hiring (as well as related changes in procedure). Anyhow, lots of slides from various presentations.

UC Campuses are tops in Washington Monthly rankings, which are different in substantial ways from the US News and World Report rankings...

Still time to sign up for Harvard Extension School courses for this semester; here's the list for computer science. Including, for example, E-210.

Dick Lipton's future book, taken from his blog, appears on Amazon (you can pre-order now!).

Nature's take on Hauser's MonkeyBusiness opens with: "When news broke last week that famed Harvard University evolutionary psychologist Marc Hauser had been investigated for scientific misconduct, it was no surprise to many in the field. Rumours had been flying for three years, ever since university officials arrived to snatch computers from Hauser's laboratory at the start of the inquiry. By the time Harvard completed its investigation in January, the gossip had become standard cocktail-hour fare at conferences."
Maybe they're right -- I'm not in his field -- but I'd never heard any sort of rumor at Harvard. I'm clearly not getting invited to the right cocktail hours.

How's that New Job Treating You? Edition

2010-08-22T15:23:00.000-04:00

I told myself I'd quit blogging when summer ended. That's a bit over a week away, as classes start September 1. Also nicely, from the count on the right, I'm nearing 500 blog posts. Seems like a good stopping time.

I'm now not infrequently asked how the new "Area Dean" job is working out. Just fine, thanks. I figured I'd say a little more about it, and perhaps that will also explain why it's a good time to give blogging a rest; I can't imagine people would want regular blog posts on this sort of stuff.

So far, the time commitment is about what I expected, but only because I was told to expect that it would take more time than I would expect. There's a lot of meetings, e-mail, and writing. Pleasantly, the time thus far has been spent on fairly worthwhile endeavors -- most of the time has been spent on hiring and promotion plans. Since, really, managing those issues are the highest priorities of this job, that feels like time well spent. Some time has been spent on letter-writing -- those CAREER, Sloan, and other fellowship letters get written by someone, and now that someone is often me. Finally, some time has been spent as being "voice of the faculty" on certain issues. For example, there are some non-trivial changes supposed to take place on our e-mail system, and unsurprisingly the CS faculty are more concerned than the average faculty member about this. (A little knowledge is a dangerous thing...) My job, where possible, is to be the consensus voice and contact point on faculty-administration issues like this.

Because I'm new -- and because it's summer and we're not having our regular faculty meetings -- there's been a lot of e-mail. We're a consensus-oriented faculty in CS, so I want to represent the consensus. I feel at this point it's important for me to check carefully with other faculty members before expressing a collective opinion (or even my own, since often it will be taken as the collective opinion). Being new at the job, this means -- in my mind -- checking in with the faculty perhaps more than is truly necessary, both so I am secure that I am representing them accurately, and perhaps even more importantly, so that THEY'RE secure that I am representing them accurately. I suspect after a few months, assuming that I've grown into the role and the faculty has developed a trust in how I perform the job, there will be less need for as many explicit checks on things. (I suspect some faculty will just get tired of getting e-mail from me!) On the other hand, maybe they'll appreciate this conservative style, even if it means they get e-mail pings on administrative issues more frequently. We'll see.

I expect further aspects of the job will reveal myself as the semester begins -- more committee meetings, more curricular issues to handle, more faculty concerns. There are also some long-term initiatives that I expect CS to be at the center of that are just starting up but will require my attention. (They're not ready to talk about yet.) And, perhaps, I'll find myself involved in other activities like fund-raising. (I may have to convince my Dean that, although my standard work wardrobe is a simple button-down shirt and jeans -- or a T-shirt and jeans over the summer -- I do own a few suits and ties and can be made to don them for appropriate occasions.)

It is time-consuming, and it will, sadly, clearly eat into my research time. I'm thinking about how best to handle that. And when you're ~~shafted with~~ given a job like this, it really makes you appreciate your predecessors. (I knew Greg Morrisett was doing a great job before, but now I really appreciate it.)

So far, though, it's all fine. I hope to do some good in the position; and I hope I end up being good at the position.

RATS roundup

2010-08-20T23:35:00.000-04:00

I didn't see every talk (my brother lives in the area, so I took a break to see family) but I did have a fun day at RATS. There was a brief introduction by Chris Anderson of Wired/The Long Tail fame (on video -- I was disappointed he couldn't make it in person, I wanted to meet him), which was very interesting. I was pleased that as he was talking he kept mentioning power law and lognormal distributions; I knew he mentioned my survey on his blog at one point, but I (and others, as expressed to me later) were still surprised he mentioned them together when discussing long tail issues. That nicely set up my nice "survey talk" on lognormal/power law distributions. This was followed by the excellent talk by Aaron Clauset on power-law distributions in empirical data, discussing the challenging issues of how do you determine, based on your data measurements, whether you're looking at something that seems to be following a power law or some other distribution. (I'm asked this question a lot; happily, I can just point people to Aaron's paper.) Sharad Goel gave a fascinating talk on the implications of the long tail in marketing/web sales, arguing that the "value" for sites like Amazon in offering the "long tail" of items is NOT necessarily in the additional sales, but in the power of locking in customers. (Since Amazon has "essentially everything", at a reasonable if not optimal price, why bother wasting time going anywhere else?) Neel Sundaresan of eBay discussed insights form eBay data about the differing "shape" of different market segments, and the implications for assisting customers to find items in the large landscape that is eBay. Silvio Lattanzi talked about implications of power laws in compressing social networks, and on models for affiliation networks.

The slides, apparently, should all be up at some point on the RATS webpage, or I'll update with an appropriate link.

MonkeyBusiness : Some Resolution

2010-08-20T16:02:00.000-04:00

Wow. After days of various speculation and reports from multiple new sources, Dean (Mike) Smith of the Harvard Faculty of Arts and Sciences has made an announcement regarding the investigation of Marc Hauser. The opening paragraph is the key:

"No dean wants to see a member of the faculty found responsible for scientific misconduct, for such misconduct strikes at the core of our academic values. Thus, it is with great sadness that I confirm that Professor Marc Hauser was found solely responsible, after a thorough investigation by a faculty investigating committee, for eight instances of scientific misconduct under FAS standards. The investigation was governed by our long-standing policies on professional conduct and shaped by the regulations of federal funding agencies. After careful review of the investigating committee’s confidential report and opportunities for Professor Hauser to respond, I accepted the committee’s findings and immediately moved to fulfill our obligations to the funding agencies and scientific community and to impose appropriate sanctions."

Rather than reproduce the whole letter here, I can point you to Harvard Magazine, or Science. Mike also discusses the Harvard process and the reason for confidentiality in such cases. I'm glad to see this come out, and I can imagine the difficulties Mike had in deciding to produce such a letter. (As I have stated previously in this blog, I have great respect for Mike Smith, who was in the office next to me before getting proverbially kicked upstairs, and I'm very happy that someone of his talents is serving as Dean of FAS). On the other hand, it's a sad day for Harvard, and arguably science more generally.

Various Quick Pointers

2010-08-19T11:10:00.000-04:00

While it may not be news elsewhere, I'm certainly interested in the "local" case of Marc Hauser, the evolutionary psychologist at Harvard whose work has been "under review". The latest interesting update appears at the Chronicle of Higher Education.

As reported elsewhere, congrats to Dan Spielman for winning the Nevanlinna Prize.

I'll be at the ill-named RATS (Research and Analysis of Tail Phenomena Symposium) tomorrow reviving my introductory talks on power laws, lognormal distributions, and the importance of verification. Stop by and say hi!

While I was away in the UK the Microsoft PR machine must have gone to work, and I've seen a few articles like this describing our work on password popularity. I'm happy to see my name "in lights" a bit -- why not? -- I just think it's interesting that this is the paper that gets it there. (I guess our coding work is also being touted a bit as part of Dan's Nevanlinna Prize, so that's "in the news" as well.)

The Museum of Mathematics is getting more notice -- check out their web page.

In Need of a Few Bad Papers

2010-08-13T11:48:00.000-04:00

For my graduate class this semester, there's a lot of paper-reading, and I view learning how to critically and constructively read papers as part of the student goals for the class.

A corollary of this, it seems to me, is that the class should include some bad papers, so students learn to recognize (and, if possible, get something out of) reading those. So I need some really good examples of bad papers. (In one of the areas of the class focus -- web search, compression. coding, streaming data structures...)

Now I should be clear about what I mean by bad papers. I'm looking for something of a higher standard than an automatic journal reject -- I get at least one of those a month in my mailbox, and it's not clear there's much to learn from that. I'm talking about papers that at least superficially look quite reasonable -- indeed, I'm expecting papers that have been published in reasonable places -- but when you think about them more, there are subtle (or not-so-subtle) flaws. In theoretical papers, possibly it might be that the paper starts with a model that sounds really nice but it just clearly wrong for the problem being addressed. For systems papers, it might be a paper where the experiments just don't match up to what ostensibly was being proposed.

[I had a nice example of a bad paper in earlier incarnations of the class, but I don't think it's aged well, and I've removed it.]

Maybe bad is even the wrong term for what I'm looking for. Perhaps I should use a more neutral word, like "controversial" -- indeed, then I can get the students to take sides. (Is the Faloutsos, Faloutsos, Faloutsos paper still considered controversial these days? That could be a nice example, but it's not really on topic for the class.) Or perhaps I just want papers that reached too high for their time -- noble failures. The key is that, in my mind, just showing students examples of great papers doesn't seem didactically sound. Negative examples are important for learning too (especially if they also show that great scientists don't always get it right).

Feel free to mail me rather than post a comment if you're afraid of offending anyone. Naturally, mailing me links to my own papers will be taken with the appropriate humor.

STOC tutorial online

2010-08-13T11:29:00.002-04:00

Paul Oka asked me to announce that the STOC 2010 tutorials are now all online. You can find them here.

Monkey Business

2010-08-12T07:25:00.000-04:00

I see Harvard's in the news yet again, as the Boston Globe broke a story about psychologist Marc Hauser, who is "taking a year-long leave after a lengthy internal investigation found evidence of scientific misconduct in his laboratory." One paper has been retracted, others are under examination. As discussed over in Shots in the Dark, an unpleasant issue is that Harvard is being silent regarding its investigation. It's not clear to me what the right approach in such cases are -- what rights to privacy, if any, does an academic have in such situations, or, assuming improper behavior is found, is it incumbent on the institution to correct the scientific record itself? The issue is also raised in a New York Times article. Feel free to discuss the institutional ethics in the comments.

I have no inside insight on what has actually transpired; however, I have served on university committees with Marc in the past, and found him an enjoyable colleague. I hope to the extent possible the issues are resolved satisfactorily.

This controversy provides an interesting contrast with the current hubbub over the P not equal NP paper -- best considered over at Richard Lipton's blog here, here, here, and here. In theory we don't have to worry about people "forging" a proof in the way that experimental data might be forged, but proofs can easily have mistakes or unclear gaps, and this is not viewed as misconduct -- just embarrassing. I wonder what the state is in computer systems work -- I can't recall hearing of cases where there were accusations of misconduct with data, although I've certainly heard mutterings that experiments in papers were carefully chosen to (excessively) highlight positive results. Such cases can lead to heated discussions in PC meetings, and to some interesting discussions post-publication, but I haven't heard people suggest that that level of data manipulation corresponds to misconduct. Our field seems to have, for now, sidestepped these particular issues.

Other UK Adventures

2010-08-11T14:01:00.000-04:00

While in the UK, I went out to some other places to give talks -- Liverpool and Cambridge.

At both places I gave my talk on our analysis of the auction site Swoopo, which seemed well received. Of course it's a topic that can appeal to a wide, general audience and is just fun to think about, but the major credit has to go to our student Giorgos Zervas. Not only did I swipe his excellent slides, I even shamelessly adopted some jokes from his presentation, and of course they got the biggest laughs. Maybe I need to get him to prep all my talks. (I also talked about some recent work on networking+hashing at UCL and Cambridge as well. Slides are up at my talks page.)

At Liverpool I was hosted by Leslie Goldberg, and it was great fun to ask her questions about the UK system. One issue that came up is a UK policy to use "short-term economic impact" as one of the bases for research funding decisions. Leslie has rallied against the idea -- she has an interesting web page devoted to the issue with a host of opinions on why it's a bad idea. We also discussed the RAE, the Research Assessment Exercise, where schools are scored and ranked based on their research output, and this affects their future government funding for research. (Here's an article from the Guardian in 2008 when the last results came out.) It's interesting that the NSF does not do something like this, but the link between university funding (apparently, even for research) and the government is perhaps more direct in the UK. It's worth pointing out that Cambridge is at the top overall, and my host institution University College London was 5th in the latest rankings; specifically for computer science, if my info is right, Cambridge is still 1st, UCL is still fifth, and Liverpool is 11th.

At Cambridge I was hosted by Jon Crowcroft at the computer lab and Peter Key of Microsoft. The two building are right next to each other, far from the Cambridge center (about 2 miles). They're just past Churchill college, where I spent almost a year after college, so I got to experience the waves of nostalgia as I walked by. (I would have experienced it even more had I had a bike.) More than nostalgia, I felt a twinge of jealousy -- when I was at Churchill XX years ago, it was far removed from everything. Now it's pretty much at the center of the mathematical sciences complex and the computer science buildings, which have moved out to the outskirts (for space reasons, and so nice new modern buildings could be made for them). Why couldn't they have had that when I was around? Re-visiting Cambridge was also a blast -- it's just a lovely city. Hey, come to think of it, why doesn't someone plan a major conference there (not hard to get to from London airports; I'm pretty sure the main conference could be held at University/Microsoft lecture rooms; hotels, though, are probably quite expensive).