Classes

Richard Lipton ends a recent blog post with the question:

My question today is how can we better educate students to solve problems, to apply knowledge across boundaries, and in general be better problem solvers? What do you think?

When talking with a visiting prospective graduate student, we discuss the fact that our requirements include taking 10 classes (recently reduced from 12). The student seemed to think that's a very large number of classes to have to take.

I'm a big believer in graduate students taking classes. I'm obviously biased having had to suffer through many requirements as a graduate student at Berkeley. And I freely admit, some of the classes felt like suffering.

But the classes provided me with a strong basis to build on. I found classes good for introducing me to the basics of an area, so that I could understand the problems and communicate with people in that area. Classes also introduced me a much larger group of people, working in a larger variety of areas, than I would have experienced on my own.

And while here I'm certainly talking here about theory people getting to know about things outside of theory (as well as systems people getting to know some theory and AI and other things as well), I think the argument holds as well solely for the increasingly balkanized theory community just knowing about what each other is doing. These days, there seem to be boundaries between different areas of theory that are as high as boundaries between theory and systems. (See, for example, this recent post and comments on "European theory".)

I've heard the arguments against classes. The biggest is that they take time away from research. There are plenty of counter-arguments. (Most students don't really spend 40+ hours a week on research. It's important to train for the long-term future career and not just focus on research. There are important other benefits of classes -- meeting people and being able, if needed, to teach in multiple areas.) Other complaints focus on specific implementations. (Why should I have to take a graduate OS class if I took one as an undergraduate? Fine, let's find something else worthwhile for you to take.)

I think one reason for the trend in reducing or even eliminating class requirements is students generally don't like taking classes, especially in areas not directly related to their research. Why should they? It's work they have to do right now, and the payoff is generally long-term. As educators, we should find ways to make this tradeoff better when possible -- but more importantly, as educators, we have to explain clearly to the students that this type of education really is in their long-term interest.

To my mind, classes (and class requirements) are still a powerful tool for educating students on how to solve problems, including across boundaries. The trend away from classes, which should include both "core knowledge" for computer science as well as opportunities (or even requirements) to explore connections between CS and other fields, does not benefit us.

Thinking Big (Memory)

I gave one of my standard programming assignments this year -- finding minimum spanning trees on big random graphs. It seems for many students this is the first time they've experienced the possibility of not having enough memory using a straightforward implementation; they actually have to think about memory issues.

Year by year I've slowly increased the size of the graphs I require from students. This year, I think I left it too small; some students got away without having to think too hard about the memory issues. I'll have to up it for next year. Part of the problem is that I leave implementation details -- like what language they program in -- up to them. My framework is that I care about them being able to get the results -- I don't care about the details like which language they use. On the other hand, this looseness leads to large variations in how much students have to worry about various things. Java can handle memory issues for you (at the expense of speed); your laptop might exhibit different performance (including whether or not it runs out of memory) than a campus account (which is where the code should eventually be able to run).

One issue that became big this year was students wanting to use Python. I tried to tell them it was a bad idea, but many students like the high-level language and the sleekness of the resulting code. Unfortunately, standard constructs in Python are memory hogs, causing crashes or impossible slowness. Many of the students who started in Python had to eventually rewrite their code in another language -- or failed to deal with graph sizes that the assignment asked for.

I didn't design the programming assignments in my algorithms class to teach students about programming. But I find these exercises really stretch some of their programming skills, making them think about questions (what's the best language to use? what's the bottleneck here -- time or memory? how can I debug/test my code effectively?) that they need to learn to think about sometime, and perhaps aren't dealt with sufficiently in introductory classes any more.

New Cuckoo Hashing Paper

Moni Naor nicely pointed me to a new preprint he has up on de-amortizing cuckoo hashing. (The paper is entitled De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results, by Arbitman, Naor, and Segev.)

The "starting point" of the paper was the technique for de-amortizing cuckoo hashing Adam Kirsch and I suggested in our 2007 Allerton paper, which involved using a content addressable memory as a queue for move operations when doing cuckoo hashing. (See the blog post I wrote way back when here.) Our work was experimental, as we didn't analyze the queueing process, which is based on the number of moves needed when doing an insertion.

