Thursday, December 14, 2006

Motivation

You can tell a lot about a field by how researchers motivate their results in papers and talks. Pure mathematics often gives little or no motivation starting a paper or talk with something like "Let λ be an inaccessible cardinal…" In economics, even in theoretical papers, considerable time is spent in coming up with stories to justify a given model. More discussion is spent in economics talks about the model than the particular proofs and results that derive from that model.

In theoretical computer science and in particular computational complexity we straddle between these two worlds. Our goal is to understand the power of efficient computation so we have complexity classes like NC, P, P/poly, BPP and BQP that try to approximate real-world models of computation. We have classes like NP, #P and PSPACE that capture a large number of interesting problems that we would like to solve. We have models like Probabilistically Checkable Proof Systems (PCPs) whose parameters help us understand the limitations of approximation. We have combinatorial tools like expanders and extractors that have wide applications in many areas of complexity and beyond.

But all these classes, models and tools have very nice theoretical properties as well. We tend to focus more on the theoretical foundations judging papers more for their theorems and the difficulty of the proofs than the importance of the underlying problem. In the end we reduce the amount of motivation in the paper often to a single sentence of the introduction and a theory audience only rarely questions the importance of a model during a talk.

Once we deemphasize the motivation of a model, then others, in an attempt to find open problems, look at variations of the model. Often these variations are motivated solely by the importance of the original model, even if the variations have little relevance with the original motivation of the model. Researcher then consider variations on the variations deviating quite far from the original model and its motivations.

Other computer scientists often complain, rightly or wrongly, that theoretical computer science and computational complexity have lost touch with real computational issues. We must be careful to not focus too much on presentations that don't express or don't even have some reasonable motivation beyond the difficulty of the proofs.

1. Very often theoreticians look at a
problem because existing techniques
do not seem to be able solve the
problem. This is at least the case
in approximation algorithms. This is
often good because it helps us
develop new tools whether the
problem is well motivated or not. Of
course this makes sense only if
the problem has some somewhat
subjective "aesthetic" structure.

However, when giving talks to a
wider CS audience, it is best to
and explain the context and
related problems. Often theoreticians don't articulate
this philosophy of tackling problems
to develop new tools.

2. In fairness, exploring variations of a model can give us insight into what it is about the original model that gives it the properties it has. In some cases, this improves our understanding of why a particular notion captures a computational phenomenon -- or helps convince us that the old notion is no longer sufficient.

For example, in cryptography, there is a phenomenon called "chosen ciphertext attack," in which an adversary can pick ciphertexts of her choice, submit them to a decryption oracle, and then see the results. This sounds freaky, but in fact several real-world protocols provide openings for attacks of this sort; perhaps you don't get to see the entire decryption, but you may learn, say, whether a consistency check on the resulting plaintext failed. There are at least two variant formalizations here, and work investigating relations between these formalizations. This sort of work is valuable for establishing what the "right" formalization might be, even though it requires looking at seemingly small variations of a model.

3. Computer science is about systems and theory. It is not necessary that systems research has to give profound proofs of correctness or impossibility. Nor it is necessary that theoretical research gets always motivated by some applied application. A while ago you had this discussion of why not all faculty members are not able to teach all first year courses. Just a remark that question is not irrelevant to this one.

