Journal Version : Two Choices + Bloom Filters

A paper that's been sitting around in the pipeline far too long is finally out in its journal version.

Using the Power of Two Choices to Improve Bloom Filters, by Lumetta/Mitzenmacher.

This paper pretty much came about from a dare. I was visiting my friend Steve Lumetta while at Allerton, and as he was ribbing me about all my papers being on either Two Choices or Bloom filters, he suggested I should be able to combine the two in one paper. It took a few minutes for me to work out that he wasn't entirely teasing me, he actually had an idea.

The basic idea is the following: instead of having one group of k hash functions we use to insert an item into a Bloom filter, we have two groups of hash functions. We insert items sequentially into the Bloom filter, but we use our power of two choices as follows: when we insert an item, we use the group of k hash functions that sets the smaller number of bits to 1 (since fewer 1s means fewer false positives). When checking if an item in the Bloom filter, we have to see if all corresponding bits are set to 1 for either group of k hash functions, since we don't know which group we used initially for each item.

It turns out you can analyze this scheme, and somewhat surprisingly to me, there are settings where it leads to improved false positive rates. That is, the gain you get from putting in fewer ones actually more than makes up for the fact that now you have to check two groups of k hash locations. We also explore even better schemes (based on better choosing which group to use for each item) that we can't analyze.

I admit I took this as a funny mathematical curiosity more than a practical scheme. And I couldn't resist the title. (If you know my work, it really does sound like a joke.) But someone saw the paper and ran with the idea: the follow-on SIGMETRICS paper Building high accuracy bloom filters using partitioned hashing gives a potentially practical variation. (It's not clear to me when you'd use this variation over a perfect-hash-function-based Bloom filter; I suppose their variation is more amenable to adding a small number of additional items on the fly.)

My hope is perhaps it will inspire other non-obvious valuable uses of the power of two choices.

Committee Games, Playing by the Rules, and Double-Blind

There's a phenomenon I've noticed in committee meetings. To avoid any issues related to discussing PCs, I'll discuss it in relation to a thesis prize committee I've served on multiple times at Harvard. It's very much like a PC -- usually about a 1/3 of the theses nominated receive the prize.

We're given a bunch of senior theses to read, and asked the score them on a 1-5 scale, with 3 being the nominal desired average. Obviously, it's very hard to give any of these theses a 1 or even a 2 -- faculty are generally good about being selective about nominating a thesis for this prize -- but if you want to give a 3 average, you have to make tough decisions.

At the meeting, your average on your theses is compared to the average of the other reviewers on your theses, and your scores are re-scaled accordingly. So if you worked to maintain a 3 average, but the other reviewers on average gave your theses a 3.5, those theses you read would get a higher "scaled score". Similarly, if you gave your theses a 4 average, they would get a lower scaled score.

Now, even with the scaled scores, I find in these meetings that when someone has given a much higher average than their peers, their scores are discounted even further. Perhaps they couldn't manage to be tough and give a low score to some theses, and they thought they were being nice by giving high scores (which the students never see) to everyone, but in the end it often makes things worse for the theses they've read. There seems to be a higher-level phenomenon going on here, where committee members who don't play by the rules have their theses suffer some extra punishment. Unconsciously or consciously, the mindset seems to be that if you couldn't be bothered to make the tough decisions before the meeting, why should your judgment be trusted as much as others who did?

There can also be a similar effect, where those who give scores close to a 3 average but find their theses overall have a much higher average get appear to have their theses get a slight bump even beyond the scaled score. The theses they read are sometimes rewarded for their playing by the rules.

