Idiot

CSP stands for COMPUTER SAVY PERSON. 25 years ago the following happened:

BILL: I can't get my computer to work.
CSP: Just push this button you idiot.
BILL: Thanks! That works!

15 years ago the following happened:

BILL: My awk program did not compile and in trying to find the error I found an example from the awk manual which did not compile.
CSP: Just use gawk instead of awk you idiot.
BILL: Thanks! That works! I don't think its idiotic to not know to use gawk.

5 years ago the following happened often:

BILL: My FILL-IN-SOFTWARE is not working, whats the problem?
CSP: We can find a work-around, but, by Rice's theorem, we can't find out what the problem really is.
BILL: Thanks!

Recently the following happened.

BILL: When I play a song on You-Tube I'm not getting sound.
CSP: That will take a few hours to fix. We need to INSERT TECHNO BABBLE.

When they were done sound worked, but many other things did not. And there were some things which I would call odd except that computers doing odd things is not odd. I fired up FIREFOX and a short time later OPEN OFFICE opened mysterious. There was a debate on this.

CSP1: I think FIREFOX is somehow linked to OPEN OFFICE.
CSP2: I think some weird combination of keys caused it.
BILL: Did I do something idiotic like accidentally click on some icon (this turned out to not be the case).

In the good old days computers were simpler. The staff would tell me I was an idiot and fix the problem! The staff now is 10 times better then they were then, 100 times more polite, but computers have gotten VDW(4,2) more complicated.

I miss being an idiot.

Meta Comment on FOCS/STOC comments

The comments on both Vijay's guest post and Lance's post brought out many comments about FOCS/STOC. People seem to have strong feelings and stronger opinions. Here is a list of questions this discussion has raised.

1. Is the community really driven by these conferences? An Underlying assumption of these discussions has been that someone judges us based on the number of STOC/FOCSs we have. Who is this mysterious someone? Is it our departments? Our Colleges? Ourselves? Granting agencies?
2. Is it bad that we are so judged?? PRO: Its good to have a central place where you know the good papers are. CON: The rest of the items on this list are about what problems there are in judging quality CON: Some of these papers are never put into proper journal form. CAVEAT: Is the Journal-Refereeing system all that good to decry that it is lacking here?
3. Other fields do not have high-prestige conferences- why do we and is it a good thing?. Our field moves fast so we want to get results out fast. It is not clear that FOCS/STOC really do this. Using the web and/or Blogs can get the word out. Important new results in theory get around without benefit of conferences. For results just below that threshold its harder to say.
4. Are the papers mostly good?
5. Is their a Name-School-bias? Is their a Name-person-bias? Some have suggested anonymous submissions to cure this problem.
6. Is their an area-bias? There are several questions here: (1) is the list-of-topics on the conference annoucement leaving off important parts of theory? (2) is the committee even obeying the list as is? (3) have some areas just stopped submitting?
7. Is their a Hot-area-bias?
8. Is their a mafia that controls which topics gets in?
9. Is their a bias towards people who can sell themselves better? To people that can write well?
10. Is their a bias towards making progress on old problems rather than starting work on new problems?
11. Is their a bias towards novel or hard techniques?
12. Is it just Random? Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random? One suggestion is to make it pseudo-random by using the NW-type generators. This solves the problem in that since it really is random it is less prestigous and most of the problems on this list go away. Would also save time and effort since you would not need a program committee.
13. Are there many very good papers that do not get in? It has been suggested that we go to double sessions so that more get in. If the quality of papers has been going up over time this might make sense and would not dilute quality.
14. Is 10 pages too short for submissions? This was part of Vijay's Video Suggestion. Are figures and diagrams counted for those 10 pages? If they are they shouldn't be.
15. Are many submissions written at the last minute and hence badly written?
16. Are many submissions written by the authors taking whatever they have by the deadline and shoving it into a paper?
17. Since the conference is about all of theory, can any committee do a good job?Vijay was partially addressing this problem by trying to find a way to make their job easier.
18. Do other conferences have these problems? That is, the more specialized conferences- do they have similar problems? Why or why not?
19. Do you actually get that much out of the talks? If not then it is still valuable to to go for the people you meet in the hallways?
20. For all the items above, even if true, are they bad? Some have suggested that bias towards big-names is okay.

