Monday, June 30, 2008

Strange Transactions on Information Theory Policies

The journal where I've published the most now is the IEEE Transactions on Information Theory. (Probably because when I write any journal article in information theory, I send it there, while my other work is more scattered.) So I hope it's clear that, as a journal, I hold it in high regard. That being said, they have some strange policies that I just don't understand. (If you're not familiar with the journal and want to check what I'm saying, their submission guidelines are here.)

First and foremost, they have a distinction between "regular papers" and "correspondence". As they briefly make unclear, "a correspondence item will have one point to make briefly and without adornment, whereas a regular paper will be a more well-rounded treatment of a problem area." In the old days, as far as I can tell, this distinction didn't matter much, and roughly the distinction boiled down to length -- for me, long papers were regular papers, shorter papers were correspondence. Perhaps in the IT community there was more prestige for a regular paper, but I've never been aware of it -- at least in my mind citation count would give a better idea of a paper's importance than its nominal type -- and never cared.

This strangeness didn't become important until recently, when to deal with the apparent problem that the Transactions was becoming too big and thereby using too much paper [yes, I know this shouldn't be a problem, but they still send out lots of paper copies], they limited correspondence items to 5 journal pages.

This, to me, is just strange. First, I dislike the idea of page limits in general for journals. The journal is supposed to be the "permanent record" of a scientific result. If it takes 50 pages to present the result, then that's what it takes. A journal certainly has a right (indeed, perhaps a duty) to have authors properly edit a work so that there's not a gross amount of wasted verbiage, but to set a priori page limits, in my mind, goes against the purported purpose of journal publication.

Second, I don't see how this page limit jibes with this (already strange) regular paper/correspondence distinction. Sometimes, presenting a single point briefly takes more than 5 pages. (Arguably, it often takes this long, if one wants to do a suitable job presenting previous work, or substantial mathematical setup must be done.)

As an example, I submitted a paper to ToIT. I thought it was clearly a correspondence, according to their definition, since it really covered a single thematic issue. Given the policy, I wasted at least a day cutting things from my version to make it a (just over) 5 page submission version. (I had tables and a picture -- it really was a hard exercise to cut that last page.)

The reviews came back, and most of the complaints were questions of the form, "Why don't you talk about Z?", where in fact my discussion of Z was something I took out to get things down to 5 pages. (Duh.) The editor asked the editor-in-chief -- no exceptions to the 5 page rule.

So the editor, smartly, decided that I had a 6-page regular paper. While I appreciated the solution, the whole thing just highlighted the silliness of the policy, and perhaps the strangeness in distinguishing "regular papers" and "correspondence" in the first place.

Another policy I object to is their decision not to publish already-published conference articles unless there is "substantially new" material. (This is not spelled out, but I have been told the rough figure is "30% of the article must be new", whatever that means.) Again, in my mind, this goes against the purported purpose of a journal as the final record of a research result. Conference papers are, in my mind, dramatically more likely to be wrong, and at the very least have generally had little feedback in the reviewing process. A journal is supposed to provide more in terms of reviewing; if a conference paper and journal paper ended up identical, I'd have no problem with it -- and I'd congratulate the author on writing such a solid conference version (assuming I didn't question the reviewing practices of the journal).

I can understand this policy in the context of copyright. An IEEE journal can't (re-)publish something another organization has the copyright to, and an author should understand this. But when the paper was in an IEEE conference -- what's the problem?

These two policies interact in a very strange way in the context of the IEEE International Symposium on Information Theory (ISIT) -- the big IT conference. ISIT papers are -- get this -- 5 pages. One might naturally hope that ISIT papers could be turned right over into Transactions correspondences -- and get the benefit of more complete reviewing and editing for that "final version". But not, it seems, under the current policy that the journal version must have something "new" over the conference version. But I can't add anything new to my 5 page conference version without going over that arbitrary 5 page correspondence limit. Am I the only one that sees something wrong with that picture? (And yes, I have ISIT papers that I won't bother submitting to ToIT, because they're really correspondences that should/would be 6-7 pages once I add that 30% new stuff in.) If they're going to not publish things from conferences, even IEEE conferences, then having a 5 page ISIT limit and a 5 page correspondence limit is, in my mind, just strange.

Monday, June 23, 2008

Yet Another Survey... Deletion Codes

Next week I'll be at SWAT for an invited talk. When I gave them a choice of topics, they went with: A Survey of Results for Deletion Channels and Related Synchronization Channels. I've actually given this talk a few other places, but there's been some new stuff, so it's been updated a bit. (I'll put the latest version of the slides up on my talks page after the talk...)

The invitation gave me an excuse to buckle down and finish something I started over a year ago -- a survey article on results for the capacity of the deletion channel (and related problems) to go with the talk. I must be out of practice writing, because it's taken me most of the month to get this thing done. (Well, OK, there was that whole "baby incident" that took up some time, but still, I've clearly been doing far too much administration this last year, and I need to shake off the rust.) It's probably still a bit rough so anyone interested enough to read it, please feel free to mail corrections/suggestions directly.

Apparently, based on some mild teasing from a colleague and friend, I'm known as someone who writes survey articles. (The teasing was perhaps I'm known only as someone who writes survey articles...) I don't know why I end up writing them -- I can't really say it's a fun exercise to write a survey, though it is often educational -- but somehow I feel it's valuable. In this case, there's definitely the motivation that I've done a lot of work in this area, and I want to both promote the area and my work. The survey has a couple of dozen open problems spelled out right there, so let that be motivation for some of you to read it...

Also, I'm open on suggestions on where to publish it. My last few surveys have nicely been able to go to Internet Mathematics (see here for Bloom filters and here for power laws/lognormal distributions-- although the "uncensored" version of the power law survey from my publications page is more fun) so that they've had a worthwhile permanent home. This survey won't quite fit there, and I think it's good for such things to have a visible outlet (besides, say, arxiv). Ostensibly Transactions on Information Theory will take surveys, although I haven't seen that much in practice; and this survey doesn't really fit in the Foundations and Trends model. (I like the Foundations and Trends model, but it seems to me their surveys are like "mini-textbooks" -- and cost accordingly -- while my surveys are more like "here's some background, big ideas, and pointers to papers" -- and I'd like them to be essentially free.)

Wednesday, June 18, 2008

CS Family Values

One aspect of graduate school at Berkeley I recall quite clearly was the lack of children. Graduate students having children was and is generally quite rare, and I'm not sure that CS at Berkeley was much worse in that regard than anywhere else -- I'd be interested if readers have any pointers to stats on the issue, by field and/or by school. But it struck me even then that it seemed unusual for the faculty to have kids, particularly in the theory group.

I know there's the old advice -- still apparently prevalent in some circles -- not to have children until you get tenure. Though that advice seems less widespread these days, or perhaps just more young faculty are choosing to ignore it. (Or, perhaps, I'm just out of touch -- at Harvard, at least, the common case is for CS junior faculty to have kids.) [And apparently I may also be suffering sex bias; see this summary and this pointer to an NSF report, suggesting that the effect on tenure chances for men having children is small, but is much larger for women.]

Does having kids help or hurt one's work? I don't think there's a clear answer, that it probably depends on the individual (and that the effect, in any case, is probably overestimated). On the other hand, I think a career framework that pushes people to postpone or not have children is ultimately cutting off a substantial supply of raw talent, which can't be a good thing. If academia as a whole is moving away from that 20th (19th?) century mindset, I'm all in favor of it.

(An aside -- Chloe Elizabeth Mitzenmacher arrived last week, prompting some of these thoughts. Which, due to lack of sleep, might be even less coherent than average...)

Friday, June 13, 2008

An Improved Analysis for "Why Simple Hash Functions Work"

I recently had a paper with Salil Vahdan (in SODA 2008) explaining why simple hash functions "work" for so many stream-related problems where data is hashed to be placed in a hash table or a Bloom filter or a similar structure. Here "work" means "behave essentially the way you would predict if the hash function was perfectly random." The basic reason, we suggested, was that if the data in the stream had enough randomness, it would combine with the randomness from the choice of hash function to produce value that looked independent and uniform.

Our analysis of how much randomness the data needed to have seemed a little loose. Salil and his student, Kai-Min Chung, have recently improved the analysis; here's the arxiv link, the paper will be appearing in RANDOM '08. There's some really nice and somewhat subtle arguments that I imagine will find some uses in other areas. While it "only" improves the constant factor (in terms of number of bits of randomness needed), this is certainly a case where constant factors are important.

The result further reinforces my belief that this is the right high-order explanation for why, whenever anyone actually does an experiment involving hashing, you get the right results no matter what hash function you use.

Thursday, June 12, 2008

STOC -- Choosing A Program Committee

It took longer than I expected to put together a PC for STOC, and now that it's over, I thought I'd talk about the process.

First, I downloaded the PCs for FOCS/STOC/SODA for the last three years. I wanted to get an idea of what past PCs have looked like, and I wanted the raw data. Generally, I tried to avoid asking people who have served on those committees twice in the past three years. In my mind, it's good to mix things up and get new people involved in the process.