[I should point out that I have no documented evidence of this effect. I could be imagining it all. I'm just relaying my perceived experience.]

I was originally going to bring this up as a point related to the 1-5 scale I used for STOC. The scale, I think, is naturally self-reinforcing; people who clearly go outside the rules (for whatever reason) by giving higher scores are easily seen, and unless evidence from other reviewers supports that they had exceptionally good papers, their papers will have no benefit -- in fact, they may even suffer a little.

But this also seems relevant to the discussion of what would happen if double-blind reviewing was introduced. People keep pointing out that, assuming papers were posted somewhere, double-blind reviewing wouldn't help anything. But I think it still could. PC members who tried to discuss papers making use of the authors' names would not be playing by the rules; my guess is there would be sufficient reaction from other PC members to squelch such behavior. Indeed, it may even be enough to discourage at least some people from going to look at who wrote the paper. While I'd understand if a PC member happened to know who wrote some of the papers based on their own personal knowledge, I admit I'd be troubled by a PC member who, knowing the rules were for a double-blind PC, felt the need to go outside the rules and find the authors for all of their papers. Would that cause me (and others) to discount their scores, to make up for the implicit bias they were bringing into the system? It would be interesting to find out.

[Side note: I'm greatly enjoying the debates on double-blind reviewing. And honestly, I can't say I think I know what the best answers to the underlying questions are. But I think it's great that the community is having an open, challenging discussion about conference reviewing processes; that's one of the things these blogs are for.]

Double-blind reviewing

The issue of double-blind reviewing came up a number of times when I was blogging about the STOC PC. I had wanted to wait and write a well-thought out post on the subject, and happily, was beaten to it by Sorelle, who was written an excellent post outlining the various arguments and counter-arguments (with more in the comments). Sorelle has asked this conversation to continue, so I'm continuing it here.

My primary concern against double-blind reviewing is what restrictions is puts on author dissemination. I have limited experience with double-blind reviewing as an author, and my impression was that authors were not to disseminate their work in any public way when submitting to a conference with double-blind reviewing. Perhaps times have changed, or my memory/understanding was faulty, but such strict dissemination restrictions do not seem to be the default.

For SIGCOMM (which is double-blind) the important statements in the call seem to be:

"As an author, you are required to make a good faith effort to preserve the anonymity of your submission..."

but at the same time,

"The requirement for anonymity is not meant to extend beyond the submission process to the detriment of your research. In particular, you may circulate your submission among colleagues or discuss it on a mailing list if you see fit. "

I wish this second statement was clearer, but my understanding (and apparently the understanding of at least some others) is this wouldn't prevent an author from putting the paper on their web page or on arxiv or giving a talk somewhere about it.

If we have this understanding, we should move to double-blind reviewing. To try to limit myself to something new in the argument -- again, go read Sorelle's post and comments! as a baseline -- let me say that after serving as a PC chair, it's absolutely clear to me that biases based on the authors' names do regularly enter into the picture. Let me take a hypothetical situation. Three initial reviewers give bad reviews to a paper. Another PC member takes a look -- because they know the author -- and argues that they've heard a bit about the work, that the reviewers might not realize how this is tying together two areas (quantum and e-commerce auctions! -- again, that's hypothetical) in a novel way, and think an outside reviewer is in order.

At this point, bias has almost surely entered the picture -- unless you think with high probability the other PC member would have noticed this paper without the name on it. It's a limited and seemingly harmless entry of bias -- all that's being asked is someone else look at the paper! -- but what about all the other papers that aren't going to get a second (well, fourth) look because the "right person's" name isn't on the paper? In my mind, it's bias pure and simple. At this point, it seems to me, if you want to argue against double-blind reviewing you have to argue that the cost of this solution is outweighed by the actual benefit. (Hence my concern about the "costs" of limiting authors' ability to disseminate -- which for now I'm understanding is a less severe issue than I might have originally thought.)

And by the way, I think there are much more severe examples of bias that regularly come to play in PC meetings. Much of this readily admitted, by people who give the argument that we in fact should give more trust to "name" authors that unknown authors, since they have a potentially bigger loss of reputation to protect. (See comments at Sorelle's page for those that give this argument.) People presenting this argument are at least being open that in their mind they are considreing a cost-benefit analysis on the bias they admit is there. I don't think this argument holds up -- though we can leave that discussion for the comments if needed.

To wrap up, I should say that I personally don't recall a setting where I thought there was specific bias against female authors in a theory PC, which was an issue Sorelle brought up. I'm not saying it doesn't exist, but that unlike many other clear issues of bias that I have seen, I can't recall a specific one where I felt sexism was playing a role. Of course that doesn't change my opinion that double-blind reviewing, implemented suitably, would be of positive benefit for our major conferences. And if there is bias against female authors, an additional benefit is it would likely mitigate that as well.

Hash Table with Preemptive Bloom Filter

There's a useful hash table/Bloom filter trick I've been seeing across a number of papers. (If you don't know what a Bloom filter is, then I haven't been doing my job...) For the record, I'm not claiming this trick is mine; maybe it originated in the paper Longest Prefix Matching Using Bloom Filters, where it plays a key role. But I also can't recall a paper that clearly highlights the idea, so I'm doing it here.

Suppose you'll be doing lookups of (large) keys in a (slow) hash table, and many of your lookups will be for items that actually are not in the table. For example, you may be storing URLs on blacklist or dangerous packet signatures or prefixes of addresses or whatever else. Then it makes sense to keep a Bloom filter for the items in your hash table in (fast) memory. Before you do a lookup into the table, you check the Bloom filter. A false positive in the Bloom filter means you do a lookup when you didn't have to, but this allows you to avoid a lookup for a key that's not in your hash table the large majority of the time. The approach works for any type of hash table.

This should be considered a standard approach in hash table design, so I suggest we come up with a catchy name for it, so it doesn't have to be continually repeated in future papers. I'll suggest it be called a "hash table with preemptive Bloom filter", but feel free to suggest a cooler sounding name for it in the comments.

This example highlights the need for coming up with names for nice ideas that generalize to many situations. I've seen this idea described repeatedly in multiple papers precisely because nobody has thought to give it a good name.

Visiting London

Wednesday I continued my over-the-Atlantic trip at University College London, where I gave for the first time a talk on our network coding work (blog post, arxiv link) that appears as a INFOCOM 2009 paper. The slides are on my talks page. The talk was assisted by my host Brad Karp ("no relation", most famous for his work on Greedy Perimeter Stateless Routing), who asked several pointed and useful questions that will help as this work continues. Brad's part of a growing networking group at UCL that includes Mark Handley.

Where Cambridge's charm comes from its character as a large college town and its history, London's a great big city with plenty of charm and history of its own. Both parts of the trip were great fun, in both cases because of my ever-helpful hosts -- thanks Frank and Brad! I'm already scheming to find a good excuse (international research collaborations!) to go back for a longer time.

Visiting Cambridge

I spent Monday and Tuesday visiting Cambridge (the old one; the University is having its 800th year celebration this year). Despite my standard aversion to travel, I couldn't possibly refuse; I was invited to give a Kuwait lecture by one of my early mentors, Frank Kelly. I was fortunate enough to take his course on stochastic models the year I spent in Cambridge after Harvard. (It was very interesting on this trip hearing Frank's thoughts about the similarities between computer network traffic problems and road network traffic problems -- besides doing among many other things some of the important early work on economic models related to Explicit Congestion Notification for TCP, Frank served three years as Chief Scientific Adviser to the United Kingdom's Department for Transport.)

Let me gush a bit about Cambridge for a minute. Cambridge is sufficiently small that even though I've rarely been through since that year, it was very familiar as soon as I stepped off the train. Besides indulging in nostalgia, like walking through my "alma mater" Churchill College (the ugliest college of Cambridge!), I did my share of sightseeing, including viewing the new grasshopper clock and a walk along the Backs. I also got to see a bit of Frank's new life as the Master of Christ's college. This included a special look at the recently refurbished undergraduate quarters of Charles Darwin (part of the celebration of Darwin's 200th birthday), as well as a peek through the semi-hidden windows in the Master's quarters into the chapel and college dining room. And for the first time I experienced Cambridge's Centre for Mathematical Sciences, a beautiful and functional setting for mathematics, bringing people from a range of different areas to the same cluster of buildings. (It's located about 3 minutes from Churchill -- why couldn't they have had this when I was here? Back then, Churchill was out in the far outskirts of the Cambridge community; according to Frank, most of the new construction is moving out of the town center, expanding the University so that in a few decades time, Churchill might actually be in the "center" of Cambridge.) I encourage interested math/CS students (who can get one of the fellowships for Cambridge) take the Part III Tripos, which provides a solid mathematical background for any future research career.

For my talks, I tried to present surveys for a wide audience, so Monday's Kuwait lecture was on Bloom filters and applications, and Tuesday's talk covered my survey of results for deletion channels. A highlight at the talks was seeing another of my role models, David MacKay. Well known for his popular textbook on information theory, David has finally finished his new book on energy, entitled Sustainable Energy - without the hot air (and gave me a copy to read for the flight home). It's a popular science book giving a scientist's calculations on what the real numbers are for the potential future of sustainable energy. I've previously mentioned the draft on this blog; I'll present a more detailed review of the final work some time in the future, but if you're at all interested in a scientific take on the subject, you should buy it, and you can even check it out first by downloading it via the book's home page.

Other Blog Writings of Note

Just some pointers to some other stuff around the blogosphere:

If you like that kind of stuff, for the last two days (here and here) the amusing FemaleScienceProfessor had been writing about students who feel a bit more entitled than they should. My memorable story is my first week at Harvard, just before classes started, a student e-mailing to ask me if I could change the class time because it interfered with baseball practice....

I seem to have not mentioned the blog for Blown to Bits, the book co-authored by Harvard's own Harry Lewis, who is writing most of the bits for the blog. If you're interested in the computer science and society issues, it's a good place to keep track of amusing things going on. (You can also download the book under the Creative Common license.)

I'm pleased to see people pointing out the STOC 2009 papers they are interested in seeing, like Luca and Sariel and Lance.

The FOCS 2009 call is up. Can't say I get the "brief description" thing myself -- as mentioned on other blogs, in the old days, we'd call that an introduction. Maybe now PC members who only read the introductions can save themselves some bandwidth and only read the brief descriptions! (Yes, that's a joke. Well, maybe.) But don't get me wrong, I applaud experimentation in our conference processes, and hope it goes well.

Hooray for more science funding in the stimulus package. Check out what the CRA blog and the ACM blog have to say.

NSDI news

NSDI 2009 will be coming up in April in Boston. (April 22-24) Since I was on the PC, I'll plan on stopping by, but the problem with the conference actually being in Boston is it provides an insufficient excuse for skipping out on all my other duties (most notably teaching class, but also tucking the kids into bed and helping with their homework).

I was reminded about the upcoming NSDI dates because the-powers-that-be just asked me to be on the PC again, for 2010. As we all know by now, I'm a sucker for conferences that use a 5-point rating scale and kick people out of the room for any passing reason -- and I enjoyed the PC for this NSDI -- and they managed to be the first 2010 conference to ask me -- so it looks like I'll be back again...

Looking back over my mail, I asked people about a year ahead of STOC 2009 to be on the PC. They're a good few months ahead of that. Psychologically, 2010 seems just so far away, how could I say no?

New Blog : Matt Welsh

My colleague at Harvard, Matt Welsh, has started a new blog, Volatile and Decentralized. It will be focused on systems -- primarily sensor networks -- but will also have all of his other interesting insights on teaching, students, being an associate professor, Harvard, etc. Go check out the first few posts!

I've often wondered why more systems people don't blog. I think I asked someone once (Jennifer Rexford?) and was told, "We're too busy." I'm glad Matt's not too busy to share his work and insights with all of us.

Some Notes on Collaboration

[For part of tomorrow's CS 222 class, we'll be talking about
collaboration, inspired by the Gowers's Polymath project. It fits in
with one of the themes in the class, which is getting young grad
students or senior undergrads into research mode. While I swear I've
written something like this up before, now I can't find it, so I'm
writing it down now and it will be part of my class "lecture" for
CS222 tomorrow. Think of this as a draft of lecture notes, which --
inspired in part by Luca's online blog notes -- I'm putting online. And
following the theme of collaboration, feel free to add comments,
suggestions, or advice to students that you think is useful.]

In this class, you'll be doing a final research project, most of you
with one or more partners. I'd like to spend a little time talking
about collaboration, some tricks for doing it, and how important it
can be for you as a graduate student.

I think most undergraduates -- especially those who aren't scientists
-- have the wrong impression that science and especially computer
science isn't very collaborative. The common image is of a professor
hiding away in his office, or a coder alone with the terminal. In
contrast, those of you who have been in the terminal room late the
night before a programming assignment probably know how collaborative,
and social, coding can be. And the large majority of my papers, and
most papers written in computer science, have more than one author.

In fact, as a graduate student, collaborating successfully is likely
to be key to your success. Synergy is real. Research is inherently
non-linear; it's not how much time you spend working on a problem,
it's coming up with the right idea. And working with others, for many
people, simply leads to better ideas more quickly. A key insight
could require knowledge that each individual doesn't have alone; a
different perspective can move someone forward when they're stuck; an
idea one might be quick to discard as being the wrong path might prove
fruitful in another's eyes. And beyond that, collaborating is often
fun, and having fun while working on a problem can make people more
productive on its own. So there are reasons House has his staff,
Buffy has her Scooby gang, and even Holmes hangs out with Watson.

Some quick thoughts about collaborating. First, as a beginning
graduate student, you are probably very concerned about who gets the
credit. My advice is to put this aside. When you go into a project,
you don't know who will hit on the right path -- and it's very
possible that the thought you had that broke open the problem might
not have happened if you hadn't been working with those other people.
Think of the long term -- you'll be known for your body of work over
your lifetime, people will see what you can do over a number of
projects. You don't need to focus on specific credit for this
specific project. And you want to foster an environment where you can
collaborate with others easily and naturally. That becomes harder
when you're always worried about who will get the credit. For more
on this, see also Hardy and Littlewood's Four Axioms for Collaboration,
or the end of Fan Chung's notes for graduate students.

Another thought about collaborating -- although, actually, you can use
this idea even when you're working on a project yourself! I've
generally found that when working with others in research, people
implicitly tend to take on different natural paired contrasting roles.
In fact, I think people taking on these different roles can greatly
enhance the process -- so it may be worthwhile for people to
explicitly take on these roles (and switch off from time to time)!
The sort of thing I'm thinking about includes:

Optimist/Pessimist: One person can be trying to think 3 steps ahead,
making intuitive leaps forward, assuming other details will work out
or as yet unproven lemmas will be proven. And another person can try
to be the skeptic, making sure that the assumptions being made to move
things forward aren't completely out of line, that details eventually
get filled in, and that the proofs don't break.

Writer/Editor: When one person writes, the other should read like a
hypercritical reviewer.

Implementer/Debugger: It can be time-consuming watching over someone's
shoulder as they code trying to catch mistakes on the fly, but it can
be an effective way for two people to code together.

There are other natural pairs of roles people can take on doing research,
and I think it's useful to be aware of them so you and your collaborators
can work together more smoothly.

Now we'll talk a bit about the Polymath project, which represents an
extreme experiment in collaboration -- research via blog. Is this the
future of research, as new communication tools make group research on
this large a scale possible? Does this paradigm seem helpful or
harmful to the research process? What is the right size for a
collaborative group, and why? Let's discuss...

Assignment Re-Use

For discussion: How much do you re-use assignments from year to year?

I think in computer science, assignment re-use is much more common than in other areas. In part that's because other sciences more naturally have "parametrized" problems -- you change the numbers, you get at least a nominally different problem. CS assignments don't always naturally fit that mold. Programming assignments can require a long time to design, and don't naturally parametrize. (Indeed, part of the goal in writing a program is that you can give the program different inputs!) With theoretical assignments, you can try to change the setting (the Kleinberg/Tardos book does a nice job trying to give different settings -- story problems -- in various exercises for specific techniques), but if you're asking for a proof, it can be hard to modify substantially. Good problems often get re-used.

A problem with assignment re-use that I'm unfortunately quite familiar with as an ex-member (and currently "on-call consultant") for Harvard's administrative board is that solutions start to circulate and copying can occur. When one student copies another within a class, it can already be difficult. (The question of whether the information was "given" or "taken" can be important in deciding the appropriate response.) What about when one student copies work from a student who has already finished the class? What responsibility, if any, does your institution expect people who have finished a class to take for not sharing their work inappropriately?

DCC 2009

The list of papers for the 2009 Data Compression Conference is available.

I haven't been to the DCC for some years. I've had some papers there, and served on the PC a few times. I remember it as a fun conference, with people from a mix of areas fairly loosely connected by the general theme of compression. It was also well organized, and pleasantly located at Snowbird, Utah, every year, so you could walk from the conference room in the hotel right out to the slopes.

I know they're very interested in papers from the "algorithmic" side of the world. With any luck, some of the projects from my graduate class this year will be on compression, and I may soon find myself with a good excuse to go again.

Enrollments 2009, Update

Sometimes, enrollments drop the first week, as students see the first assignment, or the first few lectures convince them to switch out. (And some students start out taking an extra course and then drop one as they figure out what they like.)

This year, my numbers are holding remarkably steady.

CS 124: 84
CS 222: 24

Both classes have "officially" gained a student since the last post. In fact, more students will likely come in; I know there's paperwork in the pipeline for a few more students for CS 124; and one student in CS 222 brought in a couple of friends from MIT who may cross-register into CS 222. I suppose it will be at least another week before I have the final numbers.

Of course, assignment #1 for CS 124 is due today. That might have the effect of getting a few students to drop...

In any case, the huge jump from last year for CS 124 (again, described in the last post) has held up. I'd like to understand how much of that is due to cyclical increases in CS enrollments, and how much of it is due to our new introductory class bringing people into CS. Please comment on whether or not you're noticing increases in enrollments, and their size, in your classes (or department more generally).

Polymath Project

Reiterating some other blogs, I point to the Tim Gowers's project, asking the question "Is massively collaborative mathematics possible?" Like others, I intend to show it to students, and discuss the ways in which it is like -- and unlike -- less massively collaborative research.

A complaint I often hear among faculty is students in Computer Science (and, I would imagine, mathematics) don't realize how social research in CS (and mathematics) usually is. The stereotype of sitting along in your cubicle working on code all day is out of touch. CS papers generally have many authors; it actually seems research in the liberal arts is less interactive, with people toiling, solo, on their own book projects. If the project does just a little to correct that impression, it will be a success in my mind.

Another New Blog

Another new blog, this time by Luis von Ahn. I'm deeply pained by the fact that besides being brilliant, he's apparently very funny. I laughed out loud from this post on Real Men of Genius, and have often wondered (out loud, even) why I don't get tips.

An Article on Genius

While I don't usually discuss things I've read, this article on genius from the New Yorker a few months back actually seems relevant to our community. Academic genius, in the stereotypes I know, burns brightly young. Can we foster the other type of genius discussed in this article within the competitive academic structure?

Comments from Jennifer Rexford

Just in case people might miss her comments, I asked Jennifer Rexford for her input on conflict of interest issues, and she added some of her thoughts to a previous post (end of comments of Part III).

Also, she pointed me to related discussions at the SIGCOMM blog.

http://blog.sigcomm.org/2008/09/fairness_of_sigcomm_conference.html
http://blog.sigcomm.org/2008/09/openness_of_the_sigcomm_confer.html

I think it's worth pointing out -- the SIGCOMM community has a blog. And they discuss as a community issues like how conferences should be organized on it. I admit, it all seems nascent still, but interesting nonetheless.

STOC PC Wrapup

I think -- hope! -- this will be my final post on STOC for a while.

As my posts have made clear, as STOC chair I chose to experiment with a few things. Indeed, even posting about the PC process as much as I have on this blog has been something of an experiment. So now's a time took back and reflect on lessons learned.

To summarize some of my previous posts, here are some recommendations for the chairs of the future (or the steering committee) :
1) Move to co-chairs instead of a single chair.
2) Increase the PC size -- a small difference is worth a lot in coverage and reducing papers/PC member.
3) I find the 1-5 scale helpful in clarifying the easy accept/rejects and papers with great differences in opinion. It also helps to check that PC members are being consistent.
4) Decide your conflict of interest policy early, make it clear to the committee, and prepare for its implications.
5) Keep the meeting running smoothly; insist that if there's agreement on a paper that discussion is limited.
6) Automate as much as possible; find software you like working with.