Systems research and evolution has its own rules well-respected within the community. Theoretical research is not the servant of systems (which doesn't care much about heory anyways). Computation has its applied part and as well its own autonomous existence, independent to the existence of related hardware or software. Goedel or even 100 years ago Hilbert or some of his predecessors they had more or less concrete questions regarding computation (or something close to that). Since no real world machines existed these questions were not important or even legitimate? Theoretical computer science has to make up its mind. If most theoreticians believe that funding is the primary reason for research then perhaps we should all go to industry and those who studied engineering to dig out their licences and start making real money.

4. Theoretical computer science has to make up its mind. If most theoreticians believe that funding is the primary reason for research then perhaps we should all go to industry and those who studied engineering to dig out their licences and start making real money.

I totally agree with this sentence, and in fact with the whole comment.

People confuse (or even define) "applications" with "new ways of getting money".
Why is something I can sell, practical or applied? For instance, car manufacturing would surely count as "applied" by most people, while I claim it is unpractical, and has no real contribution to humanity.
Understanding black holes is much more "practical": it contributes to our understanding of the world, which is much more valuable than car selling.

5. People confuse (or even define) "applications" with "new ways of getting money".

This is untrue. Motivation for models and problems can come from many different sources, and one of the major ones is that the result has applications. These applications are simply a way to project the model back to the real world - math is essentially a field of abstraction, and after making an abstraction and thinking about abstract concepts, there's nothing wrong with making them concrete. If a result of mine has applications in disease control, does that mean I should stop doing TOC and go work for a private firm?
This not withstanding, as far as computer science is concerned, ways to learn about black holes are certainly an application (in physics, or scientific computing).
Gi

6. These applications are simply a way to project the model back to the real world

I am not claiming that all "applications" are wrong. I'm claiming that some applications are actually "not practical" even if they formally conform to what most people would view as a "projection of the model back to the real world".

For instance, 'applying' your model in disease control is certainly "practical" (though one could argue that it is not the purpose of TCS to contribute to such an important effort; and if this is your main purpose, then you should not move to a private firm, of course, but maybe to the faculty of medicine, for instance).

On the other hand, progress in TCS that relates to Electronic Commerce does not seem to be very "practical": although it might have "concrete projection in the real world", it serves a marginal purpose of some firms to make more money.
I would say that to understand the evolution of starts, or of the nature of computation (for instance P!=NP), is more "practical" (though it is not what you meant by "a projection in the real world").

7. For the idealistic sorts who
claim that math and theory need no
justification from applied world and
hence do not need to justify it.
This is a perfectly valid statement
if one is working on research as
a hobby with no pay. But thats
not the case in the real world.
One shouldn't forget
the economics behind the research
enterprise. The only reason
that such large sums of money are
pumped into research is because
of past benefits and hope for
future benefits. People realize
that there is merit to working
on very theoretical areas but
one cannot deny that market
forces exist. Discussions on
the value of a particular line
of work are essentially the
market at work.

8. For the idealistic sorts who
claim that math and theory need no
justification from applied world and
hence do not need to justify it.
This is a perfectly valid statement
if one is working on research as
a hobby with no pay. But thats
not the case in the real world.

You are wrong. Scientific research is about revealing the truth. If you are doing research for the money, or try to motivate your research by "applications for getting more money", I would say that this is a perfectly valid purpose if you are working on research in some private firm or by your own (either as a hobby or a job). But that's not the case in the real world of research, i.e., most research institutions and universities.

One evidence of your mistake is the existence of pure-science, humanities, social-sciences and arts departments in most universities. This is the real world of research. What you were referring to is a marginal market-oriented sub-culture, which is not the concern of real science.

9. The only reason that such large sums of money are pumped into research is because of past benefits and hope for future benefits.

What "large sums of money" are you talking about, and where does one get them? NSF funding for all of theoretical computer science is about \$5m/year, a rounding error on a rounding error.

10. Anonymous, exactly what parts of Computer Science would you insist should move to other departments (if bioinformatics now needs to be part of the faculty of medicine)?

Also, can you tell us what department you're at, so I can make sure not to apply there? ;-)

-- A non-TCS computer scientist

11. Theoreticians who contrive "motivations" often sound pathetic. I recently heard a talk about coding by someone who obviously doesn't care about why and how people code, but only wanted to work on some "open problems" in coding. The math was nice, but the attempts to sound relevant to something that actually happens in the real world were laughable.

So you should make up your mind: are you doing theory, or are you doing something useful? Faking it makes theory look ridiculous.

An ex-TCS computer scientist.

12. So you should make up your mind: are you doing theory, or are you doing something useful?

This is a false dichotomy. There are many results which are 100% theory and incredibly useful (RSA comes to mind).

Not every result has to be applicable, that is why we call it theory, but practice is a rich source of inspiration (again RSA comes to mind) and we would be the poorer if we chose to ignore this muse.

13. One evidence of your mistake is the existence of pure-science, humanities, social-sciences and arts departments in most universities. This is the real world of research. What you were referring to is a marginal market-oriented sub-culture, which is not the concern of real science.

That is the poor world of research. The real world of research is physics, biology, economics, medicine, computer science, etc. These are not curiosity driven disciplines, but practice driven. The amount of funding for them far dwarfs that of the humanities in all developed countries, with the exception of the USA, which lately seems bent in destroying its hard won scientific advantage.

14. "... USA, which lately seems bent in destroying its hard won scientific advantage."

I don't think it can be emphasized how true this last statement it. Some good students (where I am, outside US) refuse to apply to any schools in the US, because of the Iraq war, politics, etc. Instead, they will only apply to schools in Canada.

15. There are many motivations for being a vegetarian. Some people do it for health reasons. Some find the killing of animals immoral. Some think it is better for the environment. Some do it for religious reasons. Strangely, I hear very few arguments among vegetarians that the reason that they practice vegetarianism is the right one.

There are many motivations for scientific research, and specifically for theoretical computer science. Reasons include plain old curiosity, the desire to improve technology, the intellectual challenge, and probably many others. I find it odd and rather depressing that people feel the need to argue why their reason for doing TCS research is the right one.

16. I find it odd and rather depressing that people feel the need to argue why their reason for doing TCS research is the right one.

that analogy is slightly misleading michael. it is impossible to steer clear of such discussion, if we are to resolve how to entice more new grad students and researchers into TCS (remember that they have a far weaker understanding of these issues). i agree we can definitely do it in a non holier-than-thou manner.

17. Theoreticians who contrive "motivations" often sound pathetic. I recently heard a talk about coding by someone who obviously doesn't care about why and how people code, but only wanted to work on some "open problems" in coding. The math was nice, but the attempts to sound relevant to something that actually happens in the real world were laughable.

Well, we should be careful that our notions of "what happens in the real world" are not too limited by assuming that the real world will always be the way our little corner of it has been in recent years.

Ideas that have gone from theory to practice in our lifetimes, while by no means the norm, are not rare. It is not hard to find contemporary nay-sayers who derided things like garbage-collection and software model checking as "unrealistic" or "irrelevant".

But these aren't really from the STOC/FOCS community. Any ideas that have informed practice that we can trace back to STOC/FOCS? (besides SC's paper on NP completeness)