Any proposed change in STOC/FOCS (or other conferences) should have the following:

1. State clearly what problem you are trying to solve. If it is a new problem there may be a bias against it.
2. Prove that it really is a problem. The proof has to use novel or difficult techniques.
3. State clearly what your solution is and proof that it works. The proof can be a sketch; however, if you are a big-name or from a big-name-school then people will pay more attention.
4. Comments to your suggestion must stay on topic. A referees report would never say: `The author showed that 3-colorability can be approximated well; however, the really important problem in this field is set cover, which can be shown to not be approximated by the following.'' But a comment on a blog often says things like: ``Vijay is addressing one problem with STOC/FOCS, but the real problem is ...''

Radical change to Conferences by Vijay Vazirani

(Guest Post by Vijay Vazirani!)

The processes of submitting FOCS/STOC abstracts and conducting PC meetings have undergone numerous changes since the good old days when you received your acceptance letter by US Mail and a couple of weeks later you received a huge rolled-up bunch of poster-sized papers on which you were supposed to glue your paper and mail back. There is little doubt that these changes have improved efficiency and fairness a great deal.

I would like to propose another, somewhat more radical, change that is now technologically feasible -- allowing people to submit, together with their 10 page abstract, a 10 (or 20?) minute video describing their result. The video will be optional, at least in the beginning.

They say a picture is worth a thousand words -- if so, a 10 minute video is worth millions! Imagine, as a PC member, how much easier it will be to read an abstract after you see a short video explaining the problem, the approach, and the main new ideas, and how much more "correct" your evaluation of the paper would be! In my opinion, this will greatly improve quality of the paper acceptance process. Many people complain that the latter is currently broken -- a large fraction of the decisions are nothing more than the flip of a coin or are left to such chance events as who reviews the paper or the constitution of the PC.

Many objections can be raised to this idea. Let me anticipate a couple and try to counter them. First, this change is feasible today -- if you need proof, just take a look at YouTube! Another objection is that this may give an advantage to some members of TCS community -- those who can give better talks. But then, they are precisely the people who are also better at writing clearly and already had a huge advantage. In fact, in my opinion, relatively speaking, the enhanced process will be a great equalizer -- giving a chance to people who don't have good writing skills to still be able to sell their wares.

Needless to say, this is a major change and it deserves an extensive discussion before it is implemented. I hope this blog will provide that opportunity.

Getting an 8-year old interested in math:Do's and Don'ts

I recently visited my nephew and his five kids and tried to get my 8-year-old great nephew Justin interested in some math. I told him that I am thinking of a number between 1 and 100, and he should ask YES/NO questions until he guessed it. Try to ask as few questions as possible. His first three questions were as follows.

• Is it bigger than 20? (YES)
• Is it even? (YES)
• Does it have a 7 in it? (NO)
• Is it 80? (NO)

It took him 20 more questions to get it. I bet him a quarter I could get his number with 10 questions. I succeeded and he had to beg his dad for a quarter. I've been told he has learned not to gamble with Uncle Bill. His father told me that the concept of `try to make every question cut the number of possibilities in half' was over his head since he has not learned fractions yet.

I then tried NIM-games. There are toothpicks on the table and you can remove 1 or 2. The players alternate. The player who removes the last toothpick WINS. He played his sister Jordan (who is nine) with different numbers of toothpicks on the table. They DID catch on that if the number of toothpicks is 3,6,9,12, ... like that, then Player II wins, otherwise Player I wins. They then did NIM with removing 1 or 2 or 3 and also 1 or 2 or 3 or 4, They learned the trick and the pattern. They liked it and learned some math.

I do not know if this is indicative, but it may well be that if a kid has not learned fractions yet, binary search may be over his head, while NIM games is fine and fun.

Warning: I once tried to teach my 6-year old nephew Michael that, when doing multiplication, the order does not matter.

BILL: Say you had two pans of brownies. One is 3 by 5 and the other is 5 by 3. Then---

MICHAEL: Do you! I love brownies!

We didn't get much math done ...

Knuth Prize goes to Nancy Lynch