I also have observations for authors and other members of the community.
1) When submitting an short abstract (like those that are being distributed with the list of accepted papers), just submit plain text. Your text is just being put in a database and moved around at various points. Its main use is for someone to skim it to see if they want to review the paper, or later, to attend your talk. Any special characters are likely to mess up some system at some point; Latex should be kept to a minimum.
2) Start earlier and have someone proofread your work. Errors in a proof -- even trivial errors -- are a sure way to reduce confidence in the acceptability of your paper. Other errors or typos create a bad impression. And a poorly written intro does hurt -- if we can't understand your contribution clearly, it's hard to accept the paper.
3) Most importantly to me, please don't ask annoying general questions like "When will accept/reject decisions come out", "When will we get the reviews?", and "When will the list of accepted papers go up?" Anyone who asked me one of those questions -- even anonymously on the blog -- please know that I figure you owe me a drink, and I expect you will pay up at the conference or your first opportunity. The answer to all these questions is "As soon as possible." In some cases there are administrative things going on you may not be aware of (reviews being finalized, authors changing titles or abstracts, etc.). In some cases the delay is simply that I have a life and a job that are taking priority. In any case, I can explain to you further why it's rude to ask such questions, but if you buy me the drink, then I'll probably happily spare you the explanation.
4) If you do have a special question or request -- like you need to schedule your talk on a specific day -- a little politeness, and patience, goes a long way. Remember, there are a few hundred of you, and just one of me... (And seriously, if you need to schedule your talk on a specific day because of a conflict, let me know NOW!)

STOC PC Meeting : Part V (Software)

I used Shai Halevi's conference software for STOC. I must admit, I was swayed by Shai's willingness to host the software and help out in a pinch -- I didn't want to deal with Harvard's IT staff being off-hours should a disaster happen. And while no disasters happened, Shai was a great help whenever anything did come up. I (and the rest of the community) owe him thanks for volunteering his time specifically for STOC, as well as more generally for creating the software. I really can't imagine running a PC meeting without such software.

Shai's software seems very similar in spirit to HotCRP, which I've been using recently as a PC member for some other conferences. I like them both. I'd have to say HotCRP seems a bit more polished, like it has gone through some more iterations, and has some more features than Shai's software. On the other hand, if you like control, you can apparently readily modify Shai's code (and the resulting conference database) directly to get what you want. I prefer them both to my experiences with EasyChair. If you're going to chair a conference, you should definitely check out Shai's page.

It might be worthwhile for SIGACT (or some other appropriate group) to look into having a common hosting platform and support for this sort of stuff. (Someone else I knew was using HotCRP for her conference, and when I asked how she set it up, she said that USENIX, the sponsor organization, hosted the conference software for them...) A standard default configuration maintained centrally would avoid having to "re-invent the wheel" each time someone takes over the conference. Or perhaps in the end we'll just leave it to EasyChair, which offers a perhaps less appealing standard default, but at a good price (free, currently).