Then I tried to wrap my head around issues of coverage. I know authors are (reasonably) annoyed when they see nobody on the PC in their BROAD AREA X, leaving them wondering if their paper will get a fair read. Despite (indeed, because of) my readily apparent algorithms bias, I wanted to make sure there were a suitable number of people in complexity/cryptography/quantum etc. Even on the algorithms side, I wanted to make sure major areas like data structures, on-line algorithms, approximation algorithms, etc. were reasonably covered as well. It's hard to cover everything, so I'm sure some people will still be disappointed, but I think that overall there is a nice balance in the committee. (We'll see if it's a suitable balance once the papers come in...)

Besides covering areas, there were other balancing issues that came to mind. The "ages" of the PC members was perhaps the next most important. I wanted some fresh faces, since serving on a PC is both good experience for younger members of our community, and a signal to their departments (or bosses, or future bosses) that they are well thought of. But I also wanted some more experienced hands who could possibly head off my mistakes before I made them and provide appropriate judgment where needed.

Additional balances I tried to make: "Practical" people and "pure" theoreticians. Research lab/industry people and academics. (No, that's not the same as the practical/theoretical balance.) US and non-US participants. I did also consider the number of women on the committee. My practice in this situation was not any sort of direct affirmative action, but just to make a conscious effort to make sure that I wasn't overlooking the numerous well-qualified possible female PC members when sending out invites. I look forward to the day when I don't think it's necessary for me (and others) to make this effort, but I personally don't think our field is there yet. For those who are interested in such matters, the STOC 2009 PC is 25% female. In checking back over the PC lists for the last three years, this seems to be more than average for FOCS/STOC/SODA. I admit to being somewhat surprised (and disappointed) by that, and I leave it to commenters to discuss the importance of this issue to our community.

The biggest difficulty I found in getting the PC finalized was getting senior people to sign on. Roughly speaking, the probability of your willingness to serve on a PC seems to decline monotonically with years of experience (with perhaps a significant step-function drop post-tenure). In this case, I don't mean this as a criticism. I know that the people who declined are indeed quite busy with many other things, including larger-scale efforts to benefit and promote the theory community. Or, as one colleague put it to me when I explained the problem I was having, "Duh!" Anyhow, it took a couple of rounds of trials to find, in particular, more senior colleagues, and I thank them especially for their willingness to volunteer, and/or for just giving in to my begging.

[Come to think of it, my own PCing has declined post-tenure, though I'm still averaging at least a couple of larger conferences per year...]

Anyhow, at some point or another, an official call for papers will go up, but I think it's OK to announce the PC (subject to last-minute issues or changes):

Susanne Albers
Andris Ambainis
Nikhil Bansal
Paul Beame
Andrej Bogdanov
Ran Canetti
David Eppstein
Dmitry Gavinsky
Leslie Goldberg
Shafi Goldwasser
Nicole Immorlica
Anna Karlin
Jonathan Katz
Jonathan Kelner
Subhash Khot
Ravi Kumar
Michael Mitzenmacher
Kamesh Munagala
Rasmus Pagh
Anup Rao
Rocco Servedio
Mikkel Thorup
Chris Umans
Lisa Zhang

Tuesday, June 10, 2008

Scientific Citations

A comment over at Lance's blog got me thinking about citations. To summarize, some anonymous commenter said that if a paper wasn't easily available online (specifically, "not available for free online (or through my acm portal subscription)") , they won't read or cite it, and then another commenter pointed out that it was the author's responsibility to acknowledge relevant work, give proper credit, and avoid duplicating previous work.

I certainly agree in spirit with the second comment, but I wonder, exactly, what are our responsibilities as authors? How much hunting, exactly, am I as an author expected to do to find relevant work? This is certainly an issue I've faced in my own work. For example, I've had the case where there may be a related article in an old Russian mathematics journal -- an article pops up in my search of related keywords and either the title or abstract seems potentially relevant, but I can't really tell without getting the article. So far, I've managed -- the blessings of always being near the Berkeley, Stanford, Harvard, or MIT libraries -- but it has sometimes been a non-trivial effort to track it down. In the old days, that library time was more or less expected. What expectations should there be in terms of tracking down old paper copies? What expectations should there be in terms of what an author is required to "spend" to get copies of possibly related work? I do think there is a reasonable argument that can be made that if your paper isn't freely available, an author can't necessarily be expected to cite it.

And of course I wouldn't have even faced the tracking problem except that I try to be diligent in my searches for relevant work. Working across areas, I've often found I have to spend some time guessing and doing some random walks to find out what people in another area call the concept I'm thinking about just to find the relevant papers. How much searching in Google/Google Scholar/your tool of choice should be expected of us? (I'm thinking here of the really annoying reviews I sometimes get of the form, "You should have cited this paper, I'm going to suggest rejecting your paper." That's inane. Perhaps I should have cited the paper, in which case, you should suggest that I cite the paper; that's what reviews are for.)

After all this, there's still the question of what should be cited. Science rules seem much "looser" than what I've seen in literature, history, etc. I'd never think of citing Karp or Garey and Johnson if I was showing a standard NP-completeness result (unless there was a very specific reason to do so) because it's now considered common knowledge. I think in many humanities fields that would be considered improper. Perhaps standards for various fields should be codified -- if only so that people in one field can easily understand the practices in another.

Monday, June 09, 2008

Results of the Hiring Season

I've been eagerly awaiting my chance to talk about the results of this year's hiring season for Harvard Computer Science, but wanted to wait until it seemed all the i's were dotted and t's were crossed. I think we're at that stage.

Because of some losses in Computer Science (including Mike Smith and Barbara Grosz being made Deans, of the Faculty and of Radcliffe, respectively) we were really looking to hire this year. Indeed, I think in the end my most important role as chair of the search committee was to make sure that the right people knew that we really wanted to make a lot of offers, and build support for that. The search committee itself was so great that they made the rest of the job (screening, interviewing, and deciding on candidates) relatively easy. Well, OK, it was actually a lot of work. We had hundreds of folders to go through, we interviewed 14 candidates, and because the candidates were so strong, our decisions were challenging. But the committee itself ran smoothly, with everyone really putting in a lot of effort and working to come to agreement. That's one benefit of a smaller department -- we're very collegial about this stuff.

We ended up making six offers. Given the size of Harvard's computer science faculty, this is indeed a lot, and I'm proud of the fact we were able to make the case to our peers in the School of Engineering and Applied Sciences that making this many offers was entirely appropriate. (We were helped, again, by the high quality of candidates.) In the end, we will have three new faculty members:

Yiling Chen works at the economics/computer science interface.
Stephen Chong works on information security and programming languages.
Krzysztof Gajos works on user interfaces and human-computer interaction.

We're all looking forward to their arrivals.

I, personally, feel very good about the outcome, and am pleased the search was successful. I'm of course disappointed that not everyone we made offers to decided to choose us, but I don't think any school manages 100% there. (Quite frankly, I'm sure the Dean would have been somewhat concerned with the logistics if all six had come, but that would have been a problem I'd have been happy to work through and live with.)

I expect Harvard computer science will be continuing to grow in coming years, so when you know of graduates looking for jobs, make sure Harvard is on their radar.

Friday, June 06, 2008

Is Pure Theory "Wasteful"?

Daniel Lemire has a post on his blog entitled "Why Pure Theory Is Wasteful".

I encourage people from here, if they are so inclined, to comment at his blog...

Wednesday, June 04, 2008

STOC PC -- Software Suggestions?

Well, things are moving forward on the STOC 2009 PC front. I think the committee is just about finalized; more about that in a future post.

The next big question is what software to use for paper submission and reviewing. The last several conferences I've been involved with used easychair, which I view as OK from the PC committee member side of things. Adequate, but not great.

Of course, now I'm viewing things as a PC chair, which feels somewhat different. The first priority is that it makes automated tasks easy, to save me (and the committee) time. The second (although related) priority is that there is some mechanism to easily get the data out -- preferably in some sort of tab-delimited text type way -- so that I can process it as necessary. I'd like this both so I can process information as I see fit, and so I can deal effectively with any emergencies that arise by managing the data myself. The third priority is a reasonable amount of flexibility. Finally, I'd like it easy enough that a minimally trained monkey can use it. I don't know how easychair performs in these respects.

Obviously, I'm asking too much. But I'm eager to take suggestions, both from people who have run conferences and from reviewers who just have software preferences.

Friday, May 30, 2008

More Robust Cuckoo Hashing (ESA paper)

I have a paper at ESA, with Adam Kirsch and Udi Wieder, entitled "More Robust Hashing: Cuckoo Hashing with a Stash." (Here's an extended preprint version.) The starting point of the paper is that cuckoo hashing is wonderful, and everybody should know about it and use it. (If you don't know about it or use it, see here or here. But basically, cuckoo hashing is multiple choice hashing with the added bonus of getting to move items around among their multiple choices as needed to balance load on-line.)

So, of course, we want to make cuckoo hashing even better. And one of the problems of cuckoo hashing is that it "fails" with non-trivial probability. For example, in standard 2-choice cuckoo hashing, putting n items into 2(1+eps)n cells with at most 1 item per cell can be done with probability 1 - Theta(1/n). That gives a Theta(1/n) "failure" rate, which doesn't mean anything in terms of "average" behavior, because it can always be handled by re-hashing everything with a new hash function, so that's the end of the story in most theory papers.

In practice, that kind of failure rate is a bit high. Re-hashing an entire hash table could just be too expensive an operation to have occur that frequently for many applications. Can we improve the failure rate somehow?

Let's look at where that Theta(1/n) failure rate comes from. When there are 2 choices per item, the simplest type of failure one might imagine is that 3 items try to use the same two cells -- that is, 3 items have the same 2 choices of location. Indeed, such a problem occurs with probability Theta(1/n) [exercise LTR]. But when such a problem occurs, we can imagine taking one of those 3 items and stashing it somewhere -- in a stash as suggested by the paper title. The stash should be a little space on the side, that we may have to check whenever we look for something. If we implement a stash, how does the size of the stash affect the failure rate?

If failures were essentially independent, so that each item "fails" independently with probability proportional to 1/n^2, then we'd expect f failed items with probability proportional to O(n^{-f}). This turns out to be the right intuition; 0ur analysis shows that a stash sized for s items (for constant s) reduces the failure rate to O(n^{-s-1}). The analysis is a bit trickier, since of course item failures aren't independent, but the result seems natural.

So a small, constant-sized hash -- easily implementable in software or hardware -- reduces the failure probability dramatically, allowing one to avoid rehashing in practice. What I found particularly interesting from the theory+practice perspective is the power in this setting of a constant-sized stash. It's a very natural addition for practitioners -- I don't think it would cause an engineer to blink -- but I think it really changes the potential for cuckoo hashing, making it a structure you could imagine employing on devices used by millions of customers, without having to worry about this otherwise far-too-common failure mode.

We show similar results for multiple cuckoo hashing variations. (The analysis, unfortunately, is different for all of the variations; it would be nice for someone to develop a cleaner, nicer, more unified analysis of all the varieties of cuckoo hashing.) The case of 2 choices is of non-trivial interest, however, since Udi, along with Moni Naor and Gil Segev, have recently shown that 2-choice cuckoo hashing can be used to develop a very efficient history-independent hash table (check out Udi's web page for the paper). The main problem with such a structure is, naturally, the non-trivial probability of rehashing, which can be avoided using a stash.

The stash idea also fits nicely with my previous paper with Adam on the Power of One Move for cuckoo hashing style schemes, although there the stashes (with suggested implementation as Content Addressable Memories in hardware) were larger than constant-sized. I'm beginning to think the idea of stashes (or CAMs) should be a standard section in practically oriented hashing related papers.

Wednesday, May 21, 2008

The "Conceptual" Debate

I'm not at STOC, but I see the debate about "conceptual" papers appeared again at the business meeting, as it rightly should. It's obviously an area where there's disagreement, in terms of whether there is an actual problem currently, as well as what to do about it. It's something that, as a community, we need to talk and think about.

Rather than engage in debate specifics, let me suggest (yet another) way of thinking about the problem. As a community, we need to think in terms of our field having a regular check-up. Not that we think there's any emergency, but as a community we act like our primary care physician and look at where we are, and make sure that problems that need to be looked into are being looked into.

As part of that check-up, I think it's reasonable to ask if our community has produced a healthy number of good concepts. (This, to me, is the heart of the debate.) At the end of the day, in many important ways (including NSF funding, prestige in comparison with other areas of CS, possibly even job production) the production of concepts is at least one significant way in which we'll be judged. Arguably, it's the most important way; certainly externally to CS, and to large part internally to CS, and even within TCS, people remember and latch onto concepts more than technical details.

I think the vision workshop before STOC played something of this role -- transforming concepts into nuggets for an NSF-style audience -- albeit looking more forward that backward. As a community, though, perhaps we need some metrics to go along with these checkups. We need some goals to let us know if we're being successful, and numbers to let us know if we're achieving those goals.

My bias is that one way to see if we're succeeding in concept production is to consider how much our work is used (measured say by citations) outside of TCS. If we come up with a good concept, often it will show by being spread along outside of our limited community. I know that's just one metric, but it's one I like. We should regularly see how FOCS/STOC conferences are doing in terms of the concepts making their way into other communities, and compare it to other theory conferences, and other conferences in related fields (say, with the International Symposium on Information Theory). We should see which theory papers become highly cited outside TCS and, when they don't appear in FOCS/STOC, we should question why, since FOCS/STOC are supposed to be our premier conferences.

And, personally, I think we need to think of other check-up items we ought to be looking into. (Example: how is hiring going in TCS? How many people are leaving the area after getting their Ph.D.s? Why?) Overall, I think these debates and discussions are quite healthy for the community, and we actually need more of them.

Tuesday, May 20, 2008

Summer Salary Shift

At Harvard (like most US institutions), Harvard pays us a "9-month" salary; we can earn 3 additional months "summer salary" by various means, including grants. For example, you can use NSF grants to pay up to two months summer salary (the 2 months is an NSF limitation -- the 3rd moth would have to come from somewhere else).

When I arrived at Harvard, I found it a little odd that the 9-month salary was distributed over the 12-month year, but the summer salary was all paid over the summer. What this meant is that if you took 3 months summer salary, say, you got paid almost 1/2 (well, 7/16, I think -- consider this a good word problem for your average high-schooler) of your annual salary over the 3-month summer. But I got used to it.

This summer it appears the practice is changing, with summer salary now being set to be distributed over the 12-month financial year. There is some nominal loss (for me and other faculty), in that the money we were going to get paid this summer will now be paid over the 2008-2009 academic year, costing us potential interest. I'm actually also concerned about what havoc this could eventually play with taxes, although with any luck there will be nothing significant. I suppose I'll get used to this as well, but I don't see it as a good thing.

Inside sources have suggested to me that this is part of a move to better keep up with compliance issues for federal grants, inspired by the fact that Yale is apparently currently under an unpleasant government microscope. A quick perusal of Google didn't shed any useful information on Yale's plight, and I'm not exactly sure why the change in practice would make a difference. Anyone with similar stories or insight is welcome to comment...

Wednesday, May 14, 2008

Writing a Final Exam

For me, one of the hardest challenges of teaching is making up homework assignments and final exams. For homework assignments, there's some assistance from the textbooks (and I re-use problems a lot), but final exams are very challenging: coming up with problems that test a student's learning but under a 3 hour time limitation. Making a final exam usually takes me several hours.

For my final exam, usually about 1/2 is True-False, Multiple-Choice, Give-an-Example-or-Counterexample, or Execute-the-Algorithm-on-This-Small-Example type problem. These are very different from the homework assignments, which are usually proof/computation/programming-oriented, and hence have "bigger" problems. The other 1/2 is more like the homework assignments -- proof-type-problems -- but sufficiently easier (or with sufficient hints) that students can hopefully get through them quickly. Interestingly, although you might think the first kinds of problems are easier, on both halves, student averages are about 70%.

I've toyed with the idea of giving take-home finals (which I do sometimes in my graduate classes), but these days it's just too easy for students to cheat. I know I've had students anonymously mail questions around looking for people to answer them. And arguably it's useful to have the final exam test something different than the type of problem-solving that they do on the homework.

When I think of the time spent making a final, I know I'd be happier not to give one. And of course the students would be happier too. Not better off, I think, but happier. Perhaps there's a different solution....

Monday, May 12, 2008

A Bubblesearch (Semi-)Success Story

A colleague was backing up files to DVDs and wanted to know a good bin-packing heuristic. I pointed him to First-Fit-Decreasing and Best-Fit-Decreasing, nicely described the Wikipedia entry on bin-packing, but suggested as long as he was doing that he ought to try Bubblesearch as well. Recall Bubblesearch just tries random perturbations of the greedy ordering, to try to find a better solution; the full description is in this paper.

His reported results are that with FFD everything fit into 5 DVDs, which was the minimum necessary; but he did find that Bubblesearch improved the utilization of the first 4 DVDs from 94% to 99% (with about 10,000 random perturbations, and some small parameter tuning), which he thought was impressive.

Your mileage my vary, and I'm sure there are better specific heuristics for bin-packing. The point behind Bubblesearch is that it is a natural extension for a wide class of Greedy heuristics, and moreover is really easy to understand and to implement. My completely self-interested and biased opinion is that it (or something like it) should be taught in all undergraduate algorithms classes....

Friday, May 09, 2008

Stopover at Google Boston

I gave a talk over at Google Boston yesterday, which is now actually located in Cambridge, in the building above the Kendall Square Legal Seafood [5 Cambridge Center]. It's new digs -- they've pretty much just moved in -- and the place had the look of still being put all together, in terms of decorations and all. It did look like a typical Google building -- very open cubicles, lots of conference rooms of various sizes, a game room, a lounge, a colorful cafeteria, etc. I talked about the Hiring Problem; they were going to record my talk and put it on YouTube, but nobody checked the camera battery before the talk, and it and the backup weren't charged. So I get to avoid for another day the issue of having my talks on YouTube. (The good: anyone can see your talk; the bad: anyone can see your talk.)

Although there's not "research" there per se, they're trying to build up a connection to Harvard, having speakers from EECS and other disciplines (economics, law, etc.) come by and give talks. I'm hoping they'll eventually put some research people there; it would be a nice addition to the soon-to-open Microsoft Cambridge lab. [Note to Big Tech companies -- research labs or lablets in Cambridge/the Boston area should be a no-brainer. If you want access to good students early in their careers, there are lots of good students around here...]

Wednesday, May 07, 2008

Suresh Venkatasubramanian and the "Foundations" Book

Suresh Venkatasubramanian of the famed Geomblog has offered to co-manage this Future of CS: Foundations book project with me, so we hopefully will get more chapters soon. Our goal is to arm-twist a half dozen or so people over the summer, and then once people see it get started, maybe more will join. At least, now I have a good excuse to arm-twist Suresh!

I've had some people e-mail me with interest -- I'm very enthused, and I'm hoping you'll all follow through! (And if you haven't yet, please e-mail us with interest.) I think the key rules, again, to remember are that it should be written for smart high school sophomores, and that each chapter should include a "glimpse into the future", which I think of as a description of a specific, big, open problem that one hopes might be solved in about the next 10 years.

It also, I think, helps to think of right-sized "nuggets" for such chapters. (Although I'm open to more experimental approaches, a la Chazelle.) One person suggested they'd write a chapter on universal hashing, which I think is a great idea. Trying to cover all of hashing seems too big. But explaining the basics of hashing, and then the specific role of universal hashing and why it's interesting, seems just right.



Wednesday, April 30, 2008

STOC 2009 : "Impending Doom"

Another surprise announcement: I was asked to be the PC chair for STOC 2009, and I accepted.

I have to admit, I was surprised to be asked, as I am, after all, somewhat vocal in my opinions, which are not always popular. (I was going to label myself a crank, with examples, here, here, here, and here, before someone else did, but I prefer "vocal".) Once asked, I found it hard to decline, despite the warnings that the job is a lot of work (and arguably little reward). It is an honor to be asked, I do believe in service for the community, and, most importantly, I felt it might lead to interesting fodder for the blog. (Obviously nothing confidential will be discussed, but the challenges of the process -- an inside view -- might be interesting.) It was something I was hopefully going to do once in my life. And (as Cynthia Dwork nicely pointed out to me, when I asked her about the job), I'm only getting older, and will have less energy.

Some people might be worried, given my noted worldview, that I might set out to change things drastically. I was thinking it would make a great joke to take "competitive analysis" off the list of topics of the call for papers, only to find it wasn't actually there. Rest assured that things will probably change incrementally; I respect the traditions, and I view the main part of this job to be selecting and empowering a solid, talented PC to do their best job.

The one change I'd really like to implement, so much so that I have to let people object already, is to introduce the rating system that conferences like SIGCOMM use:

5: top 5%
4: top 10%, not top 5%
3: top 25%, not top 10%
2: top 50%, not top 25
1: bottom 50%

I like this approach much better than trying to guess what everyone thinks a 7 means, or differentiating between a 6.3 and a 6.6. (Though, depending on the projected acceptance ratio, I could see changing the numbers a bit -- to top 10%, 10-20%, 20-33%.) I think this approach makes it easier to concentrate attention on controversial papers that need attention.

Tuesday, April 29, 2008

Barbara Grosz now Dean of Radcliffe

Barbara Grosz was officially appointed dean of the Radcliffe Institute for Advanced Study. Barbara had previously been the dean of science for Radcliffe and took over as Interim Dean of the Institute when Drew Faust was made President of Harvard.

For those who don't know Barbara, she's known for her work in AI, and has been a professor at Harvard since 1986. I took her class and TA'ed for her as an undergraduate. I'm excited this has been made official, because I was getting tired of using the word "interim" whenever discussing Barbara's status.

Harvard computer science continues its tradition of being quite "outgoing". Harry Lewis was Dean of Harvard College, Mike Smith is currently Dean of the Faculty of Arts and Sciences, and now Barbara Grosz is Dean of Radcliffe. Per capita, we're well above average in Dean-ness. The joke around the department is once you get tenure you have to watch your back, or someone might make you Dean of something....

Friday, April 25, 2008

Book Management

Talking about a "group-book" is a lot of fun. Actually putting one together, maybe less fun.

I like to think this project will be self-promoting, if it just gets started. A few people write their chapters. I put them online, blog about them, maybe push others to blog about them, a few more people think that's a good idea and look people are actually doing it, a few more chapters come in, and so on. Soon we have 20 or so chapters, and we think an actual book. (Maybe soon after that it catches on so well we get 40 chapters, and we make an omnibus.) To me, though, the hard part is getting started.

We need some rules of management, and if I'm currently the editor assigned to your paper for say SICOMP, you might now that management is not always my strong suit. (In self-defense, I'll say it depends on the situation. Corralling referees is not my best skill. And probably not corralling authors, leading to the failure the first time around.) So here, I'm happy to take advice. Send advice! Indeed, I've had a prod or two from people who'd be interested in co-managing/editing this project, so it won't be just me-- which is great!

I'll eventually work it out with co-editor(s), but here's my rough thoughts -- totally open to change.

1. We'll send annoying e-mail to people who we might like to write chapters. (Those who were on the old list, you're not off the list.)
2. People who want to write chapters can pick (and send me) a topic, so we don't get many people writing on the same topic.
3. Authors can make their participation public, so their name and a working title goes on the Web site, or private, so they can back out.
4. There has to be some notion of deadlines -- if you say you're going to write a chapter, after time x, you have to back out (and someone else might take the topic), or show significant progress.
5. I'd hope that several people might take time over the summer to write chapters, and then maybe some others over the fall, and so on. So if you think you can spare cycles over the summer to put a draft together, let me know!

Thursday, April 24, 2008

Writing a Chapter, and Answering Some Questions

Yesterday, I posted the chapter I had drafted on codes for the hoped for book on CS aimed at high school sophomores. (You'll also note I now have a link to Bernard Chazelle's marvelous essay, The Algorithm: Idiom of Modern Science. Bernard agreed to "donate" this essay to this book projects two years ago, and has again given permission for its use.) I just wanted to clarify, the chapter did not take long to write. There was some background time in thinking about what I wanted to present, and time for looking a few things up. The actual writing, though, took something like 3 half-days during the summer, and that includes pictures. While your mileage may vary, I don't think this project should be a time sink for anyone. I'd like to think that if you made it a priority, it could be done fairly quickly.

The chapter was designed to cover what I think are important features:
  1. A simple introduction, based on (hopefully) easy-to-follow examples.
  2. An explanation of why this is important in "the real world".
  3. Important past results, that are known and understood. (Here, Reed-Solomon codes and LDPC codes.)
  4. A goal for the future. (In this case, network codes, and figuring out how they might actually be used in networks.)
  5. Links/pointers to relevant references.
I don't think the chapter is perfect. (Feel free to send me suggestions.) But I do think this chapter is good. And that is a key point that answers many of the questions I receive about this project, about why I choose to do things one way or another. Right now, there really isn't a book/resource like what I think I have in mind. I'd rather have something that's good up in a year, rather than aim for something perfect that will take forever. "The perfect is the enemy of the good" applies here in my mind.

Other questions:

1) Why not do it in a wiki?

Answer: I've explained some in comments-- I don't think a wiki is appropriate for a "creative writing" exercise. Also, I'd like some actual commitment from authors, and I'd like them to get credit for their work. (If this all works out, you can put this on your next NSF grant application as your broad educational service.)

2) Why focus on "theory"?

