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!

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.

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?

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.

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

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.

Introducing New Scientific Ideas, and D-Wave

Apropos of my last post on Digital Fountain is Scott's Aaronson's current report on D-Wave researchers giving talks about what's behind the hype of their building of quantum computers. For those who don't know the story, the short summary is that D-Wave Systems has claimed non-trivial advancements in the development of quantum computers, and many (most? all?) academic quantum scientists aren't buying it, based on the very limited evidence they've seen.

Why does this story remind me of Digital Fountain? I recall the early, early days going around giving talks about Tornado codes and their potential uses in networks, and in the beginning, the greatest skeptics were the coding theorists. One talk in particular, I remember, early on a very senior coding theorist insisted repeatedly that highly optimized Reed-Solomon codes could do anything we were claiming. The rest of the talk was a bit more difficult to get through after that argument. (I like to think by the end of the talk he thought that maybe there might be something new there...)

So is this to say that I think the academic crowd is being too hard on D-Wave? Absolutely not. It sounds like they're doing their job -- trying to figure out what's going on and asking tough questions. The point of my parallel is that the coding theorists had the right to be skeptical. (One reason for it was there was a huge language barrier, me not knowing what a "decibel" was, and them not really getting why linear vs. quadratic complexity was such a big deal. The divide being coding theorists and CS theorists has shrunk an awful lot this past decade.) It was our job to convince them that we had the goods. And we provided evidence with equations, papers, talks, and demos. While they took some convincing, the coding theorists listened to the evidence, and rapidly came around.

Here, the story seems to be (my interpretation!) that D-Wave is presenting painfully unconvincing demos and releasing not nearly enough information for experts to see if they have any new ideas. Then they're compounding this by excessive PR overstating what might eventually be possible with quantum computing. (There seem to be some arguments whether they themselves are doing the overstating, or uninformed journalists, in which case D-Wave is just failing to correct the press, but whatever.) Their excuse for this is that they're a private company so they have to keep their secrets. Understood! But they shouldn't then be surprised when knowledgeable academics studying the issue voice their opinion that the emperor has no clothes. I'm quite sure the scientific community has enough open-minded people that if they start producing convincing evidence, or give enough details on what they're doing so people can verify if the path they're taking is productive, they'll be understood and praised. Until then, the feedback they're getting is rightly telling them they have more to do.

How Mathematicians View Computer Science?

Luca Trevisan points to an article in the AMS by Neal Koblitz on modern cryptography that I think everyone in theoretical computer science (TCS) should read, as it exposes how at least some mathematicians view the culture in TCS. In summary, it's very negative. While I think the article is flawed on many levels, I'd argue that we ought to consider it as constructive criticism, and think about what, if anything, we might learn from it.

For example, one statement I found fairly misguided is the following:

Math departments usually believe the
Conjecture. For the development of mathematics it is better for someone to publish one excellent paper in n years than n nearly worthless papers in one year.
In certain other fields of science - including, unfortunately, computer science and cryptography - the analogous conjecture, while most likely true, is not widely believed.

I accept the constructive criticism that in computer science we perhaps publish too quickly, and too many incremental things. On the other hand, this conjecture has little to nothing to do with reality. For every Wiles, who spent essentially a decade on what is a very important result, there are probably 100 mathematicians who spent a decade on the problem getting essentially nowhere and publishing what in retrospect are worthless papers. And the implication that TCS is producing only a stream of worthless papers is fundamentally incorrect. The question is really whether the culture should be that a person works only on big problems with the goal of having a very small number of big results (say, 1) over their lifetime, or that a person helps the community make progress through smaller and quicker increments (as well as the occasional larger contribution). Given the important tie between TCS and real-world applications, there's a clear reason why the community has developed with a larger focus on small/quick progress, although as a community we are also supportive of people who want to work the other way as well. The phrasing of the conjecture is clever, but I actually think TCS progresses much better with the culture it has than the one Koblitz favors. (Just like sometimes fast local heuristics are much better than slow exact algorithms.)

Rather than just start a tirade against Koblitz, however, I think we'd be best off dissecting the article and understanding what aspects of the TCS culture has led to his opinions and, in many cases, misperceptions. We may find some things worth changing, either to improve our culture, or at least to present ourselves differently to other sciences.

Blog Comment Feed

One thing I've been enjoying is that as people seem to discover this blog, they comment on the older posts. I appreciate these comments and I hope the newcomers stick around!

Suresh asked me to enable the comment feed, which would allow people to easily see these newly arrived comments. They appear to be enabled, but while there is a link for the standard blog feed at the bottom of the page is a link for the blog feed, there is no link for the comments. I spent some time playing with the template to no avail. (I'm happy to take advice from anyone who could get the link to show up.)

However, you can just enter the URL directly to your reader. Apparently, the URL you need to get the comments is:

http://mybiasedcoin.blogspot.com/feeds/comments/default

and the regular feed for the blog is

http://mybiasedcoin.blogspot.com/feeds/posts/default

Favorite tech policy/news blogs

I'm sure there are plenty of places to get such information, but for basic tech news (like what's up with Google and the FCC, voting machines, and the iPhone), I'm enjoying the Machinist blog, out of Salon.com. The longer weekly columns are interesting too; I'm already looking forward to getting a Zonbu.

For straight tech policy, my favorite for quite some time has been Ed Felten's Freedom to Tinker. The past week he's been commenting on the California e-voting reports, which gives further evidence to what most of us already know (or would have guessed) : current voting machines are fundamentally insecure. I prefer to think this is due to incompetence and ignorance rather than malicious intent on anyone's part, but what do I know. My only complaint is that he doesn't post enough!