Natrix natrix

18. (This is an attempt to get this blog commentary back on topic.)

There is one motivation that people have
that they may not even realize: They
prove theorems because they can. There
are fields of theoretical computer science
where a model is defined as a STARTING
POINT to understand something, and thus
is fairly simple, but then since it is
TOO EASY TO PROOF THEOREMS ABOUT, theorems
are proven about it, variants are looked
at, etc, most of which have little to do
with the original motivation.

19. Any ideas that have informed practice that we can trace back to STOC/FOCS?

Sure, here is a sample from STOC/FOCS/SODA:

- David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. STOC 1997: 654-663

- Jon M. Kleinberg: Authoritative Sources in a Hyperlinked Environment. SODA 1998: 668-677

- Peter Weiner: Linear Pattern Matching Algorithms FOCS 1973: 1-11

- Narendra Karmarkar: A New Polynomial-Time Algorithm for Linear Programming STOC 1984: 302-311

20. Well, we should be careful that our notions of "what happens in the real world" are not too limited by assuming that the real world will always be the way our little corner of it has been in recent years.

Indeed, as someone who works in the overlap of theory and practice I often run into systems people who get irritated by the slightest degree of abstraction, even of those details that in all probability are truly irrelevant.

21. That is the poor world of research. The real world of research is physics, biology, economics, medicine, computer science, etc.

Let me understand what you are saying: "poor" is the antinomy of "real". So for you "reality" is "richness".

I think it is now clear that you define "real world research" as a "research that gets a lot of money". This is of course a senseless definition, and so there is not much left here to argue.

22. There is one motivation that people have that they may not even realize: They prove theorems because they can...

Bill, I hope you were being sarcastic. While possibly true, this is the worst motivation for doing something and I think that is part of what the original post was getting at.

In general, whether you as a researcher care about theory, practice, or something else, it is worth asking yourself periodically why you are working on the problem you are working on.

23. Some good students (where I am, outside US) refuse to apply to any schools in the US, because of the Iraq war, politics, etc. Instead, they will only apply to schools in Canada.

I love the phrase refuse to apply, as if anyone forces them to. They don't do anyone a favor, you know....

24. The whole discussion is somewhat fruitless, since some people here oddly define "real world", "practical" and "applied" as "new ways of getting money". Could someone say what is "practical" about electronic commerce, for instance?

25. Michael Mitzenmacher says:
There are many motivations for being a vegetarian. Some people do it for health reasons. Some find the killing of animals immoral. Some think it is better for the environment. Some do it for religious reasons. Strangely, I hear very few arguments among vegetarians that the reason that they practice vegetarianism is the right one.

Of course they are free to practice anything they like. But why would anyone listen for 50 minutes to an exposition of the finer points of vegetarianism?
Even more importantly, why should taxpayers subsidize an in-depth research of vegetarianism?

misha b

26. So for you "reality" is "richness".

The other way around. There is money because they are real. When a science becomes mature enough to make predictions and hence able to make an impact in the real world, money follows. That is the power of science, not abstract truth alone. Here is a simple example: right now there are three pencils on top of my desk. That is god's honest truth. Does that make it science? Of course not, because it is irrelevant. Good science seeks truth in the context of relevance.

27. There is money because they are real.

This sentence is false. It is not justified in any way. Destiny's Child make a lot of money. Are they better than Mozart?
Criterions for "good" science are not measured by the money it gets.
Or else, we would all become engineers, working on new arms.

