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.

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.

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.

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.

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.

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

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.

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

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

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.

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.

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

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.

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

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.

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.

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.

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.

New Zealand (NZIMA)

For the last week, I've been at a workshop in New Zealand, sponsored by the New Zealand Institute of Mathematics and Its Applications. They're having a programme in algorithms, including this workshop, and they invited me to give a couple of talks. (I'll be giving versions of my "Brief History of Power Laws" talk and my "Bloom Filters Survey" talk.)

OK, OK, I know, this violates my "avoid-travel" rule. Occasionally, I find myself suckered into travel for various reasons. In this case, the managed to time the workshop over my kids' winter break, in the middle of Boston winter (and the end of New Zealand summer), while it's winter. (My wife, also a native Californian, does not enjoy winter.) Besides the weather motivation, I've never been to New Zealand, and don't see a lot of future opportunities. So why not?

I'm happy to say we've had a really nice time in New Zealand, and I encourage visitors. Let me advertise that there will be a similar workshop sometime at the end of 2008 here as well. Perhaps if you're interested you might contact Mark Wilson, who will also leave comments with pointers and information. And the rest of the week I'll have some notes/ideas/open problems from the week in New Zealand.

Conference Reviewing: Another Rant on Competitive Analysis

Because of an inadequate lack of attention regarding conference deadlines on my part, I find myself currently reading lots of papers while concurrently serving on the SPAA and ICALP Program Committees.

And somehow, this means I'm reading lots of papers with competitive analyses of algorithms. (Both the standard variety, and the more new-fangled but generally similar "price of anarchy" variety.) Looking back on it, I should have simply have told the PC chairs that it might be best to make sure not to assign me any such papers, as I'm not sure it's fair to the authors who get me as a reviewer.

OK, I'm exaggerating. Don't get me wrong; I'm not automatically assigning negative scores to any such paper. Some of these papers I really like. But in general, as I've expressed frequently elsewhere, I'm a skeptic when it comes to competitive analysis. Why exactly should anyone care that you have an algorithm that in the worst case always gets within a factor of 6.5 of the optimal solution possible? Why is that the right way to judge an algorithm? (Never mind the offshoots, like those where you have an algorithm that's competitive if it has twice as much as memory as you allow for the optimal algorithm, and so on...)

In my mind, the problem is that competitive analysis has become such a standard in Theoretical Computer Science that people don't feel the need to bother justifying anywhere in the paper why they should use competitive analysis, when in fact these papers scream for a need for motivation.

Here are some motivations that tend to work for me when reading competitive analysis papers.