Their new paper obtains provable results, showing that there a cuckoo hashing scheme that has constant worst-case insertion time (with high probability over any polynomial number of steps), by utilizing a logarithmic-sized spare space (to queue pending moves, and stash items that can't be placed in the table, a la the Kirsch/Mitzenmacher/Wieder stash technique described here). They even show that only poly-logarithmic independent hash functions suffice, using a new result from Braverman. The only big caveat is that they analyze only the case of 2-choice cuckoo hashing, where the structure of the underlying random graph related to the cuckoo hashing process is better understood. Because of this, the result only allows loads of up to 50%.

It's a very, very nice result with a lot of theoretical pieces to put together. The use of the Braverman result appears to be a general technique for lessening the randomness requirements of these sorts of problems that is interesting in its own right, never mind the useful advance in the theory of cuckoo hashing. I was also excited to see that they used simulations to enhance their theoretical results (for example, providing a conjecture on how small a constant number of moves would be required at each step -- apparently 3 suffices, a quite reasonable number!) and show off how practical the scheme is. Imagine, a theoretical paper with simulations! (Hooray!)

Overall I think the paper is a strong step forward in demonstrating the practical applicability of cuckoo hashing, while at the same time providing strong formal theoretical guarantees. I still believe cuckoo hashing (along with multiple-choice hashing) will become a (the?) standard approach for hashing in the years to come, so of course I'm excited to see results like this. There remain plenty of further open questions -- more than 2 choices? tight bounds on queue sizes? -- so don't worry, there are still interesting things left to do.

Liskov wins Turing Award

Here's the news from MIT.

STOC Registration server up

I'm told you can now register for STOC 2009. Please sign up! (Early date is April 28.)

Other STOC work behind the scenes at this point involves getting the ancillary stuff ready for the publisher (not a particularly pleasant part of the job) -- including the paper schedule. I hope to have a preliminary schedule up next week (or the week after) to help people plan their trips.

A Note to Networking/Systems People

I am sure it sometimes seems on this blog that I'm "critical" of the theory community. I am! Because constructive criticism is, I think, a useful thing.

Today, I unleash some criticism of the networking community. This complaint is based on my own experience with my papers, as well as experience I have on the other side (as a PC member), on how for example data structure papers are thought of when submitted to these communities. Mind you, this criticism isn't universal -- several people seem willing to look at and accept more theoretical papers in these communities. But not everyone...

(Still, keep in mind, I'm taking an extreme point of view here, to make a point, which I understand may inspire some interesting comments.)

When a paper comes in to a systems/networks where the main contribution is a general data structure (in my papers, this has often been a hash table construction) that naturally could apply to various networking problems (e.g., hash tables are commonly used in MANY router-level applications), and the main point of the paper is how to better make these data structures work for these applications (i.e., we consider reducing accesses to slow memory, trying to get it down from say 2 to 1, or consider pin count/hardware parallelization tradeoffs), THIS IS A NETWORKING (OR SYSTEMS) PAPER. I often hear the argument "This is a general data structure, it belongs in a theory conference," and this is just wrong, for multiple reasons.

1) Please don't try to make generality a negative. I know in systems papers you are accustomed to seeing detailed results on a single application (and when a data structure paper also includes that, it can also be a very good thing). But generality itself is a good thing, not a bad thing. (For SIGCOMM this year, one of the review fields is "longevity" -- sometimes these papers aim to have an expected long lifetime, rather than focusing on the short-term impact of a particular application).
2) In the same vein, don't dismiss a paper just because in it's evaluation, it judges the data structure on raw performance (time per insertion/deletion/lookup in a hash table) and/or on simulated data. Yes, I know, by measuring performance at the data structure level instead of the application level we haven't shown this is better on "any particular" application -- but we have tried instead to show it's better for a wide range of present and future applications! (If we haven't demonstrated this effectively, then it makes more sense to reject.) Similarly, in many settings (e.g., hashing), all data is artificial. You may have to pick a good enough hash function for your data to look random (see e.g. Mitzenmacher/Vadhan), but then it doesn't matter what your initial data was.

The first two points can also be summarized the following way: your conference has page limits. We've decided to focus on using the pages available to show off the general, widely encompassing benefits of our approach; don't dismiss us just because we haven't dug into specific implementation details for a particular application (which can take pages to do, and months to program/gather data on, and really doesn't add nearly as much to the paper as what we've put in).

3) This type of work doesn't go to a theory conference: often, in such papers, there is little of "theoretical" interest -- these are engineering papers, not papers with new theoretical techniques or technically challenging theoretical proofs (when we have proofs in this type of paper). Theory people will wonder why we're caring about these details of the hardware/software/data model -- it's only interesting in the context of your applications.
4) Indeed, the point of writing such a paper is that we are looking (or trying to look) precisely at the application and systems issues. This paper is meant for you! In fact, sometimes on the theory side it seems the only way we can get you to notice a new and powerful technique is to write papers for your community, so please try to let us in -- it will speed up adoption of these new, powerful techniques, helping your community overall. (My examples are Bloom filters, d-left hashing, etc.)

One worry seems to be that you'll accept a paper that turns out not to have the payout you'd have expected. That will happen! (By the way, it's also happening with all the other less theoretical papers you're accepting now...) But you need to have a pipeline of these ideas coming in -- who knows where the next basic data structure idea that will have a lot of applications (e.g. a Bloom filter) will come from! I worry you're cutting off your pipeline.

I understand that these papers will face the same high bar that everyone else does to get into say SIGCOMM; that's not my complaint. But in multiple settings I've seen such papers essentially dismissed out of hand, which seems unfortunate. I often hear (and even promote!) the idea that theory people could be working on more practical things. When we do try to meet you halfway, leave the door open a little for us...

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?