28. It is not justified in any way. Destiny's Child make a lot of money. Are they better than Mozart?

There you go again using the reverse implication of "richer is better", and then applying it outside the domain in which it was proposed, namely, funding of science.

Criterions for "good" science are not measured by the money it gets.

No one is proposing we measure quality of science using grant allocation. This is just a strawman of your own creation that you keep coming back to.

I claim there is a correlation between relevance (loosely defined) and quality of science and a correlation between relevant science and funding.

To give an example, topology is relevant because experience tell us that over centuries many of these "purely abstract" math results are fundamental blocks in the edifice of science. Trying to parse the intentionally obscure meanings of Kierkegaard, on the other hands, sits on the outside edge good science. In the hard sciences his writings would have merited a "reject, please rewrite and resubmit" while in philosophy it becomes the subject of PhD thesis to try to parse Soren's musings... go figure!

You also failed to address the point that abstract pursuit of truth alone is not science, as illustrated by the pencils on the desk example.

29. I claim there is a correlation between relevance (loosely defined) and quality of science and a correlation between relevant science and funding.

No. There is no such correlation, just as my "Destiny's child" example illustrates (in a different domain).
Indeed, when considering public opinion (which is close to "public funding of research"), there is an approximate reverse correlation between popularity and quality.

Your use of the word "relevance" is meaningless. You have not explained what counts as "relevant" and to what purpose.

For example, the flight to the moon is a great technological achievement, yet it is by no means a great scientific achievement. It counts by most people as something that is "practical" or "applied" -- and indeed it was funded heavily, and many scientists contributed to this project.
Yet, the proof of Fermat's last theorem by A. Wiles is a far greater scientific achievement, though it is not "practical" and much less funded.

You also failed to address the point that abstract pursuit of truth alone is not science, as illustrated by the pencils on the desk example.

First, in order to do science you have to follow certain rules of scientific research. So the pursuit of truth alone is not science, but it a necessary condition for it.
Second, your pencil example just illustrates my point: Both the existence of the pencils on your desk and the correctness of Fermat's last theorem (assuming the consistency of the mathematical axioms) via the proof of Wiles indeed constitute truthful statements.
The fact that there are pencils on your desk is highly practical: you can use these pencils. While the proof of Wiles is not.
Still, you would agree with me that even if you reached the conclusion of the existence of your pencils by scientific methods - it is not a good science, while what Wiles did is. Wiles' proof is deeper while not practical. Acknowledging the existence of your pencils, or flying to the moon are both practical, but most people would agree are not "deep", and they have no scientific merits in themselves.

30. Destiny's Child make a lot of money. Are they better than Mozart?

No, but they're hotter than Mozart, and therein lies the real motivation for theoretical computer science-- it's the sexiest kind of CS.

31. Anonymous writes:
"there is an approximate reverse correlation between popularity and quality."

This kind of arrogance will not bring TCS very far. Research on cancer is very popular, because people care about curing it. If TCS is not relevant to anything that people care about, then TCS has a problem getting people's money. Telling people that they don't know what "good" research is will not help TCS get more of their money.

32. just as my "Destiny's child" example illustrates

A correlation that holds in science may or may not need hold in other fields, so your example is irrelevant.

Yet, the proof of Fermat's last theorem by A. Wiles is a far greater scientific achievement, though it is not "practical" and much less funded.

Wiles proof is both practical (in the topology-like sense described above) and very much funded. Where exactly do you think the salary for Wiles and his grants came from? Research in the US, particularly in theoretical areas is by far and large funded by the government.

First, in order to do science you have to follow certain rules of scientific research.

I can follow all the rules you want: double blind trials, peer review publication and so on, and none of that will make the statement on pencils a good scientific fact.

The fact that there are pencils on your desk is highly practical: you can use these pencils. While the proof of Wiles is not.

The complete opposite is the case. Nobody cares that I have three pencils in my desk. It has no relevance to anyone but me. The truths discovered in the process of solving Fermat's last theorem will live forever and eventually form the basis of a breakthough in quantum physics or computer science or economics or crypto. They will also be the foundation of other breakthroughs within mathematics. That is why the proof of Fermat's last theorem is good and relevant science and the three-pencils-on-desk preprint is not.

33. Telling people that they don't know what "good" research is will not help TCS get more of their money.