STOC PC Meeting : Part IV: (Conflicts of Interest II)

Back to STOC stuff, continuing my past post on conflicts. While the theory of how to handle conflicts is one thing, the practice is another. How did things work in practice?

For those who say it's mildly annoying, I admit I agree. People having to leave the room is obviously less appealing than people not having to leave the room -- I'm not going to argue that. But really, I think the annoyance is minor, at worst. In most cases, zero to two people had to leave the room. People seemed to pay attention and get up and leave when they had to. (Arguably, people pay more attention to what's coming up when there are conflicts, which is actually a plus.) We could have been better about remembering to call people back in promptly. With practice, I don't think that would be a big deal either.

I didn't feel that we lost out on needed expertise because of the policy, but again, the implementation was more flexible than in networking conferences I've been involved in.
One PC member insisted on leaving the room for a discussion and vote because of a conflict, but we insisted they stay to answer our questions first!

Overall, I did not find it overly disruptive. And I think such a policy greatly reduces or even avoids worst-case scenarios where a PC member -- intentionally or unintentionally -- biases the outcome of a paper where they have a conflict. I've been on many PCs over the years, and I've seen it happen more than once. No, I'm not saying such happenings are rampant -- I think they're rare -- but I think they could be rarer still. To me, the annoyance involved is a small price to pay for that. Also, I think even if you disregard the possibility of someone intentionally pushing a paper where they have a conflict (which, actually, does happen), on the whole people underestimate the power of unconscious and unintentional bias.

Paul Beame (in comments to the previous post) says that people should be allowed to stay in the room, but remain silent and declare conflicts as they arise; and similarly, that software shouldn't block people from seeing reviews/discussions on conflict papers. I think he offers a consistent alternative, but I (as he knows :) ) disagree. His approach seems designed to avoid any possible manipulation of decisions by PC members that may have a conflict, which of course is all to the good. In practice, in my experience, that silence rule is not generally maintained. (For a variety of reasons, many of them laced with good intentions. It's hard for experts to stay quiet, particularly when a colleague/student/etc. is involved.) He ignores the issue that simply having the person in the room may stifle some discussion in the PC meeting. (Junior people can be and are often intimidated, to various degrees, by senior people in such a setting. We can argue about whether they should be, but in practice, they can be.) And finally (and most importantly), he's dismissing the issue of information in reviews or discussions getting back to the authors. (Yes, discussions are confidential -- as are the parts of the reviews labelled "to the committee" instead of "to the author" -- but as we've read in the previous comments, there can be a fair amount of leaking of information after the fact.) My thought is that when you say you have a conflict, that precisely means you SHOULD NOT see the reviews or hear the discussion for the paper -- the networking standard -- unless there's an important overriding reason for you to do so. That prevents you from intentionally or unintentionally leaking supposedly confidential information.

And to be clear, I think the "we need the expertise" argument is overhyped. In cases where it's needed, I would agree exceptions need to be made. In most cases, it's not needed (there are other people in the room capable of making the judgment), but people don't want to be left out of the decision process where they are also an expert. There's a difference.

I have no regrets about implementing things this way. Others disagree. Overall, I think it's a topic worthy of more community discussion. In particular, the use of conflicted subreviewers that also came up in comments on the previous post really deserves some attention. I think a more consistent and thought-through standard should apply. Our community may have it's own standard, but as a community I think more discussion including ackowledgment and understanding of the pros and cons of the various possible approaches would be useful.

STOC Links

Here they are.

Titles and authors: http://www.umiacs.umd.edu/conferences/stoc2009/titles.shtml
Abstracts also (html): http://www.umiacs.umd.edu/conferences/stoc2009/abstracts.shtml
Abstracts (raw text): http://www.umiacs.umd.edu/conferences/stoc2009/abstracts-raw.txt

Enrollments, 2009

CS-124, Algorithms and Data Structures

2008 : 36 students
2009: 83 students

That 83 will probably deviate by a few after the last add/drops shake out, but it's a somewhat surprising doubling+ of the class size. That's what we get for introducing a new, dynamic instructor for the intro CS course last year, who seems to have boosted CS enrollments across the board (taking effect this year). I was expecting 60-65.

By the way, 2008 was the lowest enrollment I've had, by far, although the previous few years had been in the 40's. My biggest year, back in the boom, was 90.

I'm double-teaching this semester, and my graduate "Algorithms at the End of the Wire" class has 23, which is pretty standard. (I think the biggest year it had more than 40... and given this enrollment boom, that's what I'll expect NEXT time I offer it.) It might lose one or two but that should hold steady. I admit I'm pleased to look around the room and see a lot of the top undergraduates I know taking the course (which was one of the reasons I arranged to double-teach this semester; I wanted them in the class before they all go and graduate...)

Rule Stupidity

Note: Update 1 Below

I thought I'd give my readers a STOC-break and discuss beginning-of-the-semester frustration with a stupid Harvard rule.