Answer: It's that perfect/good thing. I'd like something coherent, that I'm qualified to manage, that can be done in a reasonable time frame. That means some focus, and I'm choosing to focus on theory. (And theory, in my mind, needs the PR.)

If this works out, we can expand to other volumes. Heck, I'll manage/edit volume 2, communications and networking. Then I'll hand it off to someone else.

3) Who do you want to volunteer?

Answer: I'll be honest -- I have a very strong preference for Ph.D.'s (over graduate students), and I'd generally prefer "name" professors/research scientists -- we need at least some of those, so we can start developing some of that cult of personality in our field, and so the book will carry some weight with publishers and other outsiders. But I'd be open to any and all good ideas.

4) Timeline?

Answer: Well, I'll talk about "management" more next post. But I'd hope that a dozen or so people could be convinced to take some time over the summer -- maybe a week or so -- and write up a chapter draft. But since last time that sort of schedule seemed too optimistic, I'd be thrilled to get chapters by the end of the year....
Next post: ideas on management?

Wednesday, April 23, 2008

The TheoryCS Book

I'm glad to see interest of various kinds in the Book on Computer Science (I really need to come up with a catchy name) I talked about last post. And yes, as many of you correctly interpreted, I'm looking for volunteers!

To flesh the idea out for you, here is (with some small updating) the original proposal I sent out for what I had in mind. For those who don't like clicking, here are what I wrote as the main rules:
  1. The intended audience you should have in mind when writing a chapter is smart high school sophomores. I see this as the most important rule. The goal is a book (or, more concretely, a collection of chapters) the general populace can pick up and read, to learn about computer science and why it is interesting. We want to hear people say: I decided to try computer science because of this book.

    This rule has some corollaries. First, fewer equations, more pictures. Second, lots of examples. Third, simple language. I do not mean to suggest that we talk down to the audience, or assume that they are mathematically ignorant, but that we assume as little as possible, and try to reach the broadest audience.

  2. Each chapter should explain something already known and understood, and why it is significant.
  3. Each chapter should explain a specific, but big, open problem that one hopes might be solved in the next 10-20 years, but probably not before that.
  4. Each chapter should be roughly 15 book pages. If we can have 20 chapters, that will be about 300 pages, which is plenty. That's a guideline; I expect some variance.
  5. Each chapter should include at least 3 easily available references for more information.
