Computational Complexity is not a Spectator Sportmeaning that to truly understand and appreciate computational complexity research you need to be an active researchers yourself.
But we can't keep the attitude that computational complexity can only be appreciated by complexity theorists or we become closed and irrelevant. We need to sell complexity and the rest of theory to the scientific community and the public at large.
We can learn some lessons from great spectator sports like baseball. One cannot truly and deeply understand baseball unless you have played the game on a regular basis. But professional baseball knows they wouldn't exist without their fan base. They make the game interesting to fans at different levels of understanding, from casual fans who barely know the basic rules of the game, to sophisticated fans who understand the nuances of strategy.
While I will never expect to see us proving theorems in front of fifty thousand screaming fans, we should aim to make our work understandable and interesting to fans of theory who have different levels of knowledge of the field.
Maybe this will help:
ReplyDeletehttp://vnccasts.com/
It might be a good way to learn about all sorts of professions.
Want to know how to make it a spectator sport? Get some big results!
ReplyDeleteProbably most computer scientists find the incremental results of TCS uninteresting. On the other hand, the big results of TCS are very interesting.
I'm excited about Barabasi's book Linked, which is sort of a layman's intro to random graphs. I might be too close to the topic to have proper perspective, but I think it would make a good gift for the non-mathematician who is interested in math.
ReplyDeleteSomeone should write a book like it for TCS. Or is there one already out there?
There are several ways to make complexity a spectator sport. First one is make the presentation clearer. Non-determinism, while a useful paradigm, should not be way to introduce NP and NP completeness. In class, define NP as the class of problems that can be solved by the Google beowulf cluster using a program written in C together with a "fork()" instruction that activates another node. "You need to find the solution and you need to identify that you found the solution". They grasp this concept in minutes. We present several problems that are in NP together with their "proof" of this fact (ie we exhibit the par-program that solves the problem). Once kids understand this, we replace "fork()" with a "try()" instruction that slowly eases in the idea of non-determinism, as well as certificates. We then formally prove equivalence between all of these models.
ReplyDeleteDitto for Turing Machines, DFAs and other such. They seemed to be presented with an emphasis on notation (typical of the old European school of logic). Say a DFA should be defined in class as a directed graph with labeled edges and a starting node, and save the formal definition for the rare cases where it is needed.
TMs should be avoided altogether unless the student intends to on TM specific bounds. I can go on and on.
Hi Lance,
ReplyDeleteMany of us seniors are currently chosing among PhD programs. As you probably know, we are expected to come to a decision by April 15.
Would you mind sharing with us your advice on how an aspiring theorist should go about making this very difficult and important decision? I personally would find such a post very informative, and I'm certain many others would agree.
Thanks!
I recently came across the following show that seems to have been broadcast on Israeli TV in 1998:
ReplyDeletehttp://www.wisdom.weizmann.ac.il/~naor/harel.txt
This is a perfect example of how to make TCS a "spectator sport". Does anyone have or know where to get these (preferably in in digitial format)?
Anonymous Mar 27 10:46:23 wrote:
ReplyDeleteIn class, define NP as the class of problems that can be solved by the Google beowulf cluster using a program written in C together with a "fork()" instruction that activates another node.
No, by Gauss! This has no connection to nondeterminism, nor to polynomial time.
It also absurdly suggests that Google owns
an "NP machine." Beowulf clusters, C and
threading are completely irrelevant.
If you must give a "dumbed down" definition,
NP is the class of problems "whose solutions
have short proofs of correctness" while P
is the class of problems "where these proofs
can be found quickly." This ought to do for
a cocktail party. If you're teaching a class,
take the time to teach them the required
background, then give a proper definition.
For the college seniors considering grad school:
ReplyDelete#1 Find an advisor you click with. This is the most important thing about graduate school. It is very helpful if this person is tenured and not putting too much time into an outside venture. I've known people who have lost advisors in the middle of grad school because the advisor did not get tenure or the advisor left to work in industry.
#2 Follow the money. Better support means more time to do research and more possibilities for travel to conferences and workshops. Teach some, but not so heavily as to slow you down. Internships should be for connections and experience, not for financial support. In the worst case, I've known people whose advisors lost all funding and the student had to get a new advisor.
#3 After you and your advisor, your fellow grad students will have the most effect on your grad school experience. They should be energetic and intelligent, and hopefully not competitive in the bad way. It would be very good if some have interests close to yours.
#4 Consider the prestige of the department but don't let it trump the other points. The prestige of the department is worth considering mostly as an indicator for other more important factors (especially points 2 and 3). Not all highly ranked departments do all specialties, and some are ranked highly only because rankings are lagging indicators. But, when all other things are equal, it can't hurt.
#5 You will probably be spending most of the next 4-7 years of your life in graduate school. It would be worthwhile to find place that is good for living your life.
----------------------------------
#1 is by far the most important, but it is hard to know this before you select an area to work on. In such situtations, look for large departments with groups of professors with which you could possibly work.
If you are reading this blog, what you really care about are the places with multiple high-energy world-class theory of computation faculty who are taking on students.
I'm not going to try to rank them or list them all, that flame war would rage on for days.
Maybe the different schools looking for theory students could make recruiting pitches on this blog. Lance could set it up as a great big post...
Only after we've managed to sell computational complexity to the baseball fans, should we go for the ultimate challenge and try to sell it to the statistics and machine learning communities.
ReplyDeleteNo, by Gauss! This has no connection to nondeterminism, nor to polynomial time.
ReplyDeleteDon't worry, I do tell them "solvable" means "in polynomial time" and, by definition of the fork instruction, using at most 2^p(n) machines. We also need to discuss the idea of termination criteria, which eases in the concept of certificate. One can formally show that this is exactly the class NP.
I think that teaching NP using "fork()" instructions will clearly make the field vastly more accessible to the general public.
ReplyDeleteEven if you teach nondeterminism in terms of fork()-like branches (um, we already do that anyway... but I digress) you still can't get someone excited about P vs. NP.
ReplyDeleteImpagliazzo's Five Worlds paper should make people in AI sit up to the practical importance of the P vs. NP question. Many assume it's not important enough, thinking it's only about traveling salesmen or packing boxes!
But people just can't get too excited about P vs. NP because there isn't anything exciting about it. Decades of research, with little to show for it. That makes for a very slow moving game to watch. Even if you do understand the incremental results, you have to be the type to get excited about them. That describes the current set of TCS researchers.
But once the P/NP issue is resolved, you better believe lots of people are going to be excited about theory. However, in five to ten years, we'll have internalized the result, and it will no longer be exciting again. Just like Goedel's proof, if may even create a paradigm shift... but once you're in the new paradigm you get used to it.
For a layman to dabble in the field, it would be much better to go toward the deep philosophical issues that are a result of theoretical computer science. The Five Worlds is a good example, same with that one paper that goes around the topic "maybe P != NP is hard to prove because what reality would be like if P != NP." The Simulation argument could also be recast in more computational terms.
In class, define NP as the class of problems that can be solved ... using a program written in C together with a "fork()" instruction that activates another node.
ReplyDelete----------------------
I think that teaching NP using "fork()" instructions will clearly make the field vastly more accessible to the general public.
-----------------------
Even if you teach nondeterminism in terms of fork()-like branches...
I begin to identify a bit with Scott Aaronson. Even obvious sarcasm seems to be lost on blog posters.
I think that teaching NP using "fork()" instructions will clearly make the field vastly more accessible to the general public.
ReplyDeleteTo the general public one should use an even more simplified description, eg. a search in which you ask two friends for help, and they tell two friends, and they tell two friends (cue in split screen image going from one to four to eight) and so on. But as Ian Stewart pointed out, explaining science to the general public requires "white lies" that mathematicians (and theoretical computer scientists) are generally very uncomfortable with.
A physicist---in contrast---has no problem explaining newtonian physics to a child without once talking about relativity.
Many of us seniors are currently chosing among PhD programs. As you probably know, we are expected to come to a decision by April 15.
ReplyDeleteI suppose the upside to getting rejected by all the programs to which I applied is that I don't have to deal with this problem.
There is a B.C. cartoon where one woman asks "why does our society pay its athletes so much and its scientists so little." The other woman replies: "would you pay to see a scientist?"
ReplyDelete====================
ReplyDeleteLance wrote:
"... we should aim to make our work understandable and interesting to fans of theory who have different levels of knowledge of the field."
Indeed. I have little interest in, and even lesser knowledge of, the PvNP problem.
Every time I have reason to refer to it - invariably in complexity theoretical terms, since that seems to be the language which best brings out its significance, and in which it is encountered, discussed, and understood, the most - I make an ass of myself.
Yet, I have just arXived a paper titled "P =/= NP"!
Which illustrates the point Lance made.
The argument in my paper is expressed in terms that are familiar to, and within the grasp of, any mathematical logician.
I doubt, however, whether a complexity theorist would easily recognise the argument as pertaining to, leave alone being capable of settling, a central question of complexity theory.
The reason:
It has been authoritatively asserted that the PvNP problem has many equivalent formulations, one of which is purely logical.
All I have argued is that, if this, last, equivalence is valid - which, given my ignorance of complexity theory, I am not competent to verify - then there is a constructive, and intuitionistically acceptable, interpretation, of classical Peano Arithmetic, under which P =/= NP.
Now, whether my particular argument is validated or not, assessing its value simply on the basis of its inaccurate, or poor, understanding, of complexity theory can hardly profit the theory.
I have little interest in, and even lesser knowledge of, the PvNP problem...Yet, I have just arXived a paper titled "P =/= NP"!
ReplyDeleteWow. In what other field do people claim to solve major open problems without understanding them, or even being interested in them...?
Doesn't the number of cranks our field attracts illustrate its widespread interest?
I suppose the upside to getting rejected by all the programs to which I applied is that I don't have to deal with this problem.
ReplyDeleteWhere did you apply? Can you provide a link to your homepage?
There is a B.C. cartoon where one woman asks "why does our society pay its athletes so much and its scientists so little." The other woman replies: "would you pay to see a scientist?"
ReplyDeleteI thought men love with their eyes, women love with their ears. I would pay much more to hear a scientist. :)
Regarding "get some big results!" -- are the incremental results of other areas really that much more interesting? There are plenty of results in computer security that seem equally esoteric as incremental TCS results. (Not to say either one is bad, just requires background to understand.)
ReplyDeleteOn the other hand, even incremental results can be interesting if put in the context of the original motivating problem. Let us take as an example the question of whether P != NP implies the existence of one-way functions. Put less formally, we can state this as "Does P != NP mean we can do cryptography? If so, how much cryptography?" Motivating this question is easy, given the fact that the bulk of today's cryptography rests on unproven hardness assumptions.
There is a long line of work on the question. Just to mention two recent results, Akavia, Goldreich, Goldwasser, and Moshkovitz have a new paper on the topic in STOC06 and Pass is following up with another paper in Complexity06.
Still, for me, part of what makes the question come alive is the narrative Impagliazzo has for that and related questions in his "Personal View of Average-Case Complexity" paper. That helps me fit the recent results into context and gives me the motivation read the technical details -- and then I can appreciate the finer details of what the authors have done.
Actually, what I meant when I said, "complexity theory is not a spectator sport," is that you have to put in your own blood. Attending seminars and watching other people's results is like slurping the fat off the top of a bottle of milk. Or, better yet, a vial of blood. Getting things for free can be tasty, but it's your own sweat which allows you to achieve successive levels of appreciation. Time for a refill.
ReplyDelete