Setup: Math 123 (2nd semester algebra) and CS 124 (my algorithms/data structures course) are at the same time this year. Both are important prereq courses for many other courses. There are a small number of joint Math/CS majors, who, naturally, really want to take both. (They're both only offered spring semester.)

Now, since my class is recorded and put online for the Harvard Extension School -- usually now within 24 hours -- and Harvard students are given access to all these videos, this wouldn't seem to be a problem. The students take both classes and just watch the videos for mine. Is it ideal? Of course not. But it's better than making them wait a year to take one of these important classes. I do have Teaching Assistants and sections and office hours and TA office hours and all class notes online and such so they do have resources besides the recording. There are other details -- arranging final exams, for instance -- but I (and the math professor) have expressed our willingness to deal with that.

The administration says no.

Apparently, the rules on the books for "simultaneous enrollments" (taking two classes at the same time) won't allow for recorded lectures, and despite my plea for an exception in this clearly suitable case, the rule is, apparently, the rule.

Except (as I've also informed the rule-enforcing-body) it's really not. Because in this case the students will simply sign up for an independent study with me, CS91r, and have the content of their independent study be the class CS 124. This is less than ideal for everybody -- the students don't get proper credit for the course they're taking, I don't get the TA-resources associated with the students, and there's more paperwork for everyone. But it seems clear to me (and, apparently, the students, who asked me to do this) that this is in the students' best interest, so that's what I'll do.

But still, the rule-enforcing body says, the rule's the rule, and they'll enforce it.

I'm sending them all a link to this post so they can defend themselves if they choose. Feel free to comment with your own stories of stupid rule enforcement at your university...

Update 1:

I'm happy to say that I've had further conversations with the powers-that-be, and I think we've come up with a mutually acceptable interpretation of the rules that will allow the students to register for the class. I have to thank the powers-that-be for working with me, and on reflection, it undoubtedly wasn't because I got angry about it, but simply because I was consistent in asking if there was some kind of solution. It's still got to pass through a vote of a committee, but I'm optimistic, and I certainly feel they listened to my concerns -- which doesn't always happen with a bureaucracy!

STOC PC Meeting : Part III: (Conflicts of Interest)

I introduced another change for the PC meeting for STOC this year. My experience is that theory conferences are somewhat "loose" about conflicts of interest. What I mean is that while PC members can't submit papers, and it's expected that you don't review papers of current (or recent) students/advisors, other than that conflicts of interest aren't usually treated as a big deal. As a contrast, it's standard for the networking PCs I've been on to be at least as rigorous as an NSF panel; for example, if a paper has ANYONE at your institution as an author, you have no electronic access to the reviews and you're expected to leave the room during the discussion (and similarly for other "standard" conflicts of interest, including any collaborators from say the last two years). In my experience, on theory PCs, people don't leave the room just because they have a conflict. It might be expected they'd not comment, although it's not always clear to me this expectation is followed.

Indeed, I remember my first SIGCOMM PC -- the first hour or two I kept wondering why people kept coming and going in and out of the room every time a new paper was discussed. It seemed like a lot of people were off to get coffee when they weren't a reviewer on the paper. Someone explained to me that these were the people with conflicts, and I was shocked at what was considered a conflict. (I figure anyone from UCSD or Microsoft currently has to leave the room for at least 1/4 of the papers on any networking PC.)

Interestingly, when I mention this difference in "style" to people, networking people seemed shocked (and maybe a little horrified) by how theory PCs handle conflicts, and theory people seem shocked by how networking PCs handle conflicts.

[Aside: it's a bit interesting to think about further this in light of the comments on my previous post on sending scores, where many people note that many authors can get "inside information" on their paper from PC members after the fact, even though the meeting is supposed to be "confidential". This post won't cover that further -- it was actually written before the other post!]

It's a bit hard to imagine utilizing such a strict conflict of interest polity for a theory PC. The community's a bit smaller, we're highly collaborative, and the papers can be so specialized that if you stick hard and fast to conflict rules you might not have enough PC members who are really suitable to judge a specific paper. Another negative is that it does cost time -- there's a switching cost when people enter and leave the room.

But I asked the PC for a straw vote, and a large majority of those with an opinion thought it was a good idea to have people with conflicts of interest leave the room, primarily for the obvious reason that it's a lot easier to have an open discussion when you're not worried what some people might hear. (Not surprisingly, younger PC members on average seemed to think this was a bigger concern.) I should be clear, however, that this idea was quite controversial; many PC members expressed a very clear and vocal dislike for a policy that had people leaving the room regularly. Indeed, it was definitely the most controversial decision I made as the PC chair.

In order to be practical, I made it clear that I understood there would have to be exceptions, as needed, to deal with special cases, since I didn't really plan for this policy from the beginning (including when making paper assignments, although I did ask PC members to mark conflicts with the software when ranking papers they wanted -- this did not seem to be treated uniformly and universally by the PC, again because it's probably not standard in theory conferences). But the policy I planned to implement was essentially the following: if you had any standard conflict on a paper, and there wasn't a very good overriding reason for you to be in the room (e.g, you were an original reviewer, or you had a specific expertise the committee needed to evaluate the paper), you should leave.

In the next post, I'll talk about how that worked.

But before that, I think this is a matter the community (or, to the point, conference steering committees) should address. My personal take over many, many PCs is that while the strict conflict interpretation used in networking conferences may not be completely workable for a STOC/FOCS type conference, if I had to choose, it's clearly better than the "We'll assume everybody will behave properly" approach taken at most theory conferences. (Many theory conferences take a strict line on PC members not submitting, but then do essentially nothing about other possible conflicts -- that just doesn't seem right.) I think something in between these two extremes are possible, where exceptions based on needed expertise is possible, and that's what I tried to implement, but it could use some more careful thinking through. What do you all think?

STOC PC Meeting : Interlude

First, I'd like to remind everybody that the day before STOC this year, instead of tutorials or other activities, we'll be having a special event for Les Valiant's 60th birthday on Saturday, May 30th. There will be talks by a number of people to commemorate his tremendous body of work. The organizers are currently trying to finalize arrangements so that the event is free to everyone, but if needed there might be a nominal registration fee to pay for coffee and such. Confirmed speakers include:

Jin-Yi Cai
Steve Cook
Vitaly Feldman
Mark Jerrum
Mike Kearns
Michael Rabin
Rocco Servedio
Paul Valiant
Vijay Vazirani
Avi Wigderson

We hope you will plan on attending.

Second, I sent out the accept/reject notices. Comments coming later this week.

STOC PC Meeting : Part II

For this PC, I asked reviewers to use a 5 point scale, corresponding to

1: Bottom 1/2 of submissions.

2: Top 1/2 but not top 1/3 of submissions.

3: Top 1/3 but not top 1/5 of submissions.

4: Top 1/5 but not top 1/10 of submissions.

5: Top 1/10 of submissions.

I'd like to reflect on how that experiment worked.

Overall, I think it worked well. One plus it that I think the scale makes it very easy to find the bottom half of the papers (easy rejects) and top 10-15% of the papers (easy accepts), so that less time needs to be spent discussing those papers.

On the other hand, on day 2, we were left with a bunch of papers with scores with about a 3 average. This makes sense -- since we accepted about 25% of the papers, papers with about a 3 average were, by definition, borderline. In short, a grade of 3 could mean, "I like the paper but it's a reject" or "I like the paper and it's an accept."

One solution might be to tweak those percentages (an experiment worth trying) to better match the acceptance boundary. But, at the end of the day, I think the fact of it is that borderline papers are hard -- that's why we still have face-to-face PC meetings. No matter what voting system you use, these papers are the hardest to deal with. When you get down to these papers, the real question is, "Do you want to accept the paper or not?" I think a mechanism in the review software to allow a second round of voting -- corresponding to the question, "Conditioned on this being one of the X papers left we have to decide on, do you think we should accept or reject?" would be useful and would have saved us some time. In practice, we just did that verbally (approximately) in the meeting (as part of the discussion).

I think there are other advantages of this 5 point scale. When a PC member isn't following the scale -- say assigning much less than 1/2 of their papers scores of 1, or much more than 20% scores of 4 and 5 -- it's essentially immediately apparent to everyone. That's more transparent than the 10 point scale. (One can always use software that "re-calibrates" individual's scores to some sort of baseline -- that also works, but I think is much less transparent.)

To me it's just clear the 5-point scale approach must be better. At the end of the day, we have to make a binary decision on each paper. This scale gets us most of the way there, while giving enough room to distinguish the best papers and papers that need more discussion. I would use it again as a chair, and I prefer it as a PC member as well.

There's one downside to this scale -- which I'd appreciate comments on. Do we send the scores with the reviews, or not? It can be disheartening to get back scores of 1. On the other hand, it's always annoying when your paper is rejected, and I think scores provide useful feedback to the authors. (If you got all 1's and 2's, perhaps you should consider a conference other than FOCS for re-submission.) Several PC members said we shouldn't send the scores with the comments. I think we should -- of course, I'm used to getting scores of this form back from networking conferences. What do you think?

STOC PC Meeting : Part I

Over the next week, I'll present some thoughts related to the STOC PC meeting, which wrapped up earlier today. (Please don't send mail to ask about your paper(s). Messages will be sent out sometime next week.)

Today's post will be about basic logistics, which you wouldn't normally think about, unless you suddenly found yourself running the meeting. We started with roughly 150-160 papers left to consider. At 5 minutes on average per paper, you're already at about 13 hours. And if you slip to 6 minutes on average per paper, well, now you're at 15 to 16 hours, which when you consider overhead time (computer setup, lunch, the occasional rest break), you see the difference between that 5 and 6 sharply when you know people have flights to catch at the end of day 2. I think the hardest part of the meeting, from my end, was simply time management.

We started at 9 am on day 1, with plans to break at 6. It became clear that we were falling behind schedule, so we changed the dinner reservation and kept going until 7. We still seemed behind -- and with most of the easier accept and reject decisions behind us -- so we agreed to meet at 8:30 am on day 2. The mumblings and rumblings over dinner of "We're never going to finish on time" were worrisome, and I stayed up late looking over and organizing the remaining papers, so we could go through a bunch very quickly on day 2. I was definitely aided in this goal by the rest of the committee, who had clearly also done additional prepping post-dinner and were ready when they came in the door. In the first hour we made up our deficit in the schedule, and finished our decisions around 2:30, actually leaving us a comfortable amount of time to talk about other organizing issues before people started heading to the airport for their flights around 3.

While it all ended up OK, perhaps I could have done better day 1.

Also, the lesson for future PC members -- be ready to talk when your papers come up, and be prepared to make your points quickly. The seconds add up! I thank the committee for both putting in the extra long hours and for being well prepared, so we could finish on time. And everyone who submitted papers should be thanking them as well.

Another piece of "chair advice" I was told that I can't over-emphasize enough -- have someone whose job it is take notes and record the status of papers as you go. During the meeting I vaguely asked one of the PC members to keep track of things. At the end of the first night, trying to prepare for day 2, I would have been lost without his guide as to where everything stood. As chair (particularly as a single chair -- we should have co-chairs...) I found it difficult to keep things running, enter things into the system, and track things so I could go back and really see where everything was; the notetaker essentially did the tracking job for me, making the whole meeting run much more smoothly, and allowing me to get some sleep before the second day.

And speaking of sleep, I'm very tired, and need at least a day without thinking of anything related to STOC.

Graduate Student Folders Part II

We're getting to the point where we have to make our decisions on graduate student admissions. In the theory group at Harvard we got a sizable number of folders that we've cut down to about 25. We'll probably cutting those down to about 10 acceptances.

There's clearly an abundance of good people, who could become solid TCS researchers. And as we went over in my last post on this, it's difficult to choose based on an application who will become successful.

My guilt in having to choose from among these many talented people is assuaged mostly by my concern for the people who we do admit to graduate school, especially in TCS. Where will the jobs be when these people graduate? I've heard the arguments that CS is still expanding, well maybe not in America but elsewhere in the world, and that PhDs can find other work besides being a professor. I've seen that most of the other students I knew as a graduate student in Berkeley have ended up with good positions -- mostly professors -- albeit some after a number of years of postdocs. But still, at the end of the day, when I do the math, it just doesn't add up. I expect to be in my position for at least 30 years (barring the current curse of Harvard CS faculty to be moved into administration); how many professors (or scientists at research labs) can I produce over my lifetime?

The financial meltdown has only raised my concerns that in CS generally (and theory in particular) we've been living through a bubble, and we'll all be shocked when that bubble pops, though we shouldn't be.

I'm not so entirely pessimistic -- CS PhDs, for as far as I can see, should have no trouble getting pretty good jobs. But how many will get the jobs they think they're getting the PhD for? (Note the internal mental bias here -- professors remember mostly the students who did go on to get faculty/research jobs...) We'll see.

SIGCOMM PC starting... STOC PC ending...