I've had many people tell me they think this type of writing is hard -- that is, writing for a general, non-research audience -- and I understand that. This task won't be for everyone. But if, as a field, we can't articulate to a general audience what we do and why it's interesting -- and in particular, if we can't provide some idea of where we hope we'll be in specific subareas a decade or so from now -- well, then I think we're in big trouble in the big landscape of science. I'm sure we can do it. I also think we haven't really tried hard enough to do it in the past, which explains things like our current NSF budget.

If you're wondering what such a chapter might look like, I have my chapter from back in 2006 available. (It's on coding, naturally.) I'll talk more about this chapter, and how much work a chapter is, next post.

Tuesday, April 22, 2008

Failure, and a Second Try

About two years ago, I went through a huge failure on a project. In the back of my mind, I always wanted to use this blog as a jumping off point for a second chance for this project. Now is the time. Perhaps some of you can help me fix this failure.

Back in early 2006, while I was on what's now known as the SIGACT Committee for the Advancement of Theoretical Computer Science, I was thinking about ways to promote theoretical computer science (TCS). One idea that struck me is that most people entering college from high school know nothing about TCS. If they've had exposure to computer science, it has been programming. Compared to the excitement of biology (we're figuring out the building blocks of life!) or physics (we're figuring out the building blocks of the universe!), computer science must seem to the average high school student to be, scientifcally speaking, a wasteland.