1. The resulting problem is just so mathematically interesting that we really have to look at it. (One person I can think of that manages to pull off this motivation with me time and again is Susanne Albers.) Generally, to pull off this motivation, your problem should be simple, clean, and natural; if you start to bog down in details, claiming that you're giving a "more realistic" model of the problem, you've already missed the boat in my mind. (If you really wanted to be realistic, you wouldn't be using competitive analysis...)
2. You are considering the performance of real, existing algorithms. This seems reasonable to me; here's something people actually do (like, say, Shortest Job First scheduling), and you want to gain some insight into its worst-case performance for this notion of worst-case. Many price-of-anarchy results actually correspond to the behavior of reasonable algorithms one might consider in practice, so I admit I often find myself more sympathetic to Price of Anarchy results, which seem more motivated.
3. You are using competitive analysis for an essentially (complexity)-theoretical result.
4. You are using competitive analysis to gain significant insight into the problem (and algorithms for the problem) that could be useful in understanding real performance or designing real algorithms. I think most papers implicitly claim that their paper fits into this last category, just because it obviously doesn't fit into the other three, but usually this isn't explicitly discussed. I think this motivation works best when the problem is inherently very hard.

I'm sure there are other reasonable motivations. But overall I would call for more restraint from the community; not everything should be subjected to competitive analysis, just because it can.

Some News from Harvard

A few interesting pieces of news from Harvard.

First, Harvard is setting up a scheme to avoid restrictive access policies of some journals. Essentially, as I imperfectly understand it, Harvard is obtaining from the faculty a non-exclusive right to disseminate articles written by the faculty. The intention is that a Harvard faculty member should be able to say to any journal that insists on having an exclusive copyright to an article, "That's fine, but I work at Harvard, and as such Harvard has a non-exclusive right to my work, which will be placed in an open repository." Stuart Shieber, a Harvard computer science professor and a strong proponent of open access, was behind this faculty legislation. Perhaps all the universities can get together and give a message to the journals that they are the ones that actually pay the faculty, and they will work against journals where the business model depends on restricting access to the research to only those who pay a monopoly-based fee.

Second, the Dean for the School of Engineering and Applied Sciences at Harvard, Dean Venky, is stepping down. Venky and I began about the same time at Harvard, and he's done a lot for improving the visibility and status of computer science and engineering at Harvard. I hope we can find a new Dean that can continue the push to build up these areas at Harvard.

On Valiant

I was avoiding posting on Les Valiant's EATCS award and the obvious question about the somewhat odd fact that he hasn't yet been given his Turing Award yet because of the amazingly obvious bias I would have (such as being on the same faculty with him). But now that it's shown up on the complexity blog, I feel unrestricted.

From my standpoint, Les is an "old-school" scientist. He spends a long time thinking very deeply about difficult problems, trying to come up with results or frameworks that will fundamentally change how we think about something. And as the list of his results show (see the complexity blog post and comments; whatever you think Les has done, he's done even more than that), he's been amazingly successful at it; he's had several once-in-a-lifetime results. As part of his style, he doesn't care about his paper count or h-index. This type of science is incredibly risky, and not for everyone. But it's a remarkable example of what's possible.

Class Demographics

This year, my undergraduate algorithms and data structures class is about 25% women. This is significantly more than average (enough that I noticed). Based on previous experience (and initial impressions from the first few lectures), these women will be very strong candidates for graduate school should they choose to apply when they graduate (one or two years from now). (I could simply be suffering mental bias from the various studies I've read, but my recollection from prior years is that when there's a larger cohort of women in the class, they generally perform better overall. I leave others to postulate on causes and effects, or to argue whether my data point is unrepresentative.)

Why are You Doing Research (and the CRA blog)

Despite the last round of budget horrors, the CRA is optimistic about 2009. While I'd like to believe it, I'll believe it when I see it. The other good news is CDI seems to be going forward roughly as planned.

In an effort to spur further comments, I'll have to say I was disappointed by the discussion that accompanied my last pointer to the CRA blog. It seems we have a lot of self-deprecating sorts in our field who don't think what we do is important enough to be funded by the government. Even after the great successes of the last 20 years, many of which have ties both direct and indirect to government funding. I don't get it.

In my opinion, government's most important role is to do things for its citizens that individuals can't do adequately by themselves. That's why national defense is a government job. And so is basic research. Basic research is important for national defense, as well as for the economy -- both in national defense terms (the bigger/better our economy, the better our national defense), as well as for feeding the homeless (unless we keep moving forward and developing, there's going to be a lot more homeless to feed). For those who think that feeding/caring for the poor is more important than funding basic research, I'd ask 1) isn't it more efficient for charities/local organizations rather than the national government to do this (except in extreme, Katrina-like circumstances) and 2) where do you think the economic advancement that will keep the country going (so your kids aren't hungry or homeless) is going to come from?

Some comments were of the form "there are so many other things to be funded, why fund us?" (Let's say us means "computer science", though one could make the case for basic science more generally.) First, our success record is pretty darn good. (I'm confused by people who don't recognize that -- as if none of the work we've done has had an impact on the world.) Second, all the other sciences are becoming more computational; I believe Chazelle's riff that algorithms will increasingly become the language of science. Funding us should help all the sciences. Third, well, see the above paragraph.

So (and remember, following recent comments, I'm aiming to be "controversial" and "less nice"), I'll end on the following thought. Certainly, I do research because I enjoy it and am reasonably successful at it. But if I thought it wasn't actually important, I'd either go find a job that paid a lot more, or go find a job that I thought meant a lot more. I've known people that have done each of those. For those of you who really, honestly feel that CS research is mostly a waste -- and are still working in the area -- why are you still around?

Class Reviews

I just received the class reviews for my Randomized Algorithms class. Historically, I have found my reviews are bimodal. Some students describe me as their favorite professor (and end up taking all my classes). Some students describe me in fairly unflattering terms. This year was pretty much the same.

The most signal from the noise was worth hearing, although pretty much stuff I already knew. First, students would like more of my time. I apologize for being busy, I suppose. Second, it would have much better to have had a TA. I agree (you think I enjoyed grading problem sets???). Sadly, my first choice TA was (rightly) busy working on his thesis, and there wasn't really another appropriate graduate (or undergraduate) student. But going without a TA is not something I'll try again.

A lot of the rest of the comments are lost in the jumble that comes from teaching to a class that serves a wide audience, not just theory folks. Some thought it was too fast, some too slow. Some liked that we pretty much followed my textbook, some thought I should let people read the textbook on their own and cover other stuff. Most found the problem sets a "challenge", which I think is just fine.

Class reviews never answer the question I really want answered. Five years out, was my class worthwhile? Has it had any impact on your research/job/worldview/life? Or even if you don't see an impact, do you remember it as a worthwhile learning experience? I don't care if you come out of the class thinking I'm some sort of sadistic homework machine (but really, I'm not...), if a few years down the road you find it was all worthwhile.

So ex-students -- not just MY ex-students, but all ex-students -- if you have a class you particularly liked several years back, a class that sticks in your mind or a class where the material has proven really useful to you later on, please send an e-mail to that professor and let them know. Anonymously is fine. That's the kind of feedback that means a lot to teachers. And you can even do it if you had a course you particularly disliked -- at least I wouldn't mind hearing from students who years down the line still think that I did a terrible job if they have constructive contributions to offer.

On Comments

I've noticed a phenomenon surprising to me on this blog: comments trickle in regularly on older posts. Whether that's from new readers discovering the blog and going back over old posts or regular readers who take a while to think about what they want to say, I thank you, and welcome your comments and questions always. (OK, I don't always have time to answer all the questions...) But it's interesting to me that the active lifetime of a post can be substantially more than a week.

More generally, I would like to figure out how to get more people commenting on the blog. I try to discuss issues here where there can be a variety of opinions and room for tangents, and I think the most interesting part of the blog is in the discussions. I'm genuinely surprised when I go to conferences and people tell me they read the blog, since in my mind the corresponding comment-level seems sparse.

So feel free to comment on what I can do to make the blog more comment-friendly.

More on the Shopping Period

As I mentioned two posts ago, Harvard has an unusual tradition of a "shopping period" -- you don't preregister for a class, but you choose classes after the first week, after you've had a chance to go to a lecture or two and see how you like it.

As a student, I loved it. What better way to get an idea if you'll like a class than to go, hear the professor, check out the syllabus, see who else is thinking of taking the class, etc. It makes choosing classes much more flexible. Instead of switching out of classes you've already chosen without seeing, you choose later. Part of that benefit might just be psychological -- most schools allow you to change courses in the first few weeks fairly easily -- but there is a marked difference between changing your classes and choosing your classes, especially if a student has to fill out forms or get signatures to change a class. The openness of the first week is a real benefit to students. I can understand why something like shopping period just might not be feasible for some very large schools, but I think it's a shame more schools don't do it.

Several years ago, there was a movement by the administration to introduce preregistration and get rid of shopping period. I was on the Committee for Undergraduate Education and the Faculty Council, and when the idea was first brought up I spoke against it, only to find that the issue didn't seem up for discussion; it apparently had been "decided" higher up. (It's things like this that helped make the Presidency of Larry Summers so unpopular, as opposed to some of the supposed reasons popularized in the press.) I was surprised that so many faculty on these advisory committees seemed willing to go along with the idea. It was massively unpopular among Computer Science faculty; we like students being able to choose their courses.

Overall, naturally, students didn't seem to like the idea. The administration's main argument seemed to be that it would allow more accurate predictions of class sizes in advance, so Teaching Assistants (and, in some classes, classrooms) could be assigned more readily and efficiently. (Here's an old Crimson opinion giving both sides of the issue.) This was around a time period where there were murmurs of graduate student unionization, and that might have been influencing the administration's mindset. Of course, nobody in the administration had an answer when I asked what prediction mechanisms they were using now, and if there was any evidence that preregistration would help predictions any. (I wasn't the only one asking this question. This was another reason the CS faculty in particular were against the idea; they saw no reason for it. It's in interesting problem to design an enrollment predictor; one semester, Stuart Shieber ended up running a projects class to find solutions for the problem.)

A funny thing happened, though. The change had to be approved by the faculty, and while I seemed to be a lonely voice with objections in these committee meetings, apparently a lot of faculty didn't actually like the idea. Instead of it being a quick and simple vote like the administration seemed to expect, the faculty meeting was a disaster. Eleven faculty spoke on the issue; ten spoke against it (including, I'm happy to say, me). Quietly, pre-registration was dropped as an issue, and shopping period continues.

Microsoft Cambridge Lab II

It's officially hit the wires, Jennifer Chayes and Christian Borgs will be heading up a new Microsoft lab in Cambridge II -- that is, here by Harvard and MIT. The proposed theme is interesting (and, happily, very appealing to me) -- algorithms with an emphasis on social networks and algorithmic game theory.

It opens this summer. I can't wait to see how it plays out.

Shopping Period Lecture

One of the great Harvard "traditions" that I enjoyed as a student is the "shopping period". Students don't pre-register for classes; they spend the first week "shopping" whatever classes they like, and then choose what ones they want to take. (I'll talk more about the "politics" of shopping -- the pros and cons -- next time.)