I guess there's another week until the "official deadline" for SIGCOMM, but the deadline for registration of abstracts/titles has already happened, and I was asked to "bid" on papers I was interested in. It's hard to tell from the limited information, but it seems like there are plenty of interesting papers. Mostly I was looking for papers covering algorithmic engineering or just plain algorithmic problems, the econ/CS interface, and coding (network coding seems to be getting bigger), but there were certainly papers outside those areas that caught my eye. Out of the 300-400 submissions, there were more than 50 that looked interesting enough for me to request them; I was only asked to choose at least 30 to start.

Of course, since the whole process is double-blind, I don't know who submitted the papers, and hopefully the authors won't be able to figure out which reviews I end up writing.

This would all be great fun, but there's of course STOC to finish up. We've rejected about half the papers so far (we're still in the pre-meeting stage). Of course, that's the "easy" part. Now things get harder.

More on Algorithms and Implementation

In the comments on my last post on algorithms and implementation, someone asked where to publish when you sit in the middle, and how can a graduate student succeed by being in the middle. The comments seemed to suggest that publishing was hard and succeeding as a graduate student this way was largely impossible.

Sadly, and disconcertingly, I find myself largely agreeing. I think the theory community has developed to the point where, almost universally, if you want to earn a reputation as a top theorist in graduate school, you have to publish FOCS/STOC/SODA papers. And really this can't be done by focusing on practical issues. More practical papers can be published in other venues -- WWW, INFOCOM, even SPAA and PODC -- but to the theory community these papers don't carry as much weight. (Note: yes, obviously there are RARE exceptions.)

Strangely, I still think there's a reasonable job market for practically-minded theorists, both in research labs, and in smaller universities, where they'd much prefer a theorist who would interact with other groups (like networking or AI) because they really aren't big enough to have theorists who don't have "outside interests". And I think evidence of being able to work with practitioners helps most any theorist looking for a job -- you just can't build your reputation on it. But it can be hard to get that balance of theory and practice "right" as a graduate student.

I see a fair amount of people who are theoretical but practically minded simply going into other fields, either as a graduate student or after. You can be a "theoretical" networking person or AI person and succeed, and a number of graduate students who could be theorists figure out they'll be better off in these areas. You can start out as a FOCS/STOC/SODA person and then branch out to other areas. Go look at Karger or Kleinberg's DBLP pages and see how much more they've been doing in the recent past outside the confines of FOCS/STOC/SODA compared to earlier in their careers. (Or look at John Byers and Soumen Chakrabarti, who worked primarily in theory as graduate students, but switched to other areas.)

Perhaps this would make a good conference panel someday. (Offhand I'd recommend getting Mikkel Thorup and Muthu Muthukrishnan to participate -- they seem to me like role models for people who want to sit in the middle -- though I can think of many others as well...) Heck, come to think of it, I'm the STOC chair, maybe it would make a good panel coming up real soon. Please let me know if you'd like a panel on this issue -- something like "How to Succeed doing Practical Theory?" -- at STOC.

Algorithms and Implementation

I was leafing (again) through George Varghese's text, Network Algorithmics, and this caught my eye:

In summary, the uncritical use of standard algorithms can miss implementation breakthroughs because of inappropriate measures (e.g., for packets filters such as BPF, the insertion of a new classifier can afford to take more time than search), inappropriate models (e.g., ignoring the effects of cache lines in software or parallelism in hardware), and inappropriate analysis (e.g., order-of-complexity results that hide constant factors crucial in ensuring wire speed forwarding).

Thus another purpose of this book is to persuade implementors that insight into algorithms and the use of fundamental algorithmic techniques such as divide-and-conquer and randomization is important to master.

These words succinctly express feelings I commonly have. Standard algorithms theory often fails to live up to its promise in practice, untethered as it has become from applications. At the same time, a properly designed algorithm can yield immense breakthroughs in performance, so implementors cannot do without them. I believe we need more people willing to sit in the middle, but perhaps first we need more creative ways to bring theory and practice, or theorists and practitioners, together.

Georgia Tech visit

I had the pleasure of visiting Georgia Tech Wednesday, giving a theory seminar, in this case my survey talk on Deletion Channels.

A fun day filled with conversations about research, kids, and other goings-on. Highlights include getting to catch up with my academic older sister Dana Randall and younger brother Eric Vigoda. And this trip, as it seems with every trip I've taken to Georgia Tech, my host Vijay Vazirani exceeded expectations with his choice of dinner location. (And by now, I have high expectations for meals in Atlanta!)

The department has really grown into a theory powerhouse (and has a very strong networking group as well). For some time it's been on my list of schools undergraduates should think about for graduate school (but might not have realized they should be thinking about). The visit was a strong reminder of why.

Summer Funding

I should have blogged about this before, but didn't notice over break that Yale had "agreed to pay7.6 million to resolve allegations" regarding how it was handling research grants. My understanding is that this primarily related to summer funding -- the government apparently objects to professors saying they're working 100% on their research over the summer and then doing other stuff. (You know, pesky things like writing letters of recommendation or preparing for next semester's classes.) Anyone with more info, please speak up or link in the comments.

Now, of course, this all just boils down to accounting. The university (nominally) pays 9 months of salary, but strangely, we seem to be expected to also be working on our government-funded research during the academic year as well. One would think there might be some understanding that there's some appropriate blurring of time spent on various tasks. But Harvard, responsive as always when it sees another school getting fined, is changing its process to avoid the same sort of investigation. I don't quite get how this works, but apparently my June summer funding for '09 will be paid out over the spring semester, and the rest of my summer funding will be paid out over the fall semester. I'm assuming that when I eventually have to fill out forms accounting for my time they'll be modified so that research time during the year is counted some way as well.

As one colleague said to me, the new system is stupid, but so was the old system, and sometime down the road, some bureaucrat will decide this is wrong, and we'll switch to a different stupid system. What I find most odd about the new system is it seems at least part of the time I'm getting paid from a government grant for work I will only do in the future. That's OK with the government? I imagine if for whatever reason I later decided not to work over June, they'd pull the money back out of future paychecks. I also suppose this provides some understanding of why grant overhead rates, which I generally complain about, are so ridiculously high; if there's really this much paperwork (and computer accounting software setup) involved in grant management, maybe the overhead really is necessary.

Graduate Student Folders

When I'm not looking over STOC papers the next few weeks, I'll also be looking over graduate student admissions folders. (At Harvard, we're small enough that the theory folks just split up all the folders and then meet to discuss them.) Even though I've been doing this for a while, I'd love to hear from all of you -- what should I -- or we as a community -- be looking for in selecting graduate students?

I think that on the theory side we tend to look for pure brainpower over other skills. Arguably moreso in theory than in other subjects, raw intelligence matters most. (I'm not saying I agree with that argument; I'm just saying it's an argument.) I think we also know that grades don't necessarily provide the right information we need to judge this, however, and so we look for evidence that one has the ability to do research in the form of actual research projects accomplished or letters from faculty members we know (and believe) who suggest that there's intellectual power and creativity there.

I do think most faculty do keep in mind the other skills that can make for a successful student. Communication skills, the ability to work well with others, a sense of what they want to accomplish, the mindset to deal with the one-step-forward-two-steps-back nature of research -- all of these also come into play in decision-making. These can be much harder to judge, however, unless they're clearly marked by their absence in some way.

I wonder if the competitive landscape for graduate slots at the top schools causes us to miss out on some promising people. Over at the FemaleScienceProfessor blog, she discusses why she'd rather take the motivated B student over a lot of A students for undergraduate research projects. I'm curious, having no evidence one way or another, do people think we're doing a good job getting B undergraduates who could become great researchers into the pipeline early on enough so they can construct a good application for graduate school? Do we accept enough of these students when they apply?

Deletion Channel Paper

There's a new paper with bounds on the capacity of the deletion channel on the arxiv by Fertonani and Duman. The main results are some new upper bounds which generally are better than the upper bounds found in a paper by Diggavi, Mitzenmacher, and Pfister, which was the first look at the problem in a long while.

The bounds achieved are very nice. They use a simpler approach than our earlier paper, essentially dividing the input or output into fixed sized blocks and numerically calculating the capacity per block. With clever manipulation, they can extend the bounds in various ways -- the nicest result (in my mind) being that, in the limit as the deletion probability d goes to 1, the capacity is upper bounded by 0.49(1-d). [Our previous result gave a bound of 0.79(1-d), and some of my work on lower bounds showed that the capacity is at least 0.11(1-d).]

It seems to me their work raises some interesting questions. One question is the following: at some point, they have to rely on numerical calculations to determine their upper bounds, using the Blahut-Arimoto algorithm to calculate the capacity of a fixed finite channel. Their approach is limited by this calculation; for instance, if one "chops" the input into blocks of 10 bits, then there are 1024 possible input sequences and 2048 possible output sequences for the deletion channel, and essentially they have to compute the capacity of this fixed channel in a "brute force" way, which requires keeping track of the probability that each input results in each output. Bigger blocks means better bounds but bigger calculations. (Technically one can find ways to avoid keeping the entire 1024 by 2048 probability matrix, since it's fairly sparse, but the calculations still grow big very fast.)

Is there any hope for an approximate version of the Blahut-Arimoto algorithm that would give provable upper bounds on the capacity but could take smaller time/space? It would seem there might be other uses for an approximate expectation-maximization procedure, although perhaps generally one wants such good approximations that there's no real benefit in practice. Any thoughts?

Co-Chairs

Although it's far from over, I'm already clear that one of my recommendations for the future of FOCS/STOC conferences is to start having co-chairs instead of a single chair.

The reasons for having co-chairs that I can see include:
1) Chairing involves a lot of administrative work, often bursts for short intervals. Being able to share that kind of work seems to have a huge upside.
2) Although I don't think it's come up for STOC yet, having a co-chair watch your back can help avoid silly mistakes.
3) Particularly for FOCS/STOC, having co-chairs from two different subareas (one from a more algorithmic side and one from the complexity side) would seem to offer better coverage.

Many conferences in other areas of comparable size to FOCS/STOC have co-chairs (e.g., NSDI, SIGCOMM that I know of) and in my experience as a PC member it's always gone well.

What are the possible downsides of co-chairs?
1) Whenever two people are co-in-charge, they have to work together well. I hope it wouldn't be too hard to find people who could capably co-chair for these conferences.
2) I imagine it can be hard finding people willing to chair; now you'd have to find 2! Although I actually think it might make it easier to get people to accept if they can co-chair -- it will seem like less work, and if one person is more experienced, you could have a somewhat less experienced person co-chair.

So, how's STOC going?

I suggested that I'd blog about my experiences as STOC PC chair, so I thought I'd give an update.

We're nearing the point where all the "first round" reviews are supposed to be in. All papers had 3 PC members assigned to them, and my goal was to have 3 reviews for each paper a few weeks before the PC meeting. So far, it seems to be going well; most PC members have been putting in reviews. A few who seem to be working with an offline scorecard haven't uploaded what they've completed -- which makes things a bit more difficult for me, naturally :( -- and I expect some papers won't have 3 reviews by the deadline for various reasons, the most likely being that a subreviewer hasn't finished. Subreviewers, please get things in! (And thank you.)

After that point, I hope to reject a slew of papers outright. Recall that I'm trying a new scoring scale. 1 = bottom 50%, 5 = top 10 %, other scores in between. Anything with 3 1's seems to be an easy reject. Arguably, if there's no score of 3 or above in the 3 reviews, a paper should be rejected. To be clear I won't make those decisions unilaterally, but will set up votes for the PC.

The other work at this point is finding more reviewers for papers with widely disparate scores (where the problem does not seem to be "this paper has a bug" that one reviewer noticed but others didn't, but rather a wide disagreement on the quality/importance of the result) or for papers that seem like they'll be on the borderline. Here I'm looking for people both on and off the PC -- so don't be too surprised if you get an e-mail asking for a quick review -- with the emphasis on trying to find relevant experts in the area of the paper.

How many papers will have both a 1 and a 5 score? (Or 2/5s, or 1/4s?) Seems like a statistic for the business meeting roundup. But so far, the answer seems to be more than you might think...

Preparing for Class

It's that time of the year where it's time to get my next class ready. I could use your help.

For various odd reasons, in the coming semester I'll be teaching both my undergraduate Algorithms (and Data Structures) class [it's not parenthesized like that in the course catalog, but it probably should be], and my graduate "big data" class, dubbed Algorithms at the End of the Wire. For the graduate class, I cover a variety of topics -- last time, the main areas were search engine algorithms, compression, stream-based algorithms and data structures, and coding (network coding and otherwise), and essentially each class the students are supposed to come in having read a couple of papers. One of the goals of the class is to present algorithmic theory and practice, so I emphasize trying to find practical papers that really make use of underlying theory, or theory papers that really try to impact how a practical problem is thought about. Another goal of the class is to introduce students to the ways of research, by having them read both ancient classics (like, say, Kleinberg's HITS paper) and more recent (e.g. the last year or two) papers.

I'd be interested in any suggestions for good papers for students to read -- particularly recent papers. Don't feel tied to the topics above -- I should be trying to keep up with good papers bridging the algorithm/theory divide in all areas!

Consistency in Scoring

Having just finished serving on the NSDI PC committee, and being hard at work on the STOC committee, one issue that has been on my mind is consistency in scoring papers. Ideally, when submitting to a conference, it shouldn't matter WHO reads your paper; your score should be intrinsic to your work. Of course, we don't expect -- or even necessarily want -- the complete ideal; there will be differences of opinion that occur for natural reasons. Arguably, for example, "visionary" papers are hard to judge and tend to lead to differences of opinion. So you can take solace that if you get widely varying reviews and your paper is rejected, your paper was probably just too visionary. The more cynical among us might instead think that large variances in opinion have to do with how close the reviewer is to the subfield of the paper. In theory, my take is that referees within a subarea generally give higher marks to papers in that subarea. (At NSDI, I found myself with a different impression; if anything, I thought referees working in a subarea tended to be a bit harsher towards papers in that subarea!)

My impression historically has been that there's more variance on the theory side of the world than on the systems side, particularly for the big conferences like FOCS/STOC/SODA. I was amazed, on the whole, at the consistency of NSDI reviews for papers I was on. STOC reviews are coming in, and I'm looking forward to seeing how consistent things are there, but my early impression is that there's not the same consistency, and it's interesting to hypothesize why. [Perhaps, after it's all over, I'll attempt to gather some real quantitative data on the issue, to see if my impressions match reality.]

I'll throw out a straw man for people to discuss (and attack). In theory, all (reasonable) papers start with the same basic grounding -- you have proofs of some theorems. After that point, though, things get a bit hard to judge. How "nice" are your theorems, in terms of technique/mathematical beauty/novelty? How "big" is your improvement over previous work -- for example, is improving an O(log n) competitive ratio to O(log n/log log n) "important" enough? How practical is your solution (hard to say, when nobody actually implements algorithms or gives performance results...)? A lot of this seems subjective, so naturally there are differing opinions.

In networking or other more practical fields, the same issues -- technique/beauty/novelty, quantity of improvement, practicality -- all come into play. But there's a lot more focus on the bottom line of "Could this lead to a substantial improvement for an important real-world problem." Perhaps this consistency in the criterion for what is a good paper leads to more consistency in reviews?

New Year's Affirmations

As the New Year beckons, I figured it was time for a post on affirmations, which I remember being interested in when reading about it one of Scott Adams' (of Dilbert) books (though I don't think he called them that). If you haven't heard of affirmations, it's basically the power of positive thinking. There are various forms; one is, take a list of goals you want to accomplish, write them down or repeat them to yourself every day, and you'll find they start happening.

Now, while I don't actually believe that positive thinking alone will allow me to prove P = NP (or the other way) in the coming year -- or, for that matter, win me a lottery! -- I do believe that the act of thinking clearly about the goals you want to achieve, and keeping them firmly in your mind, increases the probability that you will actually accomplish these goals. I personally find that when I set myself goals over multiple time scales -- a task list for the day, for the month, and for the year -- I'm surprisingly much better about getting things done. When I get distracted from setting goals, less happens. The conscious effort of writing tasks down and reminding myself of them makes them easier to accomplish.

So I encourage all my readers to take some time around the New Year and set some tangible, if difficult, work-related goals for the coming year. Maybe it's time to learn a new area or work with that person you've always wanted to work with. Or there's that result you know is just out of reach -- but you should keep reaching for it. Post them somewhere, remind yourself of them, and work to make them come true. I'd bet more do than you'd first think.

Whatever your goals are, best of luck with them, and for the New Year.

INFOCOM Miniconference

A number of commenters on my last post have mentioned the INFOCOM Miniconference. I hadn't actually known about the miniconference -- although I found out more details about it soon after the comments, as my second INFOCOM submission, rejected from the conference, was accepted to the miniconference. (I did have a paper in INFOCOM 2008, but my student Adam Kirsch went to the conference to deliver the paper, and I can't recall ever hearing anything about the miniconference format. Someone should have blogged about it before. :) )

