Saturday, February 09, 2008

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?


A futuristic alien said...

Hi, I'm a grad student at UIUC, and I've been reading your blog for a while. I agree with you on your previous post when you said that something is not quite working right with the democratic process today... I wanted to respond in your defence when I saw some comments that disagreed with you but didn't.

I actually find it rather petty to even talk about national interests here while considering the issue of funding science. Given that practically all the prosperity humans enjoy today is exclusively due to science, it baffles me how there is so much less money in it as compared to other mundane things with little long term value.

For those who are a bit more careful and argue that certain areas can be thrown away - just consider the possibility that you are just being terribly myopic and need more humility. I think it makes perfect sense to be extravagantly lavish with something like funding science in general, even if it means wasting some money at the cost of other more seemingly important things. Because, when things do take an unpredictable turn and there is something to be found of value, it usually is of unimaginable valuable.

A very nice analogy can be drawn from this very eloquent essay I recommend (it was written with the aim of recognizing the importance of funding anti senescence research - but I can see how very similar analogies can be made to funding science even if it seems unproductive, and even at the expense of *seemingly* more important and immediate things to attend to..)

alex said...
This comment has been removed by the author.
alex said...

I am not a computer scientist...but on the question of whether it is worth funding cs-theory, I think it would be helpful if you gave me some concrete examples of theorems in cs-theory that have had a considerable impact on the economy.

The only advance I can think of that has made a worthwhile difference is pagerank - but I'm not sure that it qualifies as cs-theory, which I tend to associate with proving theorems, rather than experimental work like the original pagerank paper.

Michael Mitzenmacher said...


1) Please see the previous post I link to for some examples (I'll repeat and give more here).

2) One misimpression you may have is that somehow there is no connection between the proving of theorems and economic value. Sometimes, in theory, we solve a specific problem with immediate practical value. Sometimes, we develop frameworks and tools that only become economically valuable when used later. (These two sides exist because computer science is part engineering -- we often build things -- and part math -- we often prove things.)

For example, CS theory includes the development of the framework of NP-hardness (as well as other complexity classes). This might not have immediate economic value, but it certainly has had tremendous value, economic and otherwise.

(Think of it this way -- number theory, an area of mathematics, perhaps had little economic value for a long time. But then it became the foundation for a lot of cryptography. Were all those number theorists working for years valueless? No, it just took some time for the practical, economic payoff to happen, and then it was huge. See the excellent argument of the alien above.)

In short, CS theory (like all theory) is generally about the long-term payoff than the immediate need. We're explorers, and we don't often know where we're going.
VC's expect 8 out of ten of their companies to fail and 1 out of ten to pay off big. Theory work is comparable.

3) Some of this comes from the last post, but cs theory that has had economic impact? Broadly speaking...

Data Stream Algorithms
Hashing/hash tables
Web algorithms (PageRank, and all sorts of other algorithms)
Program verification
Linear programming algorithms and optimizations

And the list goes on...

4) And let's not forget the possibilities for the future:

Quantum computing (if anything comes of it, cs-theory has had a huge role in it)
Biological algorithms/study of biological networks

To conclude, people who can't find payoff from theory aren't looking very hard, or are underestimating the value theory has had in the often long road from idea to product.

Anonymous said...

To add to Michael's list:

Data structures

Basic graph algorithms (DFS,
shortest paths, flows)

String matching and parsing

Machine learning - foundations and algorithms

All of these can be taken for
granted and often are but it is
the same as the computational
hardware being taken for granted
by sciences that would not get
a lot done without them.

Anonymous said...

Michael, you are an insufferable idealist. =)

First of all, you are the exception not the rule. By your own admission, you work on the border of theory and applied. Among the theorists I hang out with (admittedly, more complexity theorists than algorithms folk), practical benefits are not even a consideration (until it comes time to write a grant).

I won't argue that CS research has not been important. But more important than biology and physics? Hard to say. (Do you really think CS is of equal importance as biology because we provide the computers that the biologists do the really important work on?)

One thing no one seems to have mentioned is how good academic researchers in the US have it, as compared to our counterparts in Europe. So why all the complaining?

I found your final question galling:
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?

For one thing, I like my job and it pays pretty well. (I'm serious here -- it's great to talk about "finding fulfillment" and all, but sometimes a job is a way to pay the bills.) For another, I *do* find my research important -- but in the same way that I find philosophy and the liberal arts important: I value my own work because it contributes something of intrinsic value to society. Not because of its economic value (how crass to always reduce everything to money!).

Michael Mitzenmacher said...

Anonymous #6: I'm perfectly happy with the idea that one can choose a career in academia for personal self-fulfillment and because there's a benefit to society that's hard to measure in pure economic terms. Indeed, those reasons certainly come into play for me personally as well. I just wanted to give the argument from the economic point of view, as to why the government should fund CS research more than it does.

I should point out that I haven't (as you seem to suggest) tried to make an argument about whether CS is/has been "more important" than physics and biology -- perhaps we can save that for another blog post, and see how many people I can anger. I'm disappointed that science as a whole is being underfunded. I'm particularly disappointed that for quite some time now, theoretical computer science has been remarkably underfunded.