Because of this, rather than dive right into material the first class for my Algorithms and Data Structures class, besides going over the syllabus and requirements, I do something that at least I consider fun. We talk about how to get fair bits from a biased coin. The class starts with the classic brain-teaser: suppose you have a coin that may be biased. How can we flip that coin to decide something fairly, like who should pay for lunch?

[The simple solution to this question, unless I'm mistaken, is commonly attributed to von Neumann.]

Starting from there, I try and take the class through a series of questions, leading up to how to efficiently extract lots of random bits from a sequence of biased flips. The method I base the lecture on is due to Yuval Peres [(see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992)], and I learned about it at some point in graduate school at Berkeley. I try to run this lecture in a very back-and-forth manner, asking questions of the students and trying to get them to answer. (I also do this a bunch during the semester, with varying degrees of success...) Here's a version of my notes, with the various questions.

For the students who decide not to take the course, I figure at the very least they've learned something interesting that they can take with them. Also, it's conceivably the only time students will hear the word "entropy" in a computer science class, so I think it's worthwhile for that alone. Somehow, this problem fascinates people. Way back when I had more energy, I wrote a Dr. Dobb's article on it to show it to a wider audience, and there's been lots of related research on the problem. In some sense, this problem is the pre-history of all the randomness extraction work that has come since.

Algorithms for Newbies: Static or Dynamic?

A talk I just went too (by Lynn Stein) raised the following question for me.

While I have some strange ideas about how an algorithms class should be taught (like students should do some programming in an algorithms class), in most ways my algorithms class is quite traditional. Roughly, my class looks quite similar in the path it takes to Algorithm Design by Kleinberg/Tardos (or the corresponding subsections of the standard Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein). And specifically, I teach primarily what we'd call "static" algorithms; there's an input, a desired output, and the algorithm is the recipe.

These days, many of us do research in and arguably most commercial products use "dynamic" algorithms; that is, they're processes that are always on, reacting to the environment around them. (Your cell phone, for example, might be considered a dynamic algorithm device; so would a robot vehicle. If you like, you can think of "dynamic algorithms" as roughly being closely tied to "distributed systems".) My course is not geared to teach or have student explore dynamic algorithms, although they get brief mention. Lynn seemed to be suggesting that dynamic algorithms and programs should be taught before static algorithms and programs. It is, after all, the paradigm students are most familiar with, and arguably more interesting to them.

This doesn't sit right with me. In my mind, it's partly a "walk before you can run" issue -- you could teach a lot of calculus without teaching trig, but it doesn't seem the right way to go. Although that's not really quite the right analogy; I can see that the issues in dynamic algorithms/distributed systems -- like communication, and responding to asynchronous incoming signals -- are often quite different than for static algorithms, so much so that in many case you don't have to know your standard static algorithms to write a dynamic one. I think it's more that I think that to do anything that I would consider technically interesting you need to know static algorithms first. That is, sure you can probably teach people to write an interactive Internet chat program pretty easily, and they'd learn a lot by doing it, but that's like the task 20 years ago of writing a checkbook program, just harder because of issues raised by the interactivity. To do really interesting things with dynamic algorithms, my bias is you need good static algorithms behind it. Like Google mail's search features, or Amazon's recommendation feature, or other stuff. (Or at least, in many cases, you should understand the static version of an algorithm before trying to understand the dynamic version of it.)

So now I'm wondering if I'm just old-fashioned. What do you all think?

More SODA Stuff: Congratulations to Susanne Albers

Another fun SODA activity: getting to (belatedly) congratulate Susanne Albers on her Leibniz Prize in person. I had the great pleasure of working with Susanne early in our careers, and I'm thrilled to see her get this kind of recognition, which she greatly deserves. (A paper of hers I remember greatly enjoying was On Randomized Online Scheduling, if you're looking for a starting point to check out her work.) And 2.5 million euros is real money, particularly at the current exchange rate!