100 additional papers -- a bit over 7% of the original submissions -- were apparently accepted to the miniconference, covering most of that "top 20-30%" range. The main difference appears to be the labelling (INFOCOM miniconference, not INFOCOM) and that the paper will be limited to 5 pages in the proceedings.

While I'm happy the paper got in, I must admit, I don't understand the reasoning behind the INFOCOM Miniconference, and I hope some readers in the know will explain and elaborate. If the purpose is to have a 2-tier conference, it seems an odd structure -- why not just accept 25-30% of the papers? (A few hundred pages in the proceedings wouldn't seem to matter much since it's on a CD?)

I wonder if theory conferences like STOC, FOCS, or SODA should adopt some sort of 2-tier structure in order to accept more papers. Certainly most people who have papers rejected from these conferences (myself included) believe they should have gotten in, and some fraction of them are probably right. On the other hand, such a structure would seem to lessen the prestige associated with these conferences. Any opinions?

INFOCOM paper, network coding

A paper I co-authored on network coding -- Network Coding Meets TCP (arxiv version) -- was accepted to INFOCOM. Full credit for the success goes to the graduate student Jay Kumar Sundararajan who led the project (and is graduating and looking for jobs this year...) Our goal (as the title suggests) is to make a TCP-compatible network coding congestion control scheme, and our approach uses an interesting variation on acknowledgments Jay Kumar had utilized previously; instead of acknowledging packets, you acknowledge "degrees of freedom" (or, encoded packets that will eventually decode to message packets).