Also, while I understand complexity theorists work on some wacky completely impractical things, I optimistically think an interesting non-trivial percentage of them will end up being useful (much in the same way pure mathematics often seems useless -- until you need it). For example, the study of expanders really does seem to have actual importance in coding theory. Who knew? Recently I wrote a paper with Salil Vadhan about how the Leftover Hash Lemma has real implications about why weak hash functions work so well in practice (a paper that I, at least, think should be important to practitioners). Again, who knew? [Admission: I didn't know, until these things came up in my research, and I learned some of all the amazing things people had already thought up for me.]

I'll admit some directions seem less likely to be fruitful than others, and we can't fund everything, and as a community we need to make sure we continue to move in promising directions. I think our track record is pretty strong overall. Though FOCS/STOC are still biased against algorithmic work -- oh wait, that's another argument for a different blog post too. :)

Anonymous said...

I'm not sure I'd describe my view of the '09 budget as "optimistic." What I was trying to convey in that post was that I'm pleased that we've hit one of the key milestones in the appropriations process (the President's Budget Request) with some of the best funding numbers for computing seen in quite some time. While it's great that we're starting with such a relatively high number -- overall, across all agencies, federal support for IT R&D would be about 6 percent higher than last year under the President's plan, and NSF's funding for computing would be nearly 20 percent higher -- we've got a long way to go in the process before that number gets enacted, if ever. But it's much easier, from my point of view, to start with a nice number in the budget request and work through the appropriations cycle than to start with a low one and try and bump it up. Call it "budget inertia."

That noted, I still think we're headed for another appropriations meltdown this year. I won't go all inside baseball here, but I think it's highly likely that appropriations will once again get postponed until after the November elections at least, and likely won't get finished until there's a new Administration in charge. Now, this doesn't necessarily mean that science will again lose out when it's all said and done. It just means that, well, I don't think anyone has a clue what the end game will be.

So, I'm pleased that science -- and particularly computing research -- has a pretty good number in the budget. And I'm pretty sure that number will hold through most of the process. But whether it will be there when the final chapter gets written...I have no idea. :)

Piotr said...

Hi folks,

I was too late to respond to the previous post and comments. Fortunately, this seems to be a recurrent topic :) So here are my 3 cents:

I think that it is healthy to (critically) ponder the contributions of TCS, or any other research field for that matter. It is always good to understand why we are doing what we are doing. Also, investigating "gaps" between theory and practice can lead to new promising research directions (as in case of photoelectric effect, to borrow an example from physics).

At the same time, I am somewhat surprised by the number of comments that seem to completely ignore the contributions of TCS, in particular to non-TCS. There are quite a few of them! Crypto is a classic example; see the previous posts and this web site for more.

So, instead of extreme pessimism or optimism, I would simply advocate realism. Surely things are not perfect, and perhaps it is the case that several research directions did not deliver as much as they promised. But we should not forget about those that did deliver, often well beyond the initial expectations. As Michael points, out, in the end it is just the numbers game.


Anonymous said...

see the previous posts and this web site [TheoryMatters] for more...

I'm not an expert, but isn't it a real stretch to say that PCP research led to Digital Fountain?

And describing quantum computing as practical is an optimistic prediction for the future, not current reality.

Michael Mitzenmacher said...

By the way, alien, I didn't get around to saying it before, but I appreciate your point of view. Hope you'll comment again (whether you agree with me or not...)

Michael Mitzenmacher said...


I'm not an expert, but isn't it a real stretch to say that PCP research led to Digital Fountain?

And I don't recall saying that PCP research led to Digital Fountain. The importance of expanders, branching processes, large deviations, etc. all show up however; that's a fair bit of complexity/math that was quite helpful.

Again, some people seem to insist on "this idea in complexity led to a product". I'll happily admit that it doesn't generally work that way. But often ideas and techniques that arise in math/complexity prove important in a totally different space. I don't think this is an accident; it's because complexity is "looking ahead", which is what we want science to do.

And describing quantum computing as practical is an optimistic prediction for the future, not current reality.

And indeed, if you'd chosen to read what I'd written, you'd see that I'd described it as

4) And let's not forget the possibilities for the future:

Quantum computing (if anything comes of it, cs-theory has had a huge role in it)

We agree; it is an optimistic prediction of the future. Maybe nothing will come of quantum computing; that wouldn't shock me. But it's the kind of "risky bet" basic science is supposed to be pursuing. My point was that if it succeeds, it could be yet another great example of how cs-theory has had a large practical impact, with payoff far beyond what theory research as a whole consumes.

Anonymous said...

Michael: in my comment of February 10, 2008 9:37 PM, I was referring specifically to what is written on the TheoryMatters website, linked from the previous comment. I was not disparaging anything you said. =)

Anonymous said...

...and my point was: if we are trying to present the practical impact of TCS to the world, can't we come up with better examples? (For instance, public-key crypto is not mentioned...)

Piotr said...


I used TheoryMatters web page only as a source of examples of high-impact TCS work. I am not claiming it is in any way complete.

My understanding is that its goal was to list examples that are (a) relatively recent (so PKC is out) and (b) unexpected (and therefore difficult to fund in the application-driven model).


Anonymous said...

> My understanding is that its
> goal was to list examples that are
> (a) relatively recent (so PKC is
> out) and (b) unexpected (and
> therefore difficult to fund in the
> application-driven model).

Then there is an obvious need for a list which is more complete, and is giving examples that even non-CS people would understand. The theorymatters web page is very sketchy in that respect, and it's easy to critisize most of the items. Furthermore, it seems to me that the list is more like what people in TCS think that it's important, and not what people outside TCS consider important.
Why there are no links (e.g., to Akamai).
Why there is no game theory, auctions etc?
The fact than nothing from crypto is on the list is surprising too.

BTW: people in data mining have their document (
with top 10 algorithmic contributions in their field.

Anonymous said...

In my opinion, government's most important role is to do things for its citizens that individuals can't do adequately by themselves.

I do not know whether or not what I think is Pareto equivalent to what you think, but I would say that it's the job of government to hedge the downside risk for society.

Your word verifications should come with an answer key.