After my queries, Susanne politely explained to me that the money could not actually be used to buy a house, but was for research. I suggested that now was a very good time to ask for a raise. More banter followed. Certainly, one of the pleasures of conferences is catching up with colleagues in distant places. Congratulations Susanne!

The CRA blog on NSF Funding

If you aren't regularly reading the Computing Research Policy blog at the CRA, I recommend stopping by once a month or so. This month: find out about the latest NSF funding disaster (or "how the NSF and science in general got shafted in the budget process yet again") , including whether CDI will actually get funded (after we suckers researchers sent in 1300 proposals for about 30 grants...)

Harvard's Financial Aid

Bill Gasarch asked me to comment further on Harvard's new financial aid policy, which I briefly mentioned here, a post which strangely has gotten a few comments in the last 24 hours. (Of course, some crazy people have the wacky idea Harvard should be free.) One of the comments points to a recent op-ed piece in the New York Times; another commenter calls the piece illogical, which I'd have to agree with.) I'll offer my opinion, which has been colored by discussions with Harry Lewis. (By the way, have you bought his book yet?)

First and foremost, I'm glad Harvard did it.

One complaint is that Harvard only did it to stave off potential future legislation requiring it to spend more of its endowment. I just don't think this is true. Harvard has been raising its financial aid already quite substantially the last few years. There are plenty of other motivations and pressures to do so outside some sort of potential future legislation. In particular, if there are any political motivations, I'd say a more likely one is that the new President of Harvard and Dean of FAS did it to show some leadership and put a positive spin on their new administration out in the news. But I don't even think that's such a big reason. It's the direction Harvard's been moving for some time.

Another complaint is that this will put pressure on other schools who can't afford to do the same thing, particularly public schools, who will lose some talented students. I don't see this as a huge problem. Harvard only takes about 1700 students a year. Even if the whole Ivy League tagged along (like Yale has), that leaves plenty of talented students -- including the ones who would have gotten into Harvard but now didn't because the financial aid allowed a similarly or higher qualified student with fewer financial means to attend. When Harvard expands its entering class by a factor of 2, then people can complain what a terrible thing Harvard is doing, stealing good students away from other institutions. (Their argument will still be weak and misguided, though.)

I like how the two major complaints are so contradictory in nature. The first says Harvard isn't doing enough with it's big endowment; the other says Harvard is doing too much.

Me, I'm thrilled. Harvard did something good: it made attending Harvard more affordable. In doing so, it showed leadership, and has got people talking about the cost of college in places like the Opinion page of the New York Times. I hope it will lead to further positive changes, and improve the affordability college more generally.

The Job Search, Another Perspective

I am chairing the search committee for Harvard this year, motivating me to comment on the view from the other side of the search process. Everything here should be taken as general commentary, my own opinion, not the opinion of my employer or this search committee, and not necessarily specific to our search, which of course I can't discuss in any detail. (The following comments are not theory-specific, though I use theory-examples.)

A general search begins with getting several hundred applications for a small number of interviews and an even smaller number of eventual offers. Candidate quality is quite high, to the point where it's very difficult to whittle the folders down to a number that can be reasonably considered for interviews. [I'm personally doubtful that there will be enough academic/research lab jobs available this year (in, say, North American academic institutions) for all the highly qualified candidates. All the good people will get a job, I'm sure -- perhaps just not in academia, or in research labs. We'll lose people to non-research industry. That's not necessarily a bad thing, but I'm sure there are plenty of people who would like to stay in research that won't be able to. Of course, even if you get an academic job, it's not clear these days there's enough research funding to go around for everyone, anyway...]

Candidates need to find a way to stand out. More precisely, their research record needs to stand out. Somehow, unfortunately, it's not even enough to have a number of papers in top-tier conferences. In theory, for example, there's a number of people with multiple FOCS/STOC/SODA papers. Let's hypothetically say there's a dozen candidates with 3 or more papers in top-tier conferences in an area. What will make you stand out as one of the top two or three that gets an interview?