The INFOCOM mail said 282 papers were accepted from 1435 submissions (post-withdrawals). A quick check shows that INFOCOM has been below a 20% acceptance rate regularly in recent years, and even assuming a completely unverified estimate that 10-25% of the submissions are things that really shouldn't have been submitted in the first place, in my opinion that's still a pretty low acceptance rate for what's supposed to be the big, open-tent networking conference of the year. (In the 1990s, the acceptance rate was more commonly around 30%.) I'm sure there were a lot of good papers that got rejected this time around.

Most networking conferences have acceptance rates around 20%. Is this a good thing? Conference competitiveness has been blogged about before, but there doesn't seem to be much of a high-level discussion about the issue -- I recently saw Ken Birman and Fred Schneier wrote an article about it for Communications of the ACM. Any ideas out there?

What Else Should Grad Students Be Learning?

Apropos of application season...

Graduate school is a long stretch of time -- 5 years (or more) for most people. There are few clear goals during that time, although the obvious one is to learn how to do good research, with the hope of getting a tenure-track faculty job. With this somewhat singular -- and difficult -- goal, it's easy to fall into the extreme of focusing only on your research to the exclusion of most everything else, or to waste a lot of time not really working. Both of these things may be OK for various individuals. (As some will undoubtedly respond, if you're doing great research, it can excuse a lack of many other skills. And many people don't mind spending an extra year at graduate school with a more relaxed lifestyle than life after graduate school.) But with the new year approaching, I thought it worthwhile to suggest some of the additional skills one should try to develop in graduate school over those stretches where you need to break from research -- skills which, unfortunately and understandably, are often given short shrift by the university. (Please add to the list in comments.)

1) Time management: How much are you working each day? (And how much time do you waste reading -- or worse yet, writing -- blogs?) Even if you don't set yourself to a regular 9-5 or 10-6 schedule, it's a good time to learn to manage your working and non-working patterns. My suspicion is that people who manage a regular work schedule graduate on average a semester or year earlier.
2) Writing/speaking: If ideas are our business, idea presentation is a big contributor to the bottom line. And if you want a faculty position, the ability to give a good talk to a general audience goes a long way. If your institution doesn't have a program for improving writing and speaking, start your own (like a student seminar series, no faculty invited).
3) Leadership: Find a way to lead a research project -- maybe advising/mentoring some undergraduates. Or organize a club or student group to make your department a better place to be. Eventually, the ability to organize people to follow your goals will make you more productive.
4) Entrepreneurship: Have you looked at the economy? And professor's salaries? Graduate school is where you're supposed to learn to be creative, and to develop specialized skills. It's quite reasonable to spend some of those creative efforts or utilize those specialized skills on money-making endeavors. While it's not for everyone, for some the tangible reward of money helps unleash creativity; for others, you may learn the satisfying lesson that your intellectual achievements bring you higher rewards than a big paycheck could (a lesson worth learning early on).
5) The skill to learn additional skills: If you're a theorist, learn to program a little. If you're a systems person, learn some probability or other theory. Maybe set aside a few days to learn time-saving Latex tricks, or some other piece of useful software. There are plenty of skills that will make you a better researcher/teacher/writer in the future.

NSDI Program Committee , Part II

Some lessons from a 1-day PC meeting (nothing really new, but I thought I'd write it down):

1) Face-to-face PC meetings involve far too much sitting. Especially if you fly in and out on the same day. (I know there's a time tradeoff in scheduling an "exercise break", but seriously...)
2) Conferences with 20% acceptance rates are, by their nature, a bit depressing -- it's hard to reject so many papers, some of which simply MUST be pretty good.
3) It's easier to argue how a paper is flawed than to argue about how it's making an important contribution.
4) Taking reviewer expertise into account is important, and one outlier can cause problems; sometimes papers live on longer than they should if one reviewer gives too high a score, and sometimes papers are put way lower in the ordered list than they should be because one reviewer gives too low a score. (Of course, one expert reviewer can also bring an otherwise ignored paper back to life.)
5) There are more interesting papers than paper slots.
6) There's generally plenty of down time, when papers you didn't read are being discussed; bring something to work on quietly (but pay attention to what's going on).
7) You really do learn a lot reading 20-30 papers for a conference PC.
8) As you go down the paper list by score rank, eventually (and sooner than you think) you hit a paper that you start to question -- are these scores too high? And as you go up the list from the bottom, you'll hit a paper where you question -- are these scores too low? The rules of randomness tell us that some papers will get comparatively mis-scored in the first round of reviews, so it is good to stop and talk about the papers (and not just take the first X).
9) Hot trends come and go.
10) A steady supply of drinks (mostly caffeinated) and a good lunch can help the PC move happily along.

Thanks to the PC chairs and other members -- I had a good time. But now I'm very tired...

NSDI Program Committee , Part I

I'm spending tomorrow at the NSDI (Networked Systems Design and Implementation) Program Committee meeting. It's been a few years since I've been on the PC for a networking conference, but I've found it so far to be a lot of fun.

First, it's very "civilized" -- I had only 20 papers to read the first round, and then had 5 more for the second round. (The first round was designed to get each paper 3 reviews; the second round was for paper missing reviews, or where the scores suggested another review would be helpful.) That's not too much, compared to most theory conferences.

Second, there are a good number of "algorithmically" oriented papers for me to read. Overall, networking has become a lot more theoretical, which is good. It still seems to me, though, for a network-oriented conference, you have to be careful not to go overboard with the theory. They want results -- backed by theory, preferably -- but at the end of the day, it's the results that matter. As usual when serving on a PC, seeing how it works gives insight into how to frame my own papers.

Third, one thing that's impressed me is how long and detailed the reviews are for this conference. I tend to write shorter reviews, covering what I think the high order points are. (And one thing that has been interesting -- there's generally a lot of agreement on these high order points.) But most reviewers go into a lot more detail -- the average review is at least a good page plus of text. Very different than what I usually find in theory conferences -- although I know there's a push to improve that.

I'm not sure why the culture of networking conferences has led to more detailed reviews. Fewer papers per PC member probably helps; maybe because few papers go on to journal papers (but that's equally true in theory, I think). But it's a marked and interesting change.

Anyhow, now I'm looking forward to SIGCOMM... except that I'll need to be ready to write longer reviews.

Summer internships?

The bad economy already has people thinking about jobs -- it is, I am sure, going to be a challenging year (years?) for people graduating.

I was wondering if there would also be an effect on summer internship programs. Summer interns are often a different budget line item, but it's hard to believe that the Microsoft/Google/Yahoo/everywhere else programs, for both undergraduates and graduates, won't be curtailed in this environment.

I haven't heard anything about summer internships yet, and though it's a bit early, late December/early January is usually when I start get reminders from people to have good students apply for the summer. Can anyone comment (anonymously if needed) if they have any actual information?

Online Advertising and How People Cheat

Ben Edelman (who actually does some theory when he's not doing law and business) gave a great talk today at the Harvard Center for Research on Computation and Society lunch lecture series. It was about Web advertising scams -- how people cheat pay per impression, pay per click, and even pay per conversion schemes, for big bucks. The talk was based on this book chapter (here available as a working paper). (If he gives me a link to the slides, I'll update the post with it.)

One of the scams he gave for pay per conversion schemes is related to this blog. I often encourage people to buy my book on randomized algorithms -- to remind you all, the Amazon link is here. Now, when I put on that Amazon link, I've embedded a link that includes my Amazon Associates information, so if you buy the book, I get a small cut. Very small.** In fact, if you buy anything else after clicking that link, I get a cut -- I actually think this link alone puts a cookie on your system, so if you happen to buy on anything on Amazon for the next week or so, I get a cut. I think I got about $100 in store credit from Amazon last year, from people buying the book off my home page or buying things after hitting an Amazon link on the blog.

So again, I'll encourage you to click that link. (Heck, really, while you're there, just buy the book!)

For me naturally the gain of doing this is small, but apparently, scammers have found a way to make big money off this sort of thing. They have sneaky ways of getting these cookies onto your system -- not just for Amazon, but for other vendors also, multiple vendors at a time -- so if you click one of their links, and then buy things on the Web, they get a cut for "recommending" the purchase to you, even though they've really done nothing of the sort. When you think about it, a 5% cut from the purchases of a million Amazon customers can really add up...

If Ben Edelman happens to be coming to present at a venue near you, I highly recommend you go. And that's not false advertising.

**Actually, not so small. I get almost as much from Amazon as I do from the publisher if you buy the book through the link. Of course, I don't get much from the publisher either.