"I write today about the global economic crisis and its implications for us at Harvard."

In what I'm taking as a sign of continuing Impending Doom on the economic front, I received mail from the 3 levels in the hierarchy above me regarding the financial state of Harvard in these tough times. (First from Harvard President Drew Faust which is where the title quote comes from, then the Dean of the Faculty of Arts of Sciences, and then the Dean for the School of Engineering and Applied Sciences.)

Little was given in way of specifics, but the general theme was clear. About 1/2 of Harvard's budget comes from the endowment payout each year. (The curse of a large endowment -- this number is probably higher than most institutions.) While nobody is giving a number for Harvard, the widely quoted statement from Moody's financial research is that endowments will lose about 30% this year. Given that Harvard has been outperforming the market and most other endowments over an extended time period, you can take your guess as to whether our losses will be above or below average. No matter how you do the math, it's not good.

So that means there will be some belt-tightening, and some delays in various plans. Again, very little in the way of specifics, but I'm sure (and Faust's letter suggested) that Harvard's new progressive financial aid program would not be touched. I imagine most everyone is getting similar messages at other institutions, but feel free to share your stories in the comments.

Book by FemaleScienceProfessor

I'm an occasional reader of the blog FemaleScienceProfessor. Often the blog is just about being a science professor, which is interesting, and I can relate to. And sometimes the blog is specifically about being a female science professor, which is also interesting, even if I relate to it less.

Well, FSP has re-worked past blog entries into an on-line book available at lulu.com. I haven't yet bought and downloaded it yet, but from the Table of Contents, it appears to be a particularly worthwhile book for graduate students thinking about a life in academia, and for new faculty. The bulk of the book seems gender-neutral, if that's a concern. I thought I'd give it a free plug.

Security Issues in Cambridge

Harvard is getting new ID cards next year, thanks to an ambitious student who apparently figured out how to forge IDs (including a duplicate ID for University President Drew Faust). Because, really, how could using unencrypted ID numbers on the card, and giving access to undergraduate computer user assistants access to all ID numbers, ever lead to a problem? (The student also apparently made fake state driver licenses as well. Who says Harvard students don't learn useful real-world talents?)

Of course, Harvard isn't the only institution in Cambridge where students can obtain skills in the security area. Some MIT students, working under the famous Ron Rivest (the R of RSA!), figured out several flaws with the new ticket system for the Boston subway system, including ways to rewrite tickets so that they have lots of money available on them. So, naturally, the subway system sued to keep them from talking about the flaws at a security conference.

In both cases, the systems seem easily breakable (well, at the least the Harvard IDs were easy, not sure about the subway) with a card writer that can be obtained for a couple hundred bucks.

Of course, I'm not surprised, based on previous experience.

I wonder when organizations that want secure cards will realize that perhaps they ought to ask the students to try to break the system before they deploy it, rather than wait for them to break it after.

How Cuill Is It?

Having a strong interest in search engines, I woke up this morning and promptly took a look at cuill, the new search engine at www.cuill.com. I'm sure you can find 100 news articles on it if you want.

The first thing I always look for, naturally, is myself. One of the blessings of having a near-unique name is that searching for oneself is quite easy. Indeed, I'm sure that in the future everyone will be trying to have an essentially unique name, if only so they can register their name as a domain on the Internet without conflict. (Hey, I just looked up Mike Smith -- currently Dean of the Faculty of Arts and Sciences at Harvard -- and he shows up 3rd on Google for me. I'm impressed -- for such a common first-last name combo, that's pretty high up!)

Color me unimpressed with Cuill. They did put my homepage up first, with the nice picture of the cover of my book. After that, a lot of stuff from citeseer and such -- so you can quickly get titles/descriptions of some my papers, but it doesn't seem the best use of the real estate on the page. As a comparison, Cuill suggests it has 22,992 results for Mitzenmacher. Google suggests it has 63,700. While not perfect, Google will pretty quickly get you to my home page, my publications page, my blog, my book (on Amazon), my DBLP entry, and a few of my papers, which seems a better set of results than what Cuill currently gives.

A few other tests suggested what I expected (since every once in a while a new search engine pops up, and the story is often the same). It's good, but not great. It seems a little slow, but perhaps that will get better (it might be getting hit overmuch by a lot of curious people like me). But your mileage may vary, and it's always interesting when a new search engine opens up to the world.

Zittrain on Colbert

So I'm a little late with this news (hey, I was out of the country), but Jonathan Zittrain was on Colbert plugging his book The Future of the Internet and How to Stop It. (If you Google Zittrain and Colbert, you'll find links...) It's a pretty tech-laden interview for the mainstream, in my opinion.

This is relevant (at least to me) because I've known Zittrain for years -- we interned at Microsoft at the same time back in college, and bumped into each other again at Harvard (where he was a law professor, before moving to Oxford). I'm now officially humbled -- someone I know, approximately sort-of in my field, has appeared on Colbert. (OK, I admit, I'd personally rather go on the Daily Show, but still...)

Quick Notes from SWAT

1. I'm at SWAT, but don't have much conference news to report; I arrived right around lunch, and went to my room for a post-red-eye nap.

In sort-of-conference news, the hotel is great, Gothenburg is a beautiful city, the organizers seem on top of everything, and I had a very nice dinner with the PC/Steering committee folks. Topics ranged from the difficulty and cost of running a conference, to the "Bell Curve" and IQ, to why people live in Sweden but work in Denmark. And a few technical research-y ideas as well. A nice day. Boy, I hope I don't mess up my talk tomorrow.

2. A place I consult switched to a VoIP phone system requiring me to install phone software on my Mac and gave me a USB headphone set. The upside -- I can call home from Sweden on the wireless! Nice. Yes, I could also use Skype, but calling on a regular phone has its advantages. Yes, I know I'm late to join the 21st century.

3. Following the complexity blog, let me welcome Sorelle to the list of current bloggers. She's a CS theory graduate student who's just started!

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

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.

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

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.

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.

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.

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

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.

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?

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.

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

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

Hash Collisions -- Economist Article

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