Now, we know this isn't true. Those of us in TCS wouldn't be in it unless we thought there were fantastic, mind-bending, potentially world-changing problems in the field. And I think history is on our side; computer science, and in particular TCS, has changed the world, fundamentally, and continues to do so. I don't think, though, we do a good job of promotion, showing the world, and in particular high school students who we might hope to attract to our field, the excitement of TCS. Somehow, our field still attracts talent, but it's an uphill battle. If we could change that, I thought, we could change the perception of our field, attracting top students earlier, and long-term creating a greater appreciation of TCS in computer science and across the sciences.

So in 2006, I dreamed up a project. I wanted a book that could be handed to high-school sophomores, to give them an idea of what TCS is all about. I wanted a book I could give to friends' kids -- heck, to my own kids, when they got to the right age (and wanted to really know what Dad did with his time). I wanted a book that would be interesting, engaging, and cover the wide swathe of work we do.

So, naturally, I knew I couldn't write this myself.

Instead, I wanted a group-book, with experts writing chapters in their areas of expertise. I reached out to about 40 or so people in the TCS community, asking them to write a chapter. I hoped first drafts could be done over summer 2006. And that by the end of the year, we might have a book ready for a publisher. About 1/2 the people agreed, and I sent occasional e-mails reminding and encouraging people.

And nothing happened. I think lots of people started, but never finished, their chapters. I heard a lot about how it was difficult to write chapters for the target audience, high school sophomores. It seemed for everyone that other projects, other papers, other things took priority. Disheartened, and busy myself, I let it go.

I still thought the project was a good idea. I still think so. So now, over the next couple of weeks, I'm going to revive the project here on the blog. I hope to change the nature of the project a bit, so my initial management failure won't necessarily repeat itself. It's something I've wanted to do since I started the blog, but I've kept putting it off.

I think it's time to try again. More to follow.

Monday, April 21, 2008

Books from my Shelf, Part 3

Today, let's look at some more practical books from the shelf.

Network Algorithmics, George Varghese: Even before he wrote this book, George Varghese had essentially written the book on how to get good performance on your network devices (e.g., routers) by smartly using algorithms combined with systems thinking. George is my role model in this area, even moreso now that I've worked with him on a few projects. If you want to see how network people are thinking about and using algorithms for packet classification, prefix-lookups, switching, scheduling, security, and so on, pick up this book.

Mining the Web, Soumen Chakrabarti: Sigh. Has it really been over ten years (no need to get more specific than that!) since Soumen and I were graduate students at Berkeley together? Soumen's one of those people who could have been a great theoretician, but was always lured by that "real world" thing, and instead became an expert on information retrieval and the web, which lets him still do theory now and again but with an eye toward problems of more immediate importance. A great book for everything you might want to know to start building your own search engine. Web crawling, information retrieval, clustering and classification, etc. And lots of algorithms and algorithmic insights.

TCP/IP Illustrated, Volumes 1 + 2, Stevens and Wright: At some point, I was looking at TCP for research purposes, and this was a great book for understanding the fine details. It may take a little looking, but the details are in there. Volume 1 also provides background on a lot of basics that I think are useful for networking research. Finally, I also think it would be useful for theorists to look over this book at some point is to get some insight into real-world systems-thinking.

Sunday, April 20, 2008

DF Splash

I haven't had any official connection to Digital Fountain for some time, but I do still (I think) own an epsilon fraction of stock, so I check in the website every now and again to see what they're up to.

They have a web site for a beta/demo for their new "TV-Quality Streaming Video CDN" product, DF Splash. If any one or ones would care to review it -- in the comments, or as a guest post -- let me know. I'm curious what people think. I'd review it, but I'm swamped (CDI proposal due!), and I'd actually rather hear what other people think, if anyone is willing.

I watch far, far too much TV. I've been pretty unimpressed generally with the TV on the Internet experience -- I haven't gotten into YouTube -- but I have been enjoying www.hulu.com. I'm trying to use it to catch stray episodes I've missed on shows I watch (or watched) regularly -- instead of, say, staying up late hours to have my own mini-marathons of Bewitched.

Wednesday, April 16, 2008

Taxes and Algorithms

I'll continue with my walk through my bookshelf shortly, but as tax day just came and went, a thought or two on taxes, with an algorithmic bent...

Ideally, the computation of taxes is a (relatively simple) algorithm. Ostensibly, there should be a set of numbers one gives as inputs, and then an output-- the amount of tax you owe or are owed -- is produced. This is the basis for tax software programs -- you plug in the numbers, and off you go.

In real life, things are much worse. The required inputs are, at best, vaguely defined -- leading to such fun questions as when I make a charitable deduction by buying a ticket to a charity dinner, how much am I not allowed to deduct because of the value of the dinner -- and subject to interpretation. In computer-speak, garbage in, garbage out. I'm amused by reports like the one where Money magazine sends the same information to 50 tax professionals and ends up with 50 different tax returns (and a large spread in what is owed), or reports that in tests of IRS call-in helplines that the wrong answer is given over a third of the time. And when exceptions or odd cases occur, as they do often with the way the tax code is set up (AMT, anyone?), things rapidly become incomprehensible.

Naturally, I think there are lessons here. I actually find many tax forms are simple to understand, when I understand what the end goal and result is supposed to be. That is, it's much easier to understand an algorithm when one understands the goal of the algorithm, and there's some natural connection on how the steps of the algorithm are getting you to that goal. The problem with many tax forms is that they give the steps of the process without clarifying the goal, so I can't tell if my situation is a standard case or a special case that requires more time and attention. When theorists explain algorithms to outsiders, we ought to keep in mind that they might not understand special cases or detours in the argument that seem natural to us. We should keep the end goal clear throughout our explanation. And I admit I'd be thrilled if the US moved toward a tax system that was algorithmically speaking comprehensible (at least to me).

Another way of viewing this lesson is that there are (or should be) significant differences between algorithms designed for a computer to use, and algorithms designed for a human to use (with or without the help of computers). Humans, for instance, often like to understand the output produced, for their own satisfaction or so they can explain it to others. Computers don't care. In my past foray into human-guided search systems, this was one of the lessons I learned. In theory, we often think of an algorithm as a set of instructions transforming an input to an output. Sticking too closely to that worldview can be quite limiting; algorithms can be objects that humans -- or other agents -- interact with, leading to different design goals than we commonly consider. Even if you could just plug numbers into a computer and have your tax bill pop out, I think many people (myself included) would be unhappy, if we didn't have some understanding of how that final number was derived.