The Knuth Prize for 2007 was announced: Nancy Lynch. The formal announcement is here. The Knuth Prize is awarded for a lifetime of work in the foundations of computer science. This is in contrast to awards that are for one work (e.g., best paper at STOC). A best paper award can look silly 10 years later; however, a lifetime-of-work award has much less chance of that. The Knuth Prize is $5000 plus $1000 travel expenses to go pick it up. Do they make you fill out forms and give them your receipts? This is a small amount of money as prize money goes. The Knuth Prize is given out every 1.5 years, so saying that Nancy Lynch is the `2007 winner' isn't quite right. Donald Knuth has never won the Knuth Prize, though he certainly should. Is he eligible? Previous winners are below. Impressive bunch!

1. 1996: Andrew Yao
2. 1997: Leslie Valiant
3. 1999: Laszlo Lovasz
4. 2000: Jeffrey Ullman
5. 2002: Christos Papadimitriou
6. 2003: Miklos Ajtai
7. 2005: Mihalis Yannakakis

Complexity 2007- BE THERE!

The website for Complexity 2007 is up now (its been up for while) CCC08. In 2007 it is part of FCRC, a set of conference including STOC. Should you go? YES if you can. Should you also go to STOC or part of STOC. YES if you can. Advice:

1. Register and book hotel early and try to stay in the conference hotel.
2. Air travel: There used to be some rules-of-thumb like `fly over a weekend for a better price' or `book early or `book late' or `fly airline XXX' or ... None of these seem to be consistent anymore. One rule-of0thumb- if you see a good price grab it since it may go away.
3. DO NOT CHECK BAGGAGE. Saves time on both ends and saves the time and hassle when they lose it.
4. Look at the program ahead of time and download and read some of the papers ahead of time. This way you can follow those talks pretty well. (Papers likely on authors websites or EEEC but not necc.)
5. Bring a notebook and a clipboard OR a labtop so that you can take notes on talks and things you hear in the hallways.
6. Its a cliche to say `you learn more from talking to people in the halls then at the talks' While you certainly learn alot this way, the talks are also valuable. Not so much because you will learn the latest results and their proofs, but so that you'll know whats out there.
7. How many talks to go to? Going to all of them is tiring and leaves less hall-time. Pick talks that you already have some very basic knowledge of OR want to get into. IF you are looking for things to work on, go to more talks. If your plate is already full, go to less talks.
8. The following is typical and should not be underated: You only understand the first 3 minutes of a talk BUT you get awareness of a new area and some references to look at.
9. When you get home follow up on the topics that peaked your interest.

What to make of the Ind of CH ?

Dave Barrington suggested I blog about Paul Cohen since he just died. Scotts Blog already reported on Paul Cohen's death, and there were many comments on C^* algebras and PAC learning (none of which Paul Cohen worked on). Paul Cohen's most important result was that CH is independent of ZFC. What does this mean and what do we make of it? CH is the statement there is no cardinality strictly between N and R ZFC is Zermelo-Frankl Set Theory (with the Axiom of Choice). Virtually all of Math can be derived from these axioms. (There are quibbles about this which might be a latter blog.) Kurt Godel showed that there is a model of ZFC where CH is TRUE. Paul Cohen showed that there is a model of ZFC where CH is FALSE. Together we have that CH is INDEPENDENT OF ZFC. What to make of this? Here are opinions I have heard over the years:

1. (Mathematical Realism or Platonist) There IS a model of the reals that is the RIGHT one.In that model CH is either true of false. ZFC just isn't up to the task of figuring it out.Paul Cohen thought that there were an INFINITE number of cardinalities between N and R.I've heard rumors that Kurt Godel thought there was exactly ONE cardinality between N and R.Hugh Woodin has some mathematical reasons to think there is exactly ONE:CHone CHtwo. Many people prefer the simplicity of having NONE---the infinity after N is R. Some people think that we need to add new axioms to ZFC such as Large Cardinals or the Axiom of Determinacy to settle the question. Are these really candidates for axioms?That may be a later post.
2. (Not sure what these people are called.) Since ZFC settles virtually everything else in mathbut not this question, CH has no answer. There is No `correct' copy of the reals.The weakness in this response may be the virtually. Are there questions in math that need it? Are there such questions outside of Set Theory? That may be a later post.

What do you think? ~