Letter-writers confirming the quality of your research (and your contributions on multi-author papers) are one obvious answer, and this partially explains the often observed hiring bias in favor of students from top-tier institutions; they have top-tier letter-writers. It is, generally, helpful to come from a top-tier institution, but it's less clear that it matters which particular one. Research quantity is another way to stand out. Those rare extreme cases of people who manage to publish 20 or so papers in top conferences do get noticed, certainly.

Quality, however, matters much more than quantity. Are you working on exciting problems, that can have a significant impact in some way? Are you following the crowd, or getting ahead of it? In essence, the question is "What is candidate X famous for?" If there's a good answer to that question when you replace "candidate X" with your name, you're much more likely to get an interview. And the statement "Candidate X is famous for writing a lot of papers" isn't really sufficient in itself.

Finally, I think there are further intangibles that contribute to this notion of reputation that need to be thought about earlier on in graduate school that impact the hiring process. Giving good conference talks gets you and your work more notice, increasing the fame factor. Working with many people, including people from outside your home institution, increases the visibility of your work (and improves your collection of letters).

In the end, of course, all this advice seems obvious. Then again, being on the search committee and writing this up clarified it my mind, and will make me reflect on my own recent work practices.

The Job Search, One Perspective

Of course the most interesting part of the SODA conference (and generally all conferences) is the conversations one has out in the halls. At some point in talking to one of the many people job-hunting this year, my own employment history arose, and at the risk of self-indulgence I thought it might be instructional to repeat here.