Tuesday, April 15, 2008

Books from my Shelf, Part 2

Continuing a list of some interesting books...

Reversibility and Stochastic Networks, Frank Kelly: This was the book that got me interested in queueing theory style mathematics -- well, really it was a course I took from Frank Kelly, based on the book, and Frank then gave me a copy. The book is out of print, but nicely available online from the link. It's all about Markov chains, queues, queueing networks, and various applications. While I'm sure there are more "modern" treatments, I think the book holds up quite nicely.

Queueing Systems (Volume 1, Theory), Leonard Kleinrock: Another classic with all the basics of queueing theory, including all the fundamental results of all the basic types of queues. (While Volume 2, on Computer Applications, is also interesting, I think Volume 1 is much more useful.)

A First Course in Stochastic Processes, Karlin and Taylor: OK, another classic probability book. (Yes, there's still more of them to come.) Markov chains, renewal theory, Brownian motion, branching processes, etc. (While the Second Course, with more advanced material, is also interesting and useful, I think the first book is much more important.)

Introduction to Probability Theory and Its Applications (vols 1 and 2), Feller. Again with the classics. The classics are apparently classics for a reason, at least in my mind...

Monday, April 14, 2008

Books from my Shelf, Part 1

Commenters have told me they want some book recommendations, so here I go... since there's a number of books, I'll be breaking this post up.

But first, a caveat, I'm not a big collector of academic books. I was spoiled by Berkeley's libraries as a graduate student, and am spoiled by Harvard and MIT's libraries now. But here are some of the books on my shelf that I find useful (besides, of course, the obvious Mitzenmacher and Upfal, which everyone must have on their shelf). Some are useful for theory, some for practice, some for... well, hopefully the descriptions will give some idea. In no particular order, here are the first 5, with more to come...

Handbook of Algorithms and Data Structures, Gonnet and Baeza-Yates: Apparently out of print, but well worth getting used. This is the state of the art in hashing, search algorithms, sorting algorithms, priority queues, text search, etc. as of 1990. And one of the best sources if you need to look up, say, the formulas for the expectation and variance for the number of accesses required under linear probing hashing to insert the (n+1)st element into a table, or pretty much anything else in that vein. Chock-full of formulas and references, this is my go-to book for looking up the basics. Someone should write an updated version of this classic.

Elements of Information Theory
, Cover and Thomas: This book is the classic standard introductory text for information theory. And it's just a darn fine book, well written and covering all the basics so you could, for example, skim it over and then go to information theory conferences and act as though you sort of belong.

Modern Coding Theory, Richardson and Urbanke: OK, it's not yet on my shelf, I still have to get a copy. This book is for everything you've wanted to know about low-density parity-check codes by two of the leading experts in the field. I'm not sure I'd recommend it generally to everyone, but I would to everyone interested in coding theory in general (and LDPC's in particular).

Information Theory, Inference, and Learning Algorithms, David MacKay: This book, which I've enjoyed since it came out, now lies somewhat interestingly between the above two information theory books. It's a bit more basic and broad, covering fundamentals of compression, coding, and Bayesian inference, while also covering topics like LDPC codes and neural networks. The book is a bit idiosyncratic, and naturally, since I enjoy David's work, I enjoy the book.

Complex Graphs and Networks, Chung and Lu: I like having this book around so I can pull up Chapter 2 for reference -- all about tail bounds, with an emphasis on variants of martingale bounds (Azuma's inequality) that cover more obscure situations that arise and are hard to find easily elsewhere.

Thursday, April 10, 2008

Things I Can't Talk About

If you're a regular reader, you've probably noticed that I haven't been posting as much as usual lately. Unfortunately, that's because I've been spending too much time on things I can't talk about.

Specifically, for much of the last two weeks, I was at a trial in San Francisco as an expert witness. Luckily, one week of it was during Harvard's spring break, so I didn't miss too much class time. But the case naturally took almost all of my energy and work hours. Not only did I not have much time to blog, but I didn't even have much time to think about things to blog about. Hopefully, that will change, and I'll soon be back to my usual self.

A natural topic to blog about, of course, would be about what it was like being an expert witness. Such a topic fits within the scope of the blog. But the case is just still too close. Instead of talking in generalities, which I think is reasonable and still professional, I'd run the risk of discussing specifics, of either the case, the client, or the attorneys I worked with -- which I definitely think is not, especially in a blog context.

As I pondered this dilemma, it occurred to me that there are plenty of other things still within the realm of professional life that I can't (or, to be clear, I choose not to) talk about. Details of PC meetings is not suitable blog material, as are details of the meetings of our CS faculty search committee -- and pretty much the last few weeks, when I wasn't busy with the case, I was busy with the ICALP PC or the CS search! Nor are discussions of my work on the "Administrative Board", Harvard's rule-enforcing body, for which every case is meant to be entirely confidential. Heck, we aren't even supposed to talk about what NSF panel we serve on when we serve on NSF panels, which I find a bit extreme. (Who couldn't figure that out if they wanted to?)

It is frustrating, since part of the reason I started to blog was because I like to talk about things. But especially because a blog is a public, permanent record, there are interesting, worthwhile, and even entertaining topics... that I can't discuss.

Wednesday, April 09, 2008

The ICALP crossover game

For those who like this sort of trivia -- is there anyone who has had papers in ICALP tracks A,B, and C? (Different years are permissible.) Who has had papers in two of the three tracks?

Track B, being far out of my usual scope, seems hardest to get to me.

Tuesday, April 08, 2008

ICALP A list of papers up

The list of papers for ICALP (Track A) is now up.

This was a hard PC to be on -- lots of papers, and in fact lots of good papers, made it especially hard to draw the somewhat arbitrary dividing line. Congratulations to those who had papers accepted, and for the many that didn't, be aware that the decisions were very, very difficult to make.

Tuesday, April 01, 2008

Jennifer Rexford's take on "Practical Theory"

Jennifer Rexford, who I've mentioned before is a networking person who appreciates theory, gave me a rumor that she'll be giving a talk at STOC on "networking questions relevant to the theoretical CS community." I don't see the program up yet, but I hope it's true. She's a great speaker, with excellent perspective. Kudos to those who thought to invite her!!!

She also pointed me to an editorial she wrote on her ten favorite "practical theory" papers. Naturally, I enjoyed reading her perspective. Particularly since her perspective included my name (flattery, indeed, will you get you everywhere-- or at least on my blog).

I think, however, her editorial offers several lessons. Here's my top two. First, her notion of a theory paper is a little different than ours. Most of the papers are by networking people who think mathematically and theoretically (Varghese, Towsley) or more attuned to what I think of as EE theory. This first lesson is a reaffirmation of my long-standing notion that the FOCS/STOC view of theory is, in many respects, rather limited, especially to our peers outside of theory. I think a second related lesson goes to the importance of theory people getting out there and making their work more accessible to non-theorists. In my case, that has meant writing survey articles, giving talks for general audiences and not just theorists, and going to networking conferences to talk about my work. I'm sure there's plenty of other "mainstream theory" work that Jennifer and others from networking would greatly appreciate -- if only we as a community did a bit better job of letting them know about it.

Sunday, March 30, 2008

SPAA 2008 Accepted Papers Up

SPAA 2008 list of accepted papers is up. (I was on the PC... standard rules apply, I take credit if you like the program, but pass the blame on to others if you don't.)

Still in the throes of the ICALP PC process...

Thursday, March 27, 2008

Security, and Class Projects

As I was reading Freedom to Tinker, catching up on the latest reports of flawed voting machines, I remembered my favorite class project of all time.

My first year teaching Algorithms at the End of the Wire, I included a subunit on cryptography/security. (This was before Salil Vadhan arrived, and before Michael Rabin started regularly teaching a crypto course.) One group, for their final class project, decided to explore the potential security flaws in the Crimson Cash system, the local system where students put money on their ID. They got a card reader and figured out how to intercept and spoof messages from the vending machines in the Maxwell-Dworkin lobby. It was a standard man-in-the-middle attack -- you intercept the message from the vending machine so your account doesn't get debited, and tell the vending machine the message went through. For their demo, they showed how they could get a free soda. They got to learn about security by breaking an actual system (which, by the way, in retrospect was something of a bad idea -- next time students try to break system security, I'll make sure they do it in a closed, lab-type setting).

It was great stuff. All CS majors should do some sort of a-little-bit-out-there, hands-on project like that. And then, maybe, we'd have better voting machines.

Wednesday, March 26, 2008

Knowing Harry Lewis Can Get You Hired

For that epsilon-fraction of the world that regularly reads my blog but not the complexity blog, here's a great post about the awe-inspiring power of just knowing Professor Harry Lewis. Check out the comments (I think Harry is teasing me again). And for anyone skeptical that Harvard is a high-powered CS institution, just check out Harry's list of his past Teaching Assistants (TFs, in Harvard-speak), and see how many names you recognize...

Friday, March 21, 2008

CS 124 and xkcd

A few of my students in CS 124 (Algorithms and Data Structures) pointed me to this xkcd cartoon -- amused, no doubt, that we had covered the O(2^n n^2) algorithms in class about a week ago. And who says that you don't learn anything important in my class!

David Eppstein was inspired to write a longer blog post on the algorithm, well worth reading (especially if you're in my class!).

Saturday, March 15, 2008

Error-Correction Mechanisms for Publications

I very much like the conference-based publication system of computer science. But an obvious problem with the system -- which mathematicians sometimes throw back in the face of CS theory researchers -- is that this system leads to buggy results getting published and accepted by the community. (In my last post, I talked about the headaches this issue can cause PC members.)

This problem could be ameliorated if as a community we had some standard ways of reporting or dealing with such errors. But I don't think we really do. Occasionally an author will self-report an error or fix something for a journal version, but I imagine errors slip through more often than we'd care to think about. Perhaps it isn't really a problem; for big, important papers, bugs will be found and knowledge of them disseminated. But for smaller papers (which, let's face it, is most of what actually gets written -- even in the major conferences), there doesn't seem to be a process -- in fact, even trying to suggest that there's a bug in someone's work can get your own paper killed.

Yes, I'm unhappy to report, this happened to me. Once, on a paper, a student found a bug in some previous related work, and thought it important to mention in the conference submission to deal with possible questions about how our work related to this other paper. [Since he's job-hunting, I feel I should say this was NOT Adam.] After going back and forth, I agreed that we could in a footnote mention that there appeared to be an error that we were discussing with the author. (The author took a while to admit there was an error, and in fact the student helped suggest a fix.) The PC sent back nasty reviews, with one even suggesting that our action was unprofessional. I, obviously, disagree. This was a submission, ostensibly confidential, not for publication (the PC could ask us to remove the footnote if they objected). We were in contact with the author and trying to clarify and fix the bug we found. How the heck else were we supposed to let the committee know what was going on, if they felt it important? If they felt it wasn't important, it was just a footnote they were welcome to skip.

This attitude, I think, stems from the fact that, on the whole, we're a very pleasant, non-confrontational area of science. Fights in CS theory are rare; most people get along (professionally) quite well. From what I've seen, with rare exception, we're much less confrontational than other sciences. So somehow mentioning out loud that someone might have made a mistake is not considered good form. Again, I may be wrong, but other sciences seem less sanguine.

Of course, the underlying problem in this incident, and others I've seen as a PC member and in other contexts, is that we don't have an error-correction mechanism that allows one to report bugs or suspected bugs in published work. Perhaps we're better off without it -- maybe it would just take up time and provide little value. But I've never heard it even come up as an issue to be thought about and discussed by the community. Perhaps it should.

Thursday, March 13, 2008

Conferences and Correctness

A post by Mihai Patrascu brought up the difficult issue of how to deal with papers that may or may not be correct when on a program committee. This is, clearly, a difficult question, and can lead to tremendous difficulties, as it is often not a simple task to determine correctness.

One approach is when an issue arises to inform the author(s) and ask them to clear up the issue. I recommend this, but it is not always functional; there may be disagreements between the author and the reviewers, and there is usually a limited amount of time to settle the problem.

Also, this seems to set up an onus on the author that may be unfair: you must convince us (outside what you've already written) that your proofs are correct. Now, that might not sound like an unfair onus, but for a difficult proof it may be very challenging, particularly since initially all that's been asked for (in most conferences) is a 10 page abstract and not the "final" version. Moreover, it's unfair because it's not something you're really asking of all the other authors. Sure, nominally you are, but papers with bugs get through often enough. Sometimes we make mistakes, and arguably there is some unfairness in a policy that insists that suspicious paper X must now be proven until all reviewers are fully satisfied while papers that didn't raise suspicions pass right on through.

As I've mentioned, I think the main job of the PC is to prioritize what papers get in a conference, and a secondary job is to give feedback to the authors. As part of that job, naturally, we want to throw out papers that are wrong and let the authors know about mistakes. But my argument is that conferences (and PCs) are not designed to accurately tell if papers are completely correct. If they were, I wouldn't have 45 papers to consider in a bit over a month, and I wouldn't be given papers on topics like quantum computing to judge. Ensuring correctness is nominally what journals are for, and that's why (in general) journal articles can take more time to review, and why one seeks experts for reviewing.

I'm not sure what a good solution is, and I'm not advocating blindly giving benefit of the doubt to papers that appear wrong. But there should be a high-level understanding that the conference procedure is inherently noisy. Mistaken proofs might be published. Perhaps the problem we should turn our attention to is how, as a community, we handle these errors, including arranging for such errors to be corrected or noted (by the authors or otherwise) in an appropriate fashion.

Thursday, March 06, 2008

What is the Purpose of Program Committees?

The subject of Program Committees and conferences seems to be a timely one; besides my recent posts, here an interesting post on the theme by Mihai Patrascu, and some counter-thoughts by Daniel Lemire. Here's some more thoughts.

It's actually important that, as a community, we have a good and relatively consistent story about what conferences are for, for many reasons. Funding of conferences, certainly. So students know the rules of the game coming in. So we all know how publications in conferences should, or should not, affect hiring decisions.

As a practical matter, it is also useful to have a reasonably consistent story for specific conferences about what their goals are so that the Program Committees can perform its function appropriately. A reasonable question is why have PCs at all? Many other fields don't.

When I'm on a PC, I think my primary job is to prioritize the papers to help determine which ones make it in. In a way, it feels somewhat depressing that this is (in my mind) the main job of the PC. I do believe quality control and helping guide the direction of the community are important jobs, and that this is a powerful method for both of these things. But there is, in the end, always a non-trivial bit of arbitrariness, if you have 60 good papers for 40 slots (or if you have 20 good papers for 40 slots), around the boundary. [Joan Feigenbaum has suggested to me that we should be much more explicit about this as a community; otherwise (and this is my thoughts, not Joan's), we start finding the false notion that conferences are to be perfectly fair and essentially correct in their decisions, a standard which is impossible to reach and leads to time-wasting measures like endless PC discussions and, shudder, rebuttals for authors.]

I also think my secondary job is to offer what feedback I can to the authors. But really, there isn't sufficient time for detailed criticism, given the way theory PCs are set up. I once told an AI person I was working with that I was on a PC and had 50 papers to read, and he couldn't believe it. Apparently for AI PCs something like 10-20 papers is the norm, and 20 would be considered high. If we're going to made feedback a higher priority in the role of the PC, we're going to have to increase PC sizes dramatically, and restructure how they work. The way they're set up now, there's hardly time to read all the papers, never mind read them in sufficient detail to offer significant constructive suggestions. (That's what peer-reviewed journals are supposed to be for.)

With this in mind, I'll also throw out two wacky ideas that I'd like to see conferences try.

1) Instead of numerical scores, each PC member just gives a ranking of the papers they've read. Then use some ranking algorithm to give a first cut of where papers fall (instead of numerical averages, like PCs use now). I think this would reduce arbitrariness, since the variance in how people assign numerical scores would disappear, but it would take an experiment to tell.

2) Rather than assign each paper to three people for a detailed review, initially assign each paper to five (or more) people for quick Yes/Maybe/No vote, and chop off the bottom 50% (or whatever the right percentage is). My idea is that statistically speaking a larger number of less accurate votes is as accurate or more than a small number of more accurate votes, accurate enough that we can pre-process the bottom 1/2 or more and then spend more time on the quality papers. The negative of this is that the bottom 1/2 would necessarily get even less feedback than they do now. (I think I heard something like this idea was used in a networking conference; in my limited experience, networking PCs are much more ruthless than theory conferences about quickly finding and putting aside the bottom 1/2 or more of the papers to focus on the good ones.)

Tuesday, March 04, 2008

Missing Class

[Note: coincidence! I wrote this over the weekend, but have found myself "scooped" by a post on the same theme at the Complexity blog...]

It seems, more and more, I'm expected to miss class.

Obviously, now and again I have to miss class for a conference or workshop to go give a talk. Somewhere I'm sure there are rules and regulations (that generally go ignored) about this sort of thing, but I'm sure my employer and I share the understanding that I'm supposed to go present my research, and it's fine for me to miss a few lectures a semester for that purpose (while trying to get another faculty member or a graduate student to cover, of course).

I'm a little less clear on some of the other options that come my way. NSF panels. NSF workshops. (The FIND grant comes with 3 workshops per year.) DARPA ISAT meetings. PC meetings. Meetings to talk about Visions and Funding and such. Other invited talks. And so on. The underlying problem, of course, is that these things often require travel, which means missing class, which (along with family issues) is one of the reasons I don't understand why people don't think harder about how to avoid travel for these things.

How many classes is it OK to miss in a semester? Offhand, I'm thinking 4 is a goal for a maximum (for my standard Tu-Th teaching), perhaps because it looks like that's how many I'll miss this semester (cancelling 1 class, having 3 lectures covered by graduate students), and that's probably the most I've ever missed in a semester. (There was that one time, I missed the first day of class for the semester, because my wife inconveniently chose that day to birth our second child... but I digress.)

This semester, of course, I got myself in a bind by going to New Zealand, eating up several of my days. But I've definitely noticed more pressure the last few years for events that would cause me to miss class, which, ostensibly, is supposed to be a high priority for my job.

Saturday, March 01, 2008

Another Rant from Conference Reviewing : Algorithms and Evaluation

After my first conference rant on competitive analysis (based on my current stints on the SPAA and ICALP committees), I feel it's only fair to spread the love and rant a bit on my fellow algorithmists.

I simply claim the following : if you are presenting an algorithm with the claim that it might be useful in practice, you should aim to include at least a short experimental section showing that you've implemented the algorithm and that it/how it behaves.

Here's why:

1) If your suggestion is it's potentially going to be useful in practice, and it's your algorithm, it's incumbent on you to provide some evidence for this statement. An implementation is the best evidence. I don't expect pages of simulation results examining corner cases (although, if there's space, that's certainly nice); but a couple of paragraphs explaining that you implemented it, tested on basic data, and the program actually finished goes a long way.
2) It's not that I don't trust your math. It's just that -- well, no, it is just that I don't trust your math. Maybe you've proven that the algorithm is O(n^2). I'd like to know if in practice it seems to be O(n log n) [even if it's O(n^2) in the worst case -- now you've given an average-case or special-case open problem!]. I'd like to know if there's a hidden constant of 10,000 there that makes it really not practical in its current form. I'd like to see that you didn't make an error and that it doesn't look like Theta(n^3) when you run it. [I've got 46 papers to look over in a month. Make my job easier, your paper's more likely to get in.]
3) Maybe, just maybe, someone who might actually want to implement your algorithm will actually read your paper. A non-theorist. Don't you think they want to see that it seems to actually work before implementing it better themselves? Won't some experiments make talking about your work to non-theorists easier? Help make that connection...