We are talking here about what is the truth (though I'm not claiming of course to hold the key for it), not about good tactics to get more money. This is the point I made above. Let us not forget that funding is just a mean not the end in itself.

34. A correlation that holds in science may or may not need hold in other fields, so your example is irrelevant.

It is an illustration. It does not constitute a proof or a statement, but a logical analogy. Hence, as such, it is a perfectly valid one.

and very much funded

I do not think this is true. Wiles' work was not heavily funded.

and eventually form the basis of a breakthough in quantum physics or computer science or economics or crypto.

These are just speculations and hopes.

I can follow all the rules you want: double blind trials, peer review publication and so on, and none of that will make the statement on pencils a good scientific fact.

Indeed. Though it is a practical statement (even if it applies only to you), it does not constitute good science, since it is too concrete -- and not abstract; This illustrates that the criterion for good science is not usability or practical applications, but something else, which relates to truth of some higher level of abstraction and validity.

35. which relates to truth of some higher level of abstraction and validity.

Science values abstraction in as much as it produces results of great generality and hence great applicability and hence great relevance.

Bourbaki on the other hand proposed the pursue of abstraction for abstraction's sake and that lead nowhere.

36. The main reason that society lets mathematicians and other theoreticians have their jobs is because someone needs to teach undergraduates. For most theoretical computer scientists, the only real contribution (and damage) they make to society throughout their career is in teaching generation after generation of engineers.

37. For most theoretical computer scientists, the only real contribution (and damage) they make to society throughout their career is in teaching generation after generation of engineers.

That is equally true of 95% of applied scientists, or are you under the delusion that your "applied" results are about to change the world?

The impact of most science in the real world is second hand and, with very few exceptions, a single scientist contribution is to science what a single brick is to the great wall of China.

38. That is equally true of 95% of applied scientists, or are you under the delusion that your "applied" results are about to change the world?

Yes she/he probably is. On the other hand I don't agree with you being so harsh at her. I find it kind of refreshing hearing not only that the scientific method itself is not science but more importantly that "place this button here" or "move the cable around, it may work" is science:)) Perhaps the least "dangerous" way is to educate people by transforming them into monkeys that program. A banana on one hand the keyboard on the other. It's indeed refreshing being critisized by people who have trouble delaing with concepts as abstract as addition modn.

39. On consulting my BibTex database, here are some of the more interesting research justifications that I find.

The prize justification is from the Jefferson Library (transcribed from Thomas Jefferson's personal copy):

Spinoza's Theological and Political Discourses
(Library of Congress, Sowerby Catalog #1268, Thomas Jefferson's personal copy)
Preface: The Translator to the Reader
Religion and Government being the Subject Matter of the Book, 'tis ea\sy to gue\ss what Sort of Men are like to decry it; but let tho\se who are angry with it and find fault with it an\swer it; in the mean time the Crape Gown and the Long Robe are both defied to prove that there are any Tenets in the Whole Treati\se, half so dangerous or de\structive to the Peace and Welfare of human Society, as tho\se Doctrines and Maxims are, which have of late years been broached by time\serving Churchmen and Mercenary Lawyers; for which they justly de\serve the hatred and contempt of all mankind. Nothing more needs be \said to any Reader, than to de\sire he will deliberately read the Book twice over, before he condemn or commend it.

----- more mundane quotes -----

@book{Carmichael:99,
author = {H. J. Carmichael},
title = {Statistical Methods in Quantum Optics I: Master Equations and Fokker-Planck Equations},
publisher = {Springer},
year = 1999,
jasnote = {Note: there is no volume II as of 2005. Quote from the Preface, (no page) "As a graduate student working in quantum optics I encountered [\ldots] deep irritation caused by the work I was doing, something quite fundamental that I did not understand. \ldots Certain elementary notions that are accepted as starting points for work in quantum optics somehow had no fundamental foundation, no verifiable root. My inclination was to mine physics vertically, and here was a subject whose tunnels were dug horizontally. \ldots I now appreciate more clearly where my question was headed: Yes it does head downward, and it goes very deep. What is less clear is that there is a path in that direction understood by anyone very well. [\dots] Here one must face those notorious issues of interpretation that stimulate much confusion and contention but few definite answers."},}

@misc{Pauling:46,
author = {L. Pauling},
title = {The possibilities for progress in the fields of biology and biological chemistry},
year = 1946,
note = {Proposal to Warren Weaver, Rockefeller Foundation, June 19, 1946. This file was supplied by historian Lily Kay \cite{Kay:93}; the original sources are available through the \UW \QSE web site at \url{http://www.mrfm.org}, specifically at \url{http://courses.washington.edu/goodall/MRFM/historical_background.html#kay}},
jasnote = {The 1946 ancestor of the NIH Roadmap: Quotes: p. 1: Biology is just entering a period of great and fundamental progress. p. 1: The methods of science have now become powerful enough to offer the promise of a successful attack on even the giant molecules, such as proteins, nucleic acids, and viruses, and on the interrelations and methods of interactions of these constituents of living matter. p. 2 The answers to many of the basic problems of biology ... are hiding in the remaining unknown region between 10 Angstroms and 100 Angstroms. p.2 It is only by penetrating into this region that we can hope to hunt them down. p.3 It is proposed that an intensive attack be made during the coming fifteen years ... p. 3 An important part of the program would, indeed, be the attempt to discover and develop new techniques. p.3 A desirable result of the proposed research program will be to attract into the biological field some very able young [people] with thoroughly sound and modern training in the biological sciences. p.3 We believe that very great progress can be made by the cooperative efforts of a large group of most able investigators, supplied by the best apparatus which can be made. p. 6 Extremely important advances could be expected if the effective resolving power of the electron microscope could be considerably improved. ... If it were possible to ... make visible the individual molecules of the serum proteins and other proteins of similar molecular weight, all the uncertainty which now exists regarding the shapes of these molecules would be dispelled. In addition, direct experimental information about the methods of combination of large molecules with one another could be obtained, and a new technique would be available for investigating physiological structures such as the gene. It is our opinion that the improvement of electron microscopy is a problem which is extremely important for biology.},

@inBook{Wilson:94,
author = {E. O. Wilson},
title = {Naturalist},
publisher = {Island Press/Shearwater Books},
year = 1984,
pages = {364},
chapter = {Biodiversity, Biophilia},
jasquote = {Wilson page 5: "This creature was astonishing. It existed outside my previous imagination." Wilson page 9: "I also hoped for more than sharks, what exactly I could not say: something to enchant the rest of my life." Wilson's concluding paragraph: If I could do it all over again, and relive my vision in the twenty-first century, I would be a microbial ecologist. Ten billion bacteria live in a gram of ordinary soil, a mere pinch held between thumb and forefinger. They represent thousands of species, almost none of which are known to science. Into that world I would go with the aid of modern microscopy and molecular analysis. I would cut my way through clonal forests sprawled across grains of sand, travel in an imagined submarine through drops of water proportionally the size of lakes, and track predators and prey in order to discover new life ways and alien food webs. All this, and I need venture no more than ten paces outside my laboratory building. The jaguars, ants, and orchids would still occupy distant forests in all their splendor, but now they would be joined by an even stranger and vastly more comples living world virtually without end. For one more turn around I would keep alive the little boy of Paradise Beach who found wonder in a scyphozoan jellyfish and a barely glimpsed monster of the deep.},}

@inBook{Crease:03,
author = {R. P. Crease},
title = {The Prism and the Pendulum},
chapter = 8,
publisher = {Random House},
year = 2003,
pages = {156--7},
jasquote = {Recollection of Herbert Goldstein: The young theorist Abraham Pais gave a presentation that was interrupted by Ehrenhaft, then pushing seventy and still championing the monopole cause. He approached the podium demanding to be heard, and was politely escorted out of the room. A young physicist named Herbert Goldstein was sitting next to his mentor, Arnold Siegert. Pais's theory is far crazier than Ehrenhaft's,'' Goldstein said to Siegert. Why do we call Pais a physicist and Ehrenhaft a nut?'' Siegert thought a moment. Because,'' he said, Ehrenhaft \emph{believes} his theory.''},}

@book{Hoskin:2003,
author = {M. Hoskin},
title = {The Herschel Partnership, as Viewed by Caroline},
publisher = {Science History Publications},
year = 2003,
pages = {86},
jasquote = { William Hershel writes in 1785: "In a letter which Sir J. Banks laid before his Majesty, I have mentioned that it would require 12 or 15 hundred pounds to construct a 40-ft telescope, and that moreover the annual expenses attending the same instrument would amount to 150 or 200 pounds. As it was impossible to say exactly what some might be sufficient to finish so grand a work, I now find that many of the parts take up so much more time and labour of workmen, and more materials than I apprehended they would have taken, and that consequently my first estimate of the total expence will fall short of the real amount." Author M. Hoskin comments: "Not for the last time in the history of astronomy, an astronomer seeking support had been modest in his initial demands, knowing that the funding body, confronted later with a choice between writing off all the money spent so far or coughing up more, would cough up."},}

-----

40. Most of the people end up doing applied "research" because they are not good enough to do theory. The choice can be made very early or very late depending upon level of incompetence. Surely, any one who did badly in most of the undergraduate math courses would not end up doing a phd in Math. Similarly somebody who dropped out trying to do a phd in complexity would not do theory all through his life. There are exceptions but they are very few. How many so called researchers in bioinformatics are good enough to prove PCP theorem or for that matter publish even one good paper in theory.

41. Dear #40,

You, my friend, are an idiot. If you honestly think that theory research is somehow "harder" than other areas and that (for example) people in bioinformatics cannot publish a serious paper in focs/stoc/.. you should have a huge ego check.

Read some of the papers in ML, bioinformatics, etc. Just because you can prove the PCP theorem doesn't mean that you can produce deep results in other fields or match the level of excellence achieved by those researchers.

It's comments like these that make me feel ashamed of being a theoretician (though I keep telling myself that such egomaniacs are found in all fields).

-ro

42. "I love the phrase refuse to apply, as if anyone forces them to. They don't do anyone a favor, you know...."
4:32 PM, December 15, 2006

I guess they think they are doing themselves a favor, by not directly or indirectly supporting an evil government.

The responses to this blog entry highlight interesting trends of arrogance in TCS researchers: 1) they think they are smarter than everyone else in CS. 2) they seem to think they can separate themselves from and ignore the political atmosphere that may ultimately destroy their field. If the US economy sinks because of the war, the sinking dollar, etc, then government support for TCS, math will be the first to go. You think the funding situation is bad now ...

43. Science values abstraction in as much as it produces results of great generality and hence great applicability and hence great relevance.

Let me conclude my argument, and come back to the orignal post by Lance.

1. Practicality or applicability is neither a necessary nor a sufficient condition for a scientific research.

2. On the other hand truthfulness and abstractness is a necessary condition for a scientific research (though not a sufficient one, as you pointed out).

By this we can conclude that one should not seek, or even settle for, motivations for his research in the realm of practical applications (e.g., disease control).

44. they seem to think they can separate themselves from and ignore the political atmosphere that may ultimately destroy their field. If the US economy sinks because of the war, the sinking dollar, etc, then government support for TCS, math will be the first to go.

Sorry guy, you should work on your paranoia.
It was I that wrote the above comment ("I love the phrase refuse ..."), and I'm not even an American (not even close....)

45. It seems surprising given the volume of responses here, but this little flame war has barely generated any heat ... and it certainly hasn't generated (or shed) any light whatsoever.

46. Words are like leaves; and where they most abound much fruit of sense is rarely found.
A. Pope

Less preach more Work. Let us then be off.

47. #38 wrote:
"That is equally true of 95% of applied scientists, or are you under the delusion that your "applied" results are about to change the world?"

My results did not change the world, but they were implemented in commercial software (and I didn't even defend my phd yet).

48. Bill wrote:

...but then since it is
TOO EASY TO PROOF THEOREMS ABOUT, theorems are proven about it, variants are looked at...

Actually, I think you mean just the opposite. Most of the simplest models, Turing machines, circuits, Ave-case complexity model, etc. are difficult to prove theorems about. At least the big ones. We look at variants (restrictions) of the models in order to prove theorems about them. Wouldn't you agree?

49. Anonymous sez: If the US economy sinks because of the war, the sinking dollar, etc, then government support for TCS, math will be the first to go. You think the funding situation is bad now ...

----

Here is a BibTeX entry relating to the concluding years of the Vietnam War. The situation for fundamental research then was grim---so grim that US physics never really recovered---but the over all situation for US science over the next thirty years was pretty good, thanks largely to the confluence of VLSI, sensors, and Arpanet. Add these together and you get modern mechatronics, which provided the main engine for the US economy in the decades 1970-2000.

The points being: (1) all that has been said on this thread has been said before. (2) there is present grounds for substantial optimism in today's confluence of quantum physics, nanotechnology, and bioinformatics; this confluence is at least as powerful as the 1970s confluence of VLSI, sensors, and networks, and with diligence, it will provide at least as powerful an engine for the US and global economy.

-----

@book{Barber:75,
author = {R. J. Barber},
title = {The Advanced Research Projects Agency, 1958--1974},
publisher = {Richard J. Barber Associates},
year = 1975,
note = {NTIS accession no. AD-A154 363.},
jasnote = {Order this product from NTIS by: phone at 1-800-553-NTIS , email at orders@ntis.fedworld.gov. NTIS is located at 5285 Port Royal Road, Springfield, VA, 22161, USA.},

jasquotes = { ARPA directors, 1958-1975, from Fig. I-6 (after page I-6)

Roy W. Johnson 2/58 -- 11/59
Gen. A. W. Betts 12/59 -- 1/61
Dr. Jack P. Ruina 2/61 -- 9/63
Dr. Robert L. Sproull 9/63 -- 6/65
Dr. Charles M. Herzfeld 6/65 -- 3/67
Dr. Peter Franken (acting) 3/67 -- 11/67
Dr. Eberhard Rechtin 11/67 -- 1/71
Dr. Stephen J. Lukasik 1/71 -- 1/75
Dr. George H. Heilmeier 1/75 --

VIII-43 Barber, re AGILE program in Rechtin years: "This was indeed an area where ARPA and many other [agencies] were limited by ideas, not funds, and tried unsuccessfuly to compensate for the former with a generous application of the latter." Notes: (advanced sensors abolished as an ARPA office in 1973).

Quote -1: IX-38 "Director Lukasik "The urgent drives out the important. ... This is one of the reasons why so much of the money that ARPA put into the Vietnam War was not a good use of ARPA resources. Because there was very little of a fundamental nature that was done, because we were working on the *urgent*, not the important."

Quote 0: Barber X-1 "At most, about one-third of ARPA's lifetime can be said to be 'normal'. Most of the time it functioned in the midst of considerable bureaucratic stress. Outright abolition was widely discussed in 1959 and apparently quite seriously considered at the Secretary's level a decade later."

Quote 1: IX-13 Director Lukasic: "I really believe that the reason why you can't leave certain defense science up to the NSF, is that the NSF is going to pick its priorities on the basis of science and it may turn out that ... the defense [problem] is ninth on that list, and it may be a first rank [problem] for defense. ... [Basic research] can be mission-relevant basic research, and that's the essential point.

Quote 2: VII-28,29 During Director Herzfeld's tenure "The ARPA review figures show graduate student-research assistants in materials fields increasing from approximately 1100 in 1961-2 to 2000 in 1965-66, an 82 percent increase. ARPA-supported graduate students alone accounted for some 600 of the addition." However, under Vietnam funding pressure, the IDL program was cut from 27.3 million in 1967 to 4.4 million in 1968 ... the program never recovered.

Quote 3: VIII-59 Under Director Rechtin "Materials science now concentrates ... on reducing materials science to practice by demonstrating novel devices and new techniques." IDL's rechristened as Materials Research Laboratories (MRL's).

Quote 4: Avoiding technological surprise. Sproull (X-17) "I regarded that [guarding against technological surprise as the heart of our mission ... as *the* principal mission of the Agency. " Barber remarks: this is extremely hard to do in the context of insisting upon relevance and rapid transfer. Rechtin is anti-surprise (X-20): "You can't do anything fast enough in the business that the other side can't compensate for it before it gets disastrous. In other words, you can't come up with an overwhelming operational advantage in any short time." }, }

---

Interestingly, this is the only internal history of ARPA/DARPA ever published. It was widely perceived as negative, and was therefore suppressed (historians have to order xerox copies via the Freedom of Information Act), but with the advantage of hindsight we can see that ARPA/DARPA was doing a tremendous number of things right.

50. 1. Practicality or applicability is neither a necessary nor a sufficient condition for a scientific research.

Applicability, broadly defined**, is a necessary condition for good scientific research.

** applicable as in having impact on the real world or impact in other areas of science.

For example, Wiles' proof of FLT which you quoted as an example of "having no applications" directly lead to the resolution of Taniyama-Shimura conjecture. How's that for an application?

51. My results did not change the world, but they were implemented in commercial software (and I didn't even defend my phd yet).

So have mine yet I do not walk around with the false assumption that what I do with my systems hat on is somehow much more relevant to what I do with my theory hat on: both are minor contributions in a very large scientific effort.

Let's face it, the Googles and Akamais out there that have made a significant impact on the real world are the exception, not the rule. Quite interestingly one of those comes from the systems side (Google), the other from the theory side (Akamai).

Anyhow, this has gone for long enough, so I'm signing out.

52. Applicability, broadly defined**, is a necessary condition for good scientific research.

** applicable as in having impact on the real world or impact in other areas of science.

I am talking about practical applications in (what you call, somewhat naively) the "real world".
Such practical applications are neither necessary nor sufficient for a good scientific research.

53. My results did not change the world, but they were implemented in commercial software

Great! So you have made an impact on the market.
However, as I tried to point out earlier, it says nothing about your contribution to science (as, again, having practical applications is neither a sufficient nor a necessary condition for contributing to science).

54. Great! So you have made an impact on the market.

This was not claimed. Rather, it was said that:

My results did not change the world, but they were implemented in commercial software

55. I enjoyed the comments on this post.

I am currently an nth year grad student, and I have never really sat down with my advisors and talked about "what is good research", indeed we don't really talk about it very much at all even among the students.

So it is good to kick around the topic every once in a while and get different peoples ideas even if no conclusion is actually reached...