When I was finishing graduate school, the job market wasn't great. Most people went into postdocs. Your Jon Kleinbergs and David Kargers got jobs, of course, but most top 36 schools weren't hiring theorists out of graduate school. I felt pretty fortunate; I had interned at Digital Systems Research Center (SRC -- which, sadly, is now before-many-people's time...), and it seemed reasonably likely I might be offered a job. I also applied for several postdocs just in case, and applied to a small number of universities. I avoided a wide search, figuring my chances were small, and that I'd rather do a postdoc than take a job somewhere I didn't really want to go.

I got a small number of faculty job interviews -- including an interview at Harvard. But, at the end of the day, no academic offers. I did, happily, get a job at SRC. I think from the perspective of many graduate students, this would be seen as a failure -- no faculty job! (In telling the story at SODA, the look in the student's eyes seemed to suggest that interpretation.) In hindsight, of course, it's easy to see that this was far and away the best possible thing for me. SRC was a great place to be, full of innovative people and a strong ethic of theory/systems collaboration, and I received the benefits of mentoring from many great researchers (particularly Andrei Broder), as well as time to develop my research abilities and profile.

I decided to throw my hat in the ring again two years later. Since I liked SRC, I again only applied a small number of places that I might conceivably leave SRC for. I got 3 interviews. And just one job offer, at Harvard, which had rejected me last time around.

I suppose in this rambling anecdote I'm hoping there are some messages job-seekers current and future might take away. Patience really is a virtue; you needn't get to where you're going immediately. (It seems many CS theory folks have had long, winding, and quite pleasant careers.) For many, it might be beneficial to have some time and experience before facing the pressures of the tenure clock. You should never take it personally if you don't get an interview or a job offer. Don't be afraid to fail. Summer internships are a very good thing. Research labs are a very good thing.

I'm sure many job-seekers, having gone from undergrad right to grad school, feel the pressure to get to right to the next step, a tenure-track position. It might not work out that way. But there are many paths to a happy career; I hope you don't get so tied up in the process that you stop enjoying what you're doing.

More From SODA, Andrei Broder's talk

Andrei Broder gave an interesting invited talk on the new area of "computational advertising". As Andrei was my mentor for several years, and historically speaking, I am always thrilled by his work and his insights, consider this a gushingly positive review.

The talk started with a wonderfully complimentary introduction by Allan Borodin, who described accurately how Andrei was one of the initial leaders in the area of Web search algorithms, and his early success is a large part of the reason that so many people from our area have become involved in the field.

Andrei described computational advertising is a new scientific sub-discipline, at the intersection of search, information retrieval, machine learning, statistical modeling, etc. The main problem: find the best match between a given user in a given context and a suitable advertisement.

Andrei started with a brief introduction to advertising (brand marketing vs. direct-marketing, the $$$ behind advertising), and then focused on issues related to sponsored search (keyword driven ads) and content-match (context driven ads, e.g. driven by a page content), although he mentioned the field is much bigger than that (auctions, ad exchanges, privacy/legal issues, etc.). He emphasized the point that ads are "information". Irrelevant ads annoy; relevant ads inform and generate interest. Perhaps the most challenging fundamental question in sponsored search is how to find the right ad. Current practice allows broad matches -- if you want to advertise a Seattle hotel, you can broad match to Seattle or Seattle hotels, but this creates lots of false positives and false negatives. (You match too many things you don't want, and not all that you do. As another example, see my post on what pops up when you do searches related to theory.) What you really want is to match queries related to Seattle as a travel destination. How can that be done? How can you price query matches of these types, since it's not based on bidding on specific keywords? Notice that a lot of this now depends on semantic vs. syntactic matching -- understanding the intent. Similar questions arise in content match advertising, where there is the additional trouble of having a publisher of the page content involved. A further aspect is understanding the context of the user, potentially based on user profiles or recent past history.

One way of understanding context, naturally, is to use a search engine. To classify a keyword phrase, one could look at the search engine results, and re-define or interpret the keyword according to these results (say by giving it a category, to match a collection of ads). This can be made fast by classifying pages offline, and then use pages returning from the search query to "vote" on a category for the query (rather than text-analyzing returned pages on the fly). Even a weak classifier of pages does well if you have a reasonable voting scheme! Similar ideas can be used in content ads, using a mix of category and semantic information to find ads to go with a page. Andrei also raised the issue of caching ads; when are queries "close enough" that you can use a cached from a query-ad pair that may live in a cache?

I left the talk with the feeling that there were a lot of challenging "algorithm engineering" problems here. It's often hard to prove things in real-world settings, but one often needs real algorithmic insight to design solid, well-founded approaches to these real-world problems. This is why Google and Yahoo and MSN are hiring a lot of theoretically minded people. For such companies, there is always the aspect that one may have to give up some intellectual purity when working in these areas. You can't prove everything, and you need to make things that work. But this is a tradeoff. Not just a tradeoff in terms of money (though that's certainly there), but in terms of having a large base of users who actually use and gain from your algorithmic ideas. It's a tradeoff typical when working at theory/practice boundary, but here there's a pretty clear economic/users motivation that's really pushing this area forward. I think the talk did an excellent job of introducing the basic problems and motivation to a general (theory) audience.

Some Thoughts from SODA

There are many reports from SODA at the various theory blogs, but here's a quick report:

Persi Diaconis gave a great talk on interesting connections among carrying, shuffling, and Young tableaux. The starting point: consider adding m n-digit numbers, where the numbers are uniform base b. Then the possible carry values are between 0 and m - 1. For large n, what's the fraction of time the carry value is 0, 1, 2,... As the carries process is a Markov chain, this can be determined. He then connected this to theory of shuffles. Here's a nice model for a shuffle; each "card" corresponds to a point chosen uniformly on [0,1]. An a-shuffle maps x-> ax mod 1. The resulting re-ordering is a shuffling of the cards, which leads the way to analysis. From there he went on to tableaux.

Rather than try to summarize the talk, I'll point to his major references:

John Holt, Am Math Monthly: Carries, Combinatorics and an Amazing Matrix
Persi Diaconis, web page, papers from 2003: Mathematical developments from the analysis of riffle shuffles
R. Stanley: Volume II, enumerative combinatorics, chapter 7

He left open the problem of trying to develop a clean, pretty correspondence between the carrying process and shuffles.

Muthu conversed in the morning about MapReduce; see his new blog entry. In particular, the perspective and counterperspective on MapReduce in this post from the Database Column is quite entertaining.

I enjoyed the talk for (and want to understand the paper for) Improved Algorithmic Versions of the Lovasz Local Lemma by Aravind Srinivasan (who didn't give the talk, but it was still well-given). The Lovasz local lemma is quite beautiful, although I don't think I've ever used it in a paper. I'm inspired to try to find a good use for it.

Hunting for Problems

An anonymous commenter asked:

What advice do you give to graduate students hunting for problems?

I'd advise the following, though your working style may differ:

1. Read a lot. Nobody else wants their paper proceedings anymore, so keep those hefty tomes lying around and start reading from 2008 backwards whenever you can. I found problems (including my thesis topic) in graduate school just by reading proceedings and thinking hard when I thought I saw how to do something better. At worst, reading through proceedings introduces you to techniques, ideas, and problems, so it won't be a waste. Two notes about this approach: you'll probably have to read at least 40-50 papers before you find even one with a problem that appeals to you and that you have an idea on, and the problems you tend to find this way are generally incremental -- after all, they're based on somebody else's paper! For a beginning graduate student (with lots of time, and where publishing something incremental is just fine), those negatives aren't too bad.
2. Go to talks. For the same reason you should read a lot -- for exposure to problems and ideas.
3. Talk to people. Don't just talk to your advisor. Find other people with interesting problems and research, and see if you can help them, or if by talking to them you get a new idea for a research direction. I certainly don't come up with all of my own problems. Sharing ideas with others is key. In fact, I strongly recommend you talk with your other graduate students as much as possible, and try to start a paper-reading group/research group with them. Other students have more time than your advisor, so leverage that and work together to solve a problem. (Thank goodness we work in a field where cooperation is considered a virtue and collaboration is the norm.) At worst, it will make your work/social life at graduate school much better and less isolated.
4. Don't limit yourself to reading papers by/going to talks by/talking to theorists. If you're looking to come up with a new problem, odds are the motivation for that problem will come from outside the theory community itself. Find out what kinds of problems the systems people are having, and see if you can turn it into a theory problem. Even if your theory version is too toy to solve the real-world problem, you'll have a reasonable motivation for your introduction. And if your theory problem actually helps solve their real-world systems problem, bonus -- you now have contacts/letter-writers from outside theory that can help you in the future. And again, it will make your work/social life at graduate school better and less isolated if you talk to other people in the department besides theorists.
   

That's the top-of-my-head advice.

Meetings with Graduate Students

I think one of the signs a graduate student is on his or her way to graduating is when they start taking control of our meetings. With younger graduate students, I've found I have to set the agenda -- asking questions, pulling out information from them, and telling them things they need to do. Some time ago, I noticed that Adam was coming into our meetings with a written agenda. He asks me questions, gets information from me, and tells me what I need to do. And then, on a good day, we can collaborate on research.

I'm not saying that graduate students can walk in, day one, and take control like that. Indeed, most probably can't and shouldn't. But as a graduate student, the sooner you can take charge of your education and set your own agenda -- so your advisor is a resource, rather than your manager -- the better off you'll probably be.

Distributed Beam-forming: New Preprint

Besides NSF proposals, another item that took up time over my winter non-break was finishing a submission to ISIT 2008. To me, this paper was another example of how CS theory people and EE theory people are often tackling the same sort of problems, just in a different language.

The paper is titled Distributed Beamforming with Binary Signaling. Here's the English version of the problem. A bunch of weak transmitters are trying to transmit the same message to a receiver. Before sending the message, they are all out of phase, so their signals potentially cancel each other. They'd like to send so that they are all mostly in phase, so the signals reinforce each other and the message gets through. Initially, nobody knows their phase. The only communication possible is all the transmitters can send a signal, and the receiver can broadcast information back. How quickly can alignment occur?

To better understand the problem, we simplified it as follows. In each round, each transmitter can send a bit, a -1 or +1. Suppose the jth transmitter send the bit b(i,j) in the ith round. The jth transmitter has, for all time, a fixed phase p(j), which is +1 or -1. The receiver's obtained signal in the ith round is |sum_j b(i,j)p(j)|. If there are n transmitters, we'd like to get the obtained signal to beta n for some constant 0 < beta < 1 as quickly as possible; this is what we'll mean by alignment. The system is fully distributed, so transmitters can't communicate directly, and the only feedback they get is 1 bit broadcast every round. In this simple model, we looked at lower bounds and algorithms. The lower and upper bounds are both linear in n, but trying to get those constant factors right is apparently pretty important.

While this is a natural EE theory-type problem, it feels close to very similar problems in communication complexity, at least when simplified in this way. It was also interesting working on a lower bound, where we developed a reduction from a standard rate distortion problem. It seems to me EE people don't generally think in terms of reductions, at least not the way CS people do, although it's a terminology and framework that I think is increasing in use at conferences like ISIT. On the other hand, CS people don't always do reductions that give specific constant factors (in this case, related to entropy). So all in all it was an interesting reduction to develop here.

The "full paper" (ISIT papers are limited to 5 pages) will cover a lot more variations and have more details, though I expect there will still be many open problems. More generally, the theme of unifying the "communication complexity" picture between EE and CS, much as the coding theory picture has been greatly unified of late, seems like a great place to look for research problems.

NSF-related stuff

Although it might seem like it, I haven't really been on vacation -- just a vacation from blogging. One thing I was doing was sending in an NSF preliminary proposal for CDI (Cyber-Enabled Discovery and Innovation -- an unwieldy name I never remember without looking up), with that inspiring January 8 deadline. I was also doing minimal work on an Expeditions pre-proposal, thanks to enterprising colleagues who will probably seek payback if we get to submit a full proposal.

Does anyone have an opinion on this whole letters of intent/pre-proposal system for these new grants? Letters of intent I understand -- it's good to know how many people intend to apply for a new grant. But pre-proposals? Does this minimize the work for anyone? Sure, a 6 page pre-proposal is somewhat easier than a full proposal, but there's still a high overhead in just getting something off the ground (and getting it in the Fastlane system). And the tradeoff is now you may have to do a preliminary and full proposal, and there have to be 2 panels (1 for pre-proposals). I'd be happy if I thought someone from NSF had done the math and found that this approach would really save time and effort on our (the researcher) side and the NSF side, but I somehow think this was inspired some bureaucratic incentive I wouldn't want to imagine. I'd be happy to be proven wrong, if anyone has inside information.

So while at this point I'm sick of proposals, and would love to spend time actually doing research instead of writing to the NSF about research I'll happily do if they fund me, I see a slew of proposal deadlines coming up that I might end up applying to, and are certainly worth mentioning to the blog audience. Rather that point to individual calls, here's the link to the CISE list:

1. Theoretical Foundations. March 19 deadline. Looks standard. SING is still there. Nice to see that this time PIs can apply on two grants -- last time I applied, it was just one.
2. CyberTrust. March 24 deadline. I've never applied to this, but I hear many crypto/complexity people have had success.
3. NeTS. March 25 deadline. That's networking, for you theory folk. It looked like they've really revamped this call, completely changing all of the subareas. I'd say the subareas look more theory-friendly, with areas like Network Ecosystems and Exploratory Networking. But theory-friendliness seems to be at the whim of the panel, in my experience. (Sometimes that's good, sometimes that's bad.)
4. Assembling the Tree of Life. March 14 deadline. Not my kind of stuff, but I do know some theorists have received funding for algorithmic work on Tree of Life problems.
5. Human and Social Dynamics. February 19 deadline. Still plenty of time.

Sigh. So many calls, thankfully, not enough time to do them all. I wonder what's with the tightly grouped deadlines.

Theory and Fashion

I often end up using the Google search bar as my navigator, so I've been surprised of late when typing things like "theory cs aggregator" in to see ads with taglines like

Theory at Bloomingdale's
Theory on Sale
Theory Fashions

I didn't know CS theory was popular in the mainstream!

Theory is apparently a New York clothing design firm, and their wares are in most of the major chains (Saks, Neiman Marcus, Nordstrom's, etc.) So when you look up anything related to theory, and it's vague enough that Google isn't sure what sort of ad to throw at you, you end with clothing ads. I believe their website is www.theory.com, an address I suppose I should have purchased years ago.

Yes, www.cstheory.com is taken. (Smart thinking, Kevin...)

K'Nex Computing

Building an adder out of K'Nex.

I never know what to make of these sorts of stories. While I admire the enthusiasm, is this really what gets these students (and others) excited about computing? Somehow, it seems like the equivalent of writing your own iambic pentameter poetry in Latin. The result should be worthwhile for a small, small number of people.

Yet here I am linking to it.

Women in Theory of Computer Science Meeting

Although it's been well-covered in other blogs, I would be remiss not to mention the workshop for women in theory of computer science being organized at Princeton.

I'm always torn when I hear about such things. I think it's a very good and important idea, but at the same time, I look forward to the day when such workshops won't be necessary (and wonder why we're not there yet).

I do think that peer support is key to getting women into computer science, and having them stay. Some years ago at Harvard we were fortunate to have a group of four very mathematically talented undergraduate women, all of whom apparently had at least met each other in high school, come through the computer science ranks. It was clear that the "group dynamic" of being able to work together and talk with each other was very helpful to them. Three of the four went to graduate school in computer science; two are/have finished (in theory), one switched over to economics. While I have seen many strong women undergraduates come through Harvard, I haven't seen a group quite like this one, and I wish I saw more.

Of course, it also helps to have successful role models, so I suppose now is an apropos time to belatedly congratulate Susanne Albers for winning the Leibniz Prize. I had the great fortune to start working with Susanne while I was a graduate student at Berkeley and she was a postdoc at ICSI. It was a great experience for me, as at the time, I was still figuring out how this whole research thing worked; I learned a lot working with her. I'm thrilled she's getting this outstanding prize and the corresponding recognition for her body of work.

A New Book by Sean Meyn

I've found what to ask for my Cambridge University Press rep for my holiday present -- a new book Control Techniques for Complex Networks by Sean Meyn.

Other new bookshelf suggestions are welcome...

Hash Collisions -- Economist Article

The economist has a nice story about recent work on creating documents that yield MD5 collisions.

Harvard Improves Financial Aid

Harvard's is again improving its financial aid policy, as described here and here.

It's not as wacky or ludicrous an idea as not charging anyone tuition, but I'm still glad to hear it. (Wait, this doesn't cut my salary, does it...)

Preparing Students for Jobs

In a recent "discussion" on another blog, I repeatedly heard the refrain that we ivory-tower pie-in-the-sky university computer science professor types just aren't preparing students suitably for "real-world" employment. Personally, I think that's just BS. However, I realize I may have a fairly biased viewpoint. I teach at Harvard, and, if I may say so, our students are generally quite good and do well in the job market. Having spent some time in industry, and, if I may so so, being perhaps more interested than the average theorist about practical issues, I attempt to add "real-world" aspects to my classes, like programming assignments in my undergraduate theory course.

Now occasionally I catch students who admit to reading this blog. I mean all students, from whatever school, undergraduates and graduate students, not just students from my classes or Harvard students. I hope some of you are reading now. Because I'd like to ask you to enlighten me. (That means, for instance, I'll keep quiet on the comments.) Please tell me, in your experience, did your education prepare you for your life after in the real world. (For current students, you can comment on how you feel your education is preparing you.)

While I'd expect you to comment anonymously, I'd ask that you provide salient information where possible. (Harvard student or not, current undergraduate or long-time real-world person, CS or EE or other major, etc.) I'd also greatly enjoy hearing specific comments and criticism regarding my own classes, from any ex-students out there.

And in advance of some annoying anonymous commenter who might feel the need to say how out of touch I must be that I need to find out how students are doing by asking on my blog, please rest assured I have other sources of information (both personal and data-driven) on the subject, but this is, hopefully, an interesting opportunity for me and others to gain more insight.

Graham/Rexford talk on GENI/CCC

The CRA has the slides for a presentation by Susan Graham and Jennifer Rexford at the Grace Hopper Conference: Introducing the Computing Community Consortium. It's a nice talk covering the CCC, GENI, and some of Jennifer's current research.

SIAM is Spamming Me

Many of us received a note from SIAM today, starting with:

Dear Speaker:

We are so pleased that you are going to be a part of the ACM-SIAM Symposium on Discrete Algorithms (SODA08).

Please be advised SIAM has not yet received your conference registration. Although you may register on-site, SIAM requests you register in advance to confirm presentation of your paper.

I had to search my e-mail, to confirm my memory that I had in fact registered. I sent a note back to the sender explaining I had an e-mail confirmation, and got back this response.

Dear Michael Mitzenmacher,

Please note that this is a mass mailing. It clearly states and the end of the registration reminder

“If you have already registered please disregard this message”.

Indeed it does. But why then send a mass mailing saying clearly at the beginning of the message that they haven't gotten a registration, instead of just sending a reminder that speakers need to register? What makes this SIAM conference person (whose name I'm politely removing) think this is OK? It's not to me. I've sent a complaint, and I plan to complain further to SIAM staff at the conference.

Discussion over at the Complexity Blog...

For those who miss my regularly scheduled program, I'm busy inciting arguments over at the Computational Complexity blog on quiz-style interview....

The regularly scheduled program will return shortly.