I'm not saying every algorithms paper needs an implementation section. In many cases, "algorithmic" results are really "complexity" results -- we're just showing that something can be done, we don't actually expect anyone to do it, and in this case there's no need for a simulation or experimental results. (Of course, in such cases, I expect the authors to limit their claims of interest/utility in practice.) In some cases, space won't permit a reasonable evaluation of the algorithm -- but do plan on it for the journal version. In some cases, the coding and evaluation of the algorithm are so interesting it merits an entirely separate paper!

But I'm amazed at how few algorithms papers provide any actual experimental results (unless they're appearing in a networking/database/other systems conference, where it's more understood that results are also expected). I've actually submitted theory papers to theory conferences with experimental sections and had reviewers urge them to be taken out, which I find mystifying (and I ignore).

And yes, if I'm reviewing your paper, and you don't have any numbers where I think you should, I'm probably mentally (and numerically) docking your paper score....

Thursday, February 28, 2008

Disconnecting from E-Mail

One nice thing about traveling to New Zealand was that I spent several days disconnected from e-mail. I went a whole 80+hours without checking my mail on both ends of the trip. It was nice. (I could have checked mail, but in New Zealand it seems like all the hotels make you pay for Internet access. I didn't feel like paying. Of course, I had e-mail available at the workshop.)

The experience has suggested to me that I ought to try moving to limit my e-mail during the day. It seems more productive to set aside time to specifically deal with e-mail; maybe first thing in the morning and last thing before leaving the office. I'm not sure how this would work with other people, though; many people treat e-mail like it's a phone call, an immediate connection (including my wife), when of course it's not. I often see "emergencies" pop up in my e-mail box; while I was gone, I was asked to call somewhere for my opinion of a job candidate, and an NSF director wanted me to expand on my research nugget (as usual, by yesterday preferred, by tomorrow would be OK). These people didn't need to get in contact with me that second, but there seemed to be the clear expectation that I'd see their message and move on it within a small number of hours. Is that a realistic expectation?

Of course, these weren't real emergencies, and making a practice of leaving e-mail aside and blocking my e-mail time better would probably increase my efficiency, and possibly my happiness, since I would feel less that I was constantly being interrupted.

Wednesday, February 27, 2008

Of Mice and Computers

In the last of my posts about New Zealand, I'll talk about Mike Langston's talks on computational biology. He talked a lot about the style of computational biology. The difficulty of getting data unless you form a real partnership with people (who view their data as very valuable), the noisiness of the underlying problems, the need to worry about entire computation systems with memory/compute power/specialized hardware rather than individual algorithms, the compromises one has to make between theory and making things actually work, and so on. As I listened, it dawned on me, there's another area of research where I hear about similar issues -- search engines and computational advertising. The similarities sound uncanny.

The similarities reached the level of specific problems. The technical aspects of the talk were about heuristics/methods for maximum clique and biclique (bipartite clique) on real data. I've certainly heard of biclique coming up in search engine papers. Langston claimed to have the fastest bipartite clique algorithm in practice (at least on the biological data he was interested in). I wonder if there's room for crossover between these two fields?

The talk left me with a feeling that I've had before when seeing computational biology talks. The field seems interesting, but it looks like to have a real impact, you really need a lot of devotion to learning the underlying biology and making connections with working biologists. It doesn't seem like a good field for dabbling. So far, I haven't found myself ready to take the plunge and try to get involved with the field. Luckily for me, I still have other interesting things to do.

Tuesday, February 26, 2008

Practical Graph Isomorphism

Continuing my efforts to prove I was not just sitting out by the pool in New Zealand, I'll mention a highlight of the talks of Brendan McKay (of the Australian National University). Brendan has written code for graph isomorphism called nauty that works quite well in practice, handling graphs with up to millions of nodes. So while the complexity of the graph isomorphism problem is not known, it can be pretty hard to come up with bad examples that are actually hard to solve. As someone who's happy with good heuristics, I found it quite amusing to watch it in action. (On the other hand, it seems that many of the ideas behind this program are "old" by computer science standards. Are there any competing programs/approaches out there? Seems like a possible research direction. to revisit the algorithm engineering for this problem...)

While settling whether graph isomorphism is in P would certainly be interesting, Brendan pointed out that the question of whether it is in coNP is also quite important. Are there polynomial-sized certificates that can be used to prove that two graphs are not isomorphic? And one can imagine in practice one would like to have some methodology for easily convincing someone that two graphs aren't isomorphic.

As Brendan is a co-editor-in-chief of the Electronic Journal of Combinatorics, we also talked a bit at lunch about electronic journals (in particular the EJC). The EJC continues to grow successfully. (I'm happy to say I've published in it, back in 2004.) Remember to support your electronic journals.

Monday, February 25, 2008

Voting and Anti-Voting

While at NZIMA, I listened to Dominic Welsh's talks on Markov chains. It was a general talk, with a large chunk devoted to rapid mixing and applications. At some point he brought up the voter and anti-voter model, problems that I heard about a long time ago in the distant past, and that raised some questions in my mind.

The voter model can be expressed as follows. We have an undirected graph G, where each vertex has a label. For convenience, let's assume the labels are in {0,1}, although larger alphabets are possible. At each time step, a vertex x is chosen uniformly at random, and x chooses a neighbor y uniformly at random. Then x changes its label to match y's label. This is a Markov chain with absorbing states with all vertices having the same label. It's natural to ask things like what is the probability that you end up in the all 0/all 1 state from a given configuration.

If the graph is d-regular, and you start in a state with k 0's and n-k 1's, a simple argument gives that the probability of eventually being absorbed into the all 0 case is k/n. (Exercise Left To Reader.) Things seem to get more complicated for more general graphs. Here are some interesting questions that come to mind. Note: I don't know which are open and which aren't...
  1. Given a graph G and a starting configuration of labels, is there a polynomial time algorithm for computing the probability of being absorbed into the all 0 state? Or could a hardness result be proved? [My guess is there's a hardness result in there somewhere.]
  2. Given a star graph (one node in the center, connected to n-1 other vertices) and a starting configuration, what is the probability of being absorbed into the all 0 state (preferably in some natural closed form)? In particular, if you start with a 1 in the middle and a 0 everywhere else, what is this probability as a function of n? Notice that by symmetry here one can easily compute these values in polynomial time; the question is whether there are pleasant equations. [On some reflection, it's clear there will be nice equations; this is almost a birth-death chain with an added "phase" needed to track the center vertex. Exercise left to reader...]
  3. Similar questions to 1/2, but ask about the expected time/distribution of time until absorption.
Perhaps more interesting is the anti-voter model, which works just like the voter model, except that x changes its label to disagree with y's label. (Here the {0,1} alphabet is the most sensible.) Now we do not have absorbing states; we have a stationary distribution. But again one can ask similar questions:
  1. Given a graph G and a configuration of labels, is there a polynomial time algorithm for compute the stationary probability for that state?
  2. Are there natural families of graphs for which the stationary distribution for the anti-voting model has an easily expressible form? [d-regularity no longer seems to be enough...]
Obviously, one can argue about the importance of these questions, but I would just take the point of view that such easily expressible and seemingly natural questions about basic Markov chains are always interesting in their own right.