Coda to idiot-post

Coda to idiot.

1. The posting idiot was a test case for the newly-fixed mechanism to email posts to people (some people had been getting this blog via email instead of going to the web.) It did not work. Nobody knows why.
2. I had written:

   computers have gotten VDW(4,2) more complicated.

   One of the comments was:

   For the "Ramsey-theory idiots" out there, the technical translation of VDW(4,2) is "I don't know exactly how much more complicated computers have gotten, but its a while hell of a lot!" :-)

   The commenter is correct in clarifying what I meant; however, both the commentator and I are incorrect in the details. Inspired by the commenter, I looked up what is known about the VDW numbers. VDW(4,2) is known and is only 35. VDW(5,2) is known, and is only 178. I should have written VDW(5,5) which is unknown but quite likely quite large.
3. VDW(k,c) is the least number W such that no matter how you c-color the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15 is 4 numbers equally spaced) that are the same color. W(k,c) exists by van der Waerden's Theorem. See van der Waerden's Theorem-Wikipedia or van der Waerden's theorem-my posting in Luca's blog
4. I believe the only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005.
   1. VDW(3,2)=9, (easy)
   2. VDW(3,3)=27, (Chvátal, 1970, math review entry, article not online.
   3. VDW(3,4)=76, (Brown, Some new van der Warden numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432. Article, review not online!
   4. VDW(4,2)=35, Chvátal ref above
   5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!

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? ~

The Complexity Blog Lives!

Various people have urged Lance to keep the Blog going, perhaps under new management. Some have suggested Bill Gasarch (me) . Some have suggested anyone except Bill Gasarch. Lance flipped a coin and it came up with anyone but bill gasarch . However, not one to leave things to random chance, Lance offered me to take it over, and I accepted.

PROS: The blog will live!
CONS: It will have far more capital letters.
CONS: Fewer postings, probably twice a week. But that how Lance started.

I am honored to carry on the tradition, and will have my first real post next week. bill gasarch

The End

After 4 1/2 years and 958 posts I have decided to retire from blogging. No weblog can go on forever and I would rather end on my own terms than let the blog peter out.

Thanks for reading.

Turtles

Today a new Teenage Mutant Ninja Turtles movie opens. The turtles were quite popular back in the late 80's and early 90's, somehow making appearance in more than a couple STOC and FOCS talks. Seemed the rule to avoid popular culture in talks doesn't apply to children's shows.

Then the turtles started winning NSF Math Postdocs: Michelangelo (Grigni), Raphael (Ostrovsky) and Leonardo (Schulman). Poor Donatello never did get his postdoc.

Laws, Taxes and Computer Science

So if I get a number of P=NP and P≠NP "proofs" what do the law professors get? A long email argument that most income tax is illegal. I'll spare you the full email (but if you are really curious here is the website).

How do I know about the email to our law faculty? Because the message was cc'd to the CS faculty because of the following line:

I know that some people aren't comfortable using a computer. If you need help with a computer to search the tax code (US Code, and Code of Federal Regulations), perhaps one of the computer science faculty can assist you.

I don't hold much credence in his legal arguments but I know for sure he has no clue about computer science.

FCRC: Registration, Visas and Hockey

The Federated Computing Research Conference (FCRC) has opened registration and housing. FCRC, held June 8-16 in San Diego, is a mega-conference including STOC, Complexity, COLT, Electronic Commerce (EC), SPAA, and a few non-theory conferences as well.

Early registration deadline for the conference is May 11 and the hotel rooms are being held until May 9. It's recommended to make the hotel reservations as early as possible.

For registration, you pay a single fixed FCRC Fee and then a separate registration for every conference you attend. You are allowed to attend talks in any conference held during the same day you are registered for some conference. Tutorials and workshops are closed, though we are trying to open up the EC workshops.

If you need a visa, read this and apply now. The US visa process can take months.

Catherine McGeoch, the self-proclaimed ToC Hockey Commissioner, tells us the theory community has been challenged.

The computer architecture community (which attends ISCA) has challenged the theoretical computer science community to a "friendly inter-league" hockey game, to take place during FCRC. They will make local arrangements — we just have to get up a team.

If you are attending FCRC, and can pass as a theoretician (and/or as a hockey player), you are hereby invited to sign up for the now-forming ToC Hockey team. Tell all your friends to sign up, too.

I remember long ago in graduate school playing (badly) for the MIT theory group's intramural team, Execution Time. Now I can't even keep up with my eight-year old daughter.

Theory Program Director

The NSF has posted a search for a new theory program director to take over after Bill Steiger's term expires this summer. The program director plays a critical role for our community, running the panels for theoretical computer science grants and administering those grants, working with other program directors and the CISE leadership in establishing the funding directions of current and new programs and generally acting as an advocate within NSF for theoretical computer science. Most universities are very willing to give a leave for these positions and the NSF will typically cover your current salary.

Bob Sloan, program director in 2001-2002, wrote The Joys of Being an NSF Program Director for the latest SIGACT News.

If you have an interest not only in what we do, but also in the process and policy issues of what we do, then you too might really enjoy spending a couple of years being a program director. At many universities, definitely including mine, the whole funding process is a major component—perhaps the single most important component—in determining who will get tenure, promotions, etc. As somebody interested in process and policy, I really enjoyed getting to see how this system works from the inside.

Not only is NSF an interesting place, it is a highly purpose driven place. As faculty, we are called on to do many, many different tasks, some of which seem to have a clear goal, and some of which, well, leave one scratching one's head. One wonders, depending on where one is and who is the Dean/Provost/etc. any given year: Is the goal really to educate the masters students, or rather to keep them happy enough that we keep making money from them? NSF has one of the clearest goals possible: find the absolute best research to fund. (There can be huge disagreement about what is the best research, of course, but there really is not any disagreement about the underlying goal.)

Being a program director also gives you the ability to provide two good services to your research community. First, you have some ability to drive the direction of the research community. Second, you get to run the best, fairest competitions for funding possible. There is really quite a difference between the best panel run by somebody who knows the research area, knows who are likely to be good panelists, and is good at managing such things, and a panel run by an outsider who is a fair to middling manager of such things.

So if you would like to spend a year or two in DC and make a real impact for theoretical computer science, please consider applying.

A Computer Scientist in Jeopardy

The long-running Jeopardy television game show had a first on Friday, when all three players ended up tied for the first time.

The three contestants on the venerable game show all finished with $16,000 after each answering the final question correctly in the category, "Women of the 1930s," on Friday's show. They identified Bonnie Parker, of the famed Bonnie and Clyde crime duo, as a woman who, as a waitress, once served one of the men who shot her…The show contacted a mathematician who calculated the odds of such a three-way tie happening — one in 25 million.

In that final round contestants choose how much of their winnings to risk, so it is impossible to give a probability in such a setting. It's more an issue of simple game theory.

Before the Final Jeopardy round the totals were $13,400, $8000 and $8000. Both of the $8000 decided to risk all of their money so they wouldn't be overtaken by the other one.

The $13,400 belonged to Scott Weiss, a computer science professor at Mount St. Mary's University in Maryland. Since $13,400 is between 1.5 and 2 times $8000, the standard strategy is to bet enough so that if you win you have more than $16,000 and if you lose you have more than $8000, for example betting $3000. Had Scott done so, he would have taken home all his winnings and come back for the next show.

Instead Scott bet $2600, leading to the $16,000 tie. By doing this, Scott gets to take home all his winnings and comes back for the next show.

It takes a computer scientist to make the most conservative bet, knowing that the rules of the game give no particular advantage to winning over tying and leading to the first three-way tie ever.

A Place for Open Problems

A readers asks where he can put his open problem on the web. Back in the late 80's we had three Theorynet mailing lists. Theorynt-A announced major conferences, Theorynt-B announced local workshops and Theorynt-C had everything else including various questions people put out to the community. But now we have only one Theorynt only announcing conferences and the volume of a Theorynt-C type list today would overwhelm anyone trying to read it.

We need some Web 2.0 system. A blog or wiki to post the problems. A tagging method to mark the area and status. A voting system to rank the importance of the problem. A commenting system for discussion. A sophisticated RSS system for tracking. A visual appealing and simple interface. And most importantly someone willing to put it all together for no compensation beyond the thanks of the community.

From Toronto to Chicago to Basketball

I just returned from visiting the University of Toronto, my first visit to the campus in 18 years. I spent much of my time talking to the same people I did back then, Charlie Rackoff, Steve Cook and Faith Fich (now Faith Ellen). Also former NEC postdoc and current Toronto prof Avner Magen and my former student Rahul Santhanam visiting there for the spring.

The biggest news in Canada is happening in Chicago, the trial of Lord Conrad Black, but it barely makes the news here. Phil Rosenthal of the Chicago Tribune wrote today about the non-story. The big news in Chicago is a 73 degree day yesterday, Mayor Daley's wrangling to get the 2016 Olympics in Chicago and, of course, March Madness.

What speaks math more than the NCAA Men's Division I Collegiate Basketball tournament that gets underway tomorrow. First you have a beautiful binary tree published in all the US papers (and Canadian ones too) and filled out by millions in their office pools. Nothing like a single elimination contest to explain exponential growth, 64 teams need only 6 rounds to find a champion. Technically they have 65 teams now, and they needed an extra single-game round yesterday to get to the 64 remaining teams.

The tournament draws more betting, legal and illegal, than any other event (though the Super Bowl draws more for a single game). These bets lead to predictions. With sites like Tradesports you can get prices on securities that give you estimated probabilities. Not absolute probabilities but those who use the markets to fill out their office pools likely won't do too poorly, even with no understanding of college basketball.

When Technology Doesn't Change

My 6th grade daughter takes the ISATS (Illinois Standard Achievement Tests) this week, tests meant more to evaluate the school than the students. Despite the amazing changes in computer technology, she takes the exam the same way I did for the equivalent tests in the 70's, filling in ovals with a Number 2 pencil.

In my lifetime we've sent a man to the moon and music has moved from records to 8-tracks to cassettes to CDs to MP3 players. But what hasn't changed. The vast changes have been in computation and communication, but transportation remains mostly the same. Airplanes fly as fast now as they did in the 60's using the same basic jet engine technology. Most cars still run on the combustion engine and remain grounded. Elevators, escalators and sidewalks where people still walk. We really haven't changed how we get from point A to point B.

We still read our books on paper and write with ballpoint pens. Locks are mostly split cylinders. They still haven't invented a good mouse trap or cured the common cold. And let's not forget the greatest device devised by man: Saran Wrap.

The Tenure Process

A reader asks how the tenure process works in US universities. I will describe a typical case but the system works differently depending on the particular school, department or candidate.

Junior faculty are hired as assistant professors for a four-year term. After which they are usually renewed for an additional three-year term. At the of that second term either they are promoted to associate professor with tenure or their contract is not renewed and they need to find another position.

An assistant professor is hired based on potential and promoted to tenure based on accomplishment.

It is rare to not renew a candidate after the first term, happening only if the department feels there is little chance that the faculty member will received tenure after second term.

Since tenure requires a long-term commitment from the university, the department, the dean and the university put considerable effort in vetting the case. The candidate first puts together a tenure packet, with CV, detailed research and teaching statements, a collection of publications and list of potential letter writers. The department sends the packets to senior people in the field both on and off the list given by the candidate. Ten or more review letters are not uncommon for a tenure case. The tenure case works its way through the system from the senior members of the department through the dean, provost and so on. Many universities have a tenure committee that reviews all cases for the provost or president.

The final decision is based on several parameters including the letters, publications, teaching, grants, service to the university and academic community and how well the faculty member fits in the department. The weights given to each item as well as how high the tenure bar is held differs greatly between universities. You can get a good feeling by how recent tenure cases went in the department.

Can one come up for early tenure? Can one get credit for years as a postdoc, research scientist or an assistant professor elsewhere? Or can one "stop the tenure clock" for illness, a new child or other leaves of absences? Can one be promoted to associate professor without immediate tenure if needed? Can one get an extra year to search for a new job if not promoted? Will the candidate have access to the review letters? If the answers to these or other questions concern you, best to bring them up before you accept the job.

Pure Evil

A conversation I had with a graduate student, maybe ten years ago.

Student: I hear Bill Gates wants "P ≠ NP" proven at Microsoft and is hiring smart mathematicians to do so.
Me: All the power to him.
Student: How can you say that? Isn't Bill Gates pure evil.

There is a tendency among many academics to think of the world in black and white and in particular consider some people or institutions truly evil. Elsevier, George Bush (and Republicans in general) and the RIAA only desire to destroy everything good about academic publishing, the US, and personal freedom respectively. Bill Gates certainly used to be in that category but has softened now that Microsoft has lost some dominance and hires many of our friends.

Scientist tend to believe the world works by simple rules and we reinforce these viewpoints by only hanging out with other scientists like ourselves. The Internet has only made things worse, as we tend to only read stuff written by people who already agree with us.

I certainly don't defend all the policies of Elsevier, George, and the recording industry, but they don't have agendas of evil and in fact often have the same long-term goals that many of us share. We don't always share the same strategies but it would be better to work with them then to shut them out entirely by having no faith that they can do any good.

Bit Pieces

The Electronic Commerce accepted papers have been posted. EC will be held as part of the FCRC in San Diego in June. EC has also announced workshops on Networked Systems/Incentive-Based Computing, Prediction Markets and Data Engineering Issues in E-Commerce and Services which you can still submit paper to.

Carnegie Mellon will host OurCS: Opportunities for Undergraduate Research In Computer Science,October 5-7 for undergraduate woman. In addition to providing the participants opportunities to network, to meet role models, to learn about graduate school and jobs in CS, the conference will be unique in that undergraduate student teams will be embarking on research projects led by researchers from industry and academia. There will also be opportunities for students to present their own work as well as team results.

DIMACS in New Jersey is now hosting the Homeland Security Center for Dynamic Data Analysis (DyDAn), which plans to develop techniques to analyze massive flows of data arriving continuously over time. DyDAn should give theoretical computer scientists and discrete mathematicians the opportunity to put much of their research into practice as well as develop new theoretical tools.

In more DIMACS news, Rebecca Wright will become the new Deputy Director of DIMACS with the eventual plan to succeed Fred Roberts as director. I'm sure Rebecca will do a great job but she has a tough act to follow.

Jumping in Space

A fun fact from a McDonald's Happy Meal bag.

You can jump six times higher in space.

What does "jump" or "higher" mean in space? Given the pictures on the bag I believe what they meant to say was

You can jump six times higher on the surface of the moon than on the surface of the earth.

Ask the Astronomer agrees since the ratio of gravity on the moon and the earth is about 1/6th. Is that correct? Not quite. In a 1973 Physics Teacher note, Van Neie fixed the mass M of a person and the force F the person exerts to get a height ratio of

(6F/Mg -1)/(F/Mg-1)

where g is the gravitational constant. This does approach six in the limit but only "if the force F is several times the individual's Earth Weight, an unrealistic assumption." If a person exerts twice his earth weight when he jumps, he will jump 11 times higher on the moon.

See what you can learn eating at McDonald's.

Goodbye CompUSA

CompUSA, the "computer superstore", is closing more than half of its stores including all of them in the Chicago area. Tough competition came from many directions: Internet retailers, big box electronics stores like Best Buy and Circuit City, and price wars from Office Depot and Walmart. Despite having a CompUSA store a few blocks from me I rarely went there, though it was useful to quickly get a new fan for my PC when the old one died.

What does the closing of CompUSA have to do with computer science? Absolutely nothing, and yet everything. Computers have gone past devices you had to understand, ripping them open to add memory and other components. Now they get sold as a commodity not much different than televisions.

We do still have computer stores nearby. The local mall has an Apple Store and a Dell kiosk. But these are just showrooms, ways to exhibit their products, not places to go to get nuts and bolts to keep the computers going.

A field "Television Science" would never have flourished, but unfortunately many young people view Computer Science in a similar way today. That does not bode well for the long-term future of our discipline.

Inductive Turing Machines

On last week's Numb3rs episode One Hour, Charlie, the mathematician, and Amita, his colleague/girlfriend, had the following conversation:

Charley (to Amita): I haven't seen an inductive Turing machine used like that before.
Amita: I'm trying to find the finite state machine for these. (points to screen)

So what is an inductive Turing machine? I put the question to Bill Gasarch.

If you IGNORE the TV show, it could mean the following, taking a cue from the field of Inductive Inference:

A set of computable functions S is in EX if there is a TURING MACHINE M such that for all f in S if you feed f(0), f(1), f(2), … into M, it outputs e₁, e₂, e₃, … and in the limit the sequence converges to e, a Turing Machine index for a machine that computes f. Such a machine M is called an INDUCTIVE TURING MACHINE.

Does this definition make sense in context of the show? The set S of regular languages (those computed by finite state machines) is in EX, where e_i is the lexicographically least FSM whose output is consistent with f(0), f(1), …, f(i-1).

Of course this is an incredibly inefficient way to learn regular languages, but then again Amita wasn't having much success. Perhaps she should have used one of the efficient finite automata learning algorithms like Rivest and Schapire.

Gasarch has a different take.

The show DID NOT mean this. So what did they mean and what could they have said? They should have either used a generic term for learning or just use a fictional term. Then they can't really be wrong. Here are some possibilities:

1. Charley (To Amita): I haven't seen that learning algorithm used that way before.
2. Charley (To Amita): I haven't seen Carl Smith's Technique used that way before.
3. Charley (To Amita): I haven't seen cross-convergence used that way before.

Or they could have made Charley's comment and Amita's Answer match better:

Charley (To Amita): I haven't seen the Generalized Polynomial Hales-Jewitt Theorem used that way before.
Amita: I'm trying to prove the polynomial van der Waerden's theorem over the reals.

The conversation they DID have is connected to later in the show when they are trying to learn the maze. I can make a vague connection–the show did not do so.

Having said all that, it was a good episode.

By the way you can watch Numb3rs on-line for free.

Time to Cash It In

The US tries again with a new series of one dollar coins but will again fail since we still have the dollar bill. I have heard calls for eliminating the dollar bill and the penny since I was a kid and we have had over 300% inflation since then. Americans are no more likely to give them up than their yards and gallons.

So how about something more radical? Let's give up currency all together. No more coins. No more bills. I use electronic transactions, mostly my credit card, for nearly all purchases now. Many places don't require a signature for under $25, making the transaction faster than cash. I don't even slow down to pay tolls anymore on the Illinois Tollways. Surely we can make that final push to remove cash from the rest of the transactions.

We certainly have the technology today to eliminate currency. There will be some costs involved but with the savings for the government, banks and businesses of not having to deal with cash, we should be able to supply all Americans and visitors with smart cards. We can even put pictures of presidents on the cards to keep with tradition.

Avoiding the Two-Body Problem

The two-body problem, finding two academic jobs in the same city, is becoming an epidemic in American universities. Some administrators have estimated nearly half of all new junior hires have some sort of two-body problems that needs to be solved. Many academic couples settle for jobs at places not as strong as either could have found independently.

Why have we seen an increase in the two-body problem? There is less of a gender imbalance in Ph.D. students, particularly in the sciences, than in the past. Most Ph.D.'s spend nearly all of their working and social lives with their fellow students and romantic entanglements naturally develop.

How do you avoid the two-body problem? Find yourself a non-academic partner. You may spend the rest of your working life spending time with academics, do you really want to spend your non-working life with them as well? You have to work to find a non-academic partner. Join some clubs, preferably outside the university, that match your interests. You'll meet people who share at least one interest with you. Use the on-line dating sites, let friends set you up. It will take some work to find a partner but maybe you'll fall in love with some nice MBA. That's what happened to me.

Of course you may just end up in an academic couple. After all, you just can't stop true love.

On NP in BQP

In the wake of a misleading Economist article on the D-Wave quantum computer, Scott argues why he believes quantum computers cannot efficiently solve NP-complete problems, i.e., that the complexity class BQP does not contain NP. Let's look at that question purely from a computational complexity viewpoint.

Ideally we would like a mathematical proof that NP ⊄ BQP. But any such proof would imply P≠NP, one of the great open problems in mathematics.

Moving on, complexity theorists give evidence that a statement Q is false by a "Pigs Can Fly" argument, by showing that Q implies something else we don't believe. For example

• If there are sparse NP-complete sets then P=NP.
• If NP has efficient probabilistic algorithms (NP⊆BPP), then the polynomial-time hierarchy collapses.
• If good pseudorandom generators don't exist then exponential time has small circuits.

But we don't have any known consequences of NP⊆BQP.

What we do have is the result of Bennett, Bernstein, Brassard, Vazirani that BQP can't solve black-box NP problems, a relativized separation of NP from BQP. Relativized results like this don't tell us whether or not a statement is true, just that any proof that NP in BQP would require nonrelativizing techniques. So the sentence from the Economist article

In principle, by putting a set of entangled qubits into a suitably tuned magnetic field, the optimal solution to a given NP-complete problem can be found in one shot.

does not reflect current knowledge.

Can one have a nonrelativizing proof that NP is in BQP? We do have precedent. My very first theorem gave a relativized world where co-NP does not have interactive proof systems. We published the result in a 1988 paper Are there interactive protocols for co-NP languages? and we conjectured the answer was no. We were wrong.

But so far interactive proof and related systems have been the only source of reasonable nonrelativized proof techniques that we have seen in computational complexity and we haven't had any success using this algebraic structure of arithmetized satisfiability to make efficient quantum algorithms for NP problems.

I do conjecture that NP ⊄ BQP and most computational complexity theorists would agree with me. But until we see some negative consequences of NP in BQP, computational complexity theory has so far failed to give any real evidence that NP ⊄ BQP. We believe that NP ⊄ BQP for the same reason we believe that there are no probabilistic polynomial-time algorithms for Factoring—despite considerable effort, failure to find any algorithmic techniques that might solve the problem.

Organizing the Academic Job Market

The Economists have a Job Market Wiki listing interviews and offers in mostly academic economics departments. The wiki is far from complete and likely not entirely accurate but it does allow candidates and departments to see how the competition is doing.

This year the American Economic Association started a signaling process where each candidate can signal interest in up to two departments through a centralized AEA web site. The AEA also organizes a meeting each January whose main purpose is to provide a centralized location for job candidates and departments to have short interviews with each other.

In the computer science job market, departments start off interviewing similar sets of top candidates and until those settle do schools start looking at the next tier of still rather strong applicants. The CS academic hiring season starts in January and often lasts through June or later and this year is shaping up to be no exception.

Structurally the fields of computer science and economics have much in common—culturally diverse fields from the very theoretical to the very applied. But when it comes to the academic job market, economics and most other fields have a structured process that streamlines the search while CS remains quite ad hoc. Computer science needs some central authority to bring some organization to the process but beyond posting paid listings, the ACM and CRA currently do little to facilitate the hiring process.

Henzinger on Algorithms

A reader writes about coming across a 2003 CIO article about Google Research Director Monika Henzinger and being quite surprised to read the following:

But it was while teaching courses on her beloved algorithms at Cornell University when she had a flash. "I realized that efficient algorithms were fun but not very useful to the world anymore," she says.

The reader asks if there any reasonable sense in which that could be true?

While most algorithms developed by theorists have little practical value and will never see code, efficient algorithms play a critical role in any large system, especially at Google. As Henzinger states herself later in the same article:

If you think Google is fast, it's because we have good algorithms.

Turing Award

Frances Allen will receive the 2006 Turing Award (the most prestigious CS prize), the first woman to win the award (via USACM).

Graduate Student Guide

I have received some questions recently asking me advice for topics on which I have previously posted. So here are links to postings to help your graduate school career from cradle to grave.

• Judging Applications
• Choosing a Graduate School
• Choosing an Advisor
• Finding Problems to Work On
• Attending Conferences
• Writing a Dissertation
• Looking for Academic Jobs
• The Academic Interview Trip
  • What to Wear
  • The Job Talk
  • Meeting with Faculty
• Negotiating Your Offer

Above all, have fun!

STOC and FOCS

As many of you already know, the accepted papers for STOC '07 has been posted. And in that great circle of theory life, the FOCS '07 Call for Papers is out. Submission deadline is April 20 and FOCS will be held October 21-23 in Providence.

One of my readers broke down the STOC accepts by area. Also check out the FAQ sent with the paper comments, though I doubt "No reviewer liked my paper. How come it was accepted?" gets frequently asked.

For those authors of the 234 papers not accepted to STOC: Maybe your tastes don't match those of this committee, maybe your paper is just not STOC-worthy, or maybe life just isn't fair. In any case, don't get angry, just go update your paper with the reviewer's comments and submit your paper to a journal or another conference.

Time and Music

Two quirky computer events over the vacation.

I enter events in my online calendar in Lance-time, i.e., at the time in the time-zone I will be in when the event occurs. Calendar programs don't have Lance-time so I just use Central time. Normally not a really big problem since I just leave the calendar in Central time when I travel. But on this trip I downloaded my calendar to my mobile phone. My mobile phone knows what time-zone I am in so it automatically adjusts the clock (which I like) but also the calendar. So say, an 8 PM flight out of LA, would come up as 6 PM. Software being too smart for its own good.

During my vacation a new folder "Mike's Music" popped up in Itunes. Quite an impressive collection, including the Beatles, CSN&Y and Bruce Springsteen, most of it quite playable. I don't know who you are Mike, or how your music ended up on my machine but thanks for the tunes.

Now that I returned to Chicago the music disappeared without a trace. Go figure.

MARTIN DAVID MEMORIAL (Part II- by Clyde Kruskal)

Guest Posting for Guest Blogger Bill Gasarch,
Guest Poster Clyde Kruskal.

At my fathers memorial service, here is how
I ended my remarks.

I want to share a story that is
about my kids, my Dad, and Donald Knuth.
As you will see, it all ties together.

The way Dad learned about surreal numbers, which
became his passion, is by
reading a book by Donald Knuth, written
in the form of a dialog.  Donald Knuth is in many
ways the father of computer science.  In the 1960's
he wrote a three volume set laying out the foundations
of computer science.
The world has been patiently waiting since 1973 for
Volume 4, which is just now coming out.

Anyway, you know how Dad was when he read something.
He had to make sure every technical detail was correct,
and he never missed a typo.  After finishing the book
he sent Knuth a long list of corrections,
and was surprised to get a check back in the mail.
It turns out Knuth pays money to the first person
who finds each error in his books.

If I am allowed to interupt myself, I sent this story
to Knuth.  He wrote back that he

``... found a copy of the letter I wrote to your dad in
August, 1975.  It closed with `...your reward check is
enclosed. It's the first time I've ever paid out for
{\sl Surreal Numbers\/}; in this kind of book
[written as a dialog], I can usually claim that errors
were intentional.' ''

Well, two summers ago my colleague Bill Gasarch decided
to review a math book, which happened to be written in the
form of a dialog.  So, one afternoon, he gathered
[my triplets] Alexander, Justin, and Rebecca together,
taught them the material, and wrote down their comments
as a dialog.  Of course, anything that had to do with
both math and the kids I emailed to dad, because he
would appreciate it.  Sure enough, back came a full
page of unsolicited corrections and improvements.
Bill was amazed.  After making the edits, the review
was sent out with Bill and the three kids as authors.
It appeared in the fall.

Last month I was in Bill's office and he says.
``Look.  I just got email from Donald Knuth.''
Here's what he says about the review.
``Brilliant.''
Then it goes on to ask if he has received Volume 4 yet
to review
``possibly with the help of Alexander, Justin, and Rebecca.''

I thought to myself.  ``Wow!  I can't wait to tell Dad.''

But I couldn't.
So, I hope you heard this.
We miss you.

MARTIN DAVID KRUSKAL MEMORIAL (Part I)

Bill Gasarch again.

Martin David Kruskal was a brilliant Mathematician
who passed away in late December, at the age of 81.
       (His brother Joe, still alive, did Min Spanning Tree.
More on his whole mathematical family later).
He has three children: Karen, Kerry, and Clyde.

Clyde is a theorist in my dept who works on Parallelism.

The memorial for Martin (Feb 11, 2007) was unusual.

When someone passes away there may be a memorial service
where people take turns saying things about the deceased.
The family organizes this.

When an academic passes away there may be a conference held
in his honor (invited talks from people who knew his work).
His collegues organize this.

For Martin Kruskal they had BOTH ON THE SAME DAY!
The intent was that people would GO TO BOTH.
From 1:30-3:30 there were five 20-minute technical talks
about his work.
The speakers were warned that that many lay people would attend.
From 4:00-5:30 there were seventeen 3-minute presentations
about Martin Kruskal, the person.

0) It was held at Princeton in the math building-
like a real conference.

1) The Tech talks were GREAT if you knew just a LITTLE
bit of math. People completely outside of math may have
had some problems following some of it, but they still got
the impression that Martin did great work.

2) The Tech talks had far more personal touches than most
tech talks have.
  The Memorial talks had far more math stories in them than most
memorial talks have.

3) There were between 250 and 300 people there!
Free dinner! No registration fee!

4) Karen Kruskal remarked that Clyde was the only one
of the three children who went into mathematics, and hence
Clyde understood his fathers work.  Clyde would be the first
to tell you that this is not true.  Lay people (she's a lawyer)
do not realize just have vast mathematics is.  To her, Clyde
who works on parallel computation, and Martin, who works on
the mathematics of soliton waves, both do math, and hence
understand each others work. She was half right.

5) Martin had two brothers and two sisters. All three brothers
were first rate mathematicians:
Joe Kruskal: Kruskal MST, Kruskal Tree Theorem on Well quasi orderings,
               Kruskal-Katona theorem
Bill Kruskal: Kruskal-Wallace test in statistics (deceased)
Martin Kruskal: Soliton Waves, Kruskal Coordinates, Plasma Physics. (deceased)

6) Joe Kruskal spoke about how Martin taught him math
at a very young age. (Joe was younger than Martin.)

7) Kerry Kruskal sang a song he wrote, to the tune of
GUYS AND DOLLS, about Martin's work in Mathematical Physics.
I have a copy- Until they put it on YOU-TUBE it is the
second rarest thing in my collection.

8) Clydes Triplets (Recall that Clyde works in parallelism)
performed classical music as a trio.
(Alex-Trumpet, Justin-French Horn, Rebecca-Trumpet)

9) Clyde gave an excellent talk which involved Donald Knuth,
his triples, and yours truly.  Tune in tommorow for that.

THE DEFINITION OF RARE

(Guest Blog by Bill Gasarch has has a large collection 
of novelty songs, mostly funny songs.)

I) There was a satire on Saturday Night Life called
CONSPIRACY THEORY ROCK (which was in the style of
SCHOOLHOUSE ROCK) that was brilliant, and only aired
once.  (Too controversial, though this posting is not
about that.) I have this video clip in my collection,
and it was one of the rarest things in it.

NOW this clip is on YOU-TUBE!  Hence I can no longer
claim it is `rare'.  But the YOU-TUBE clip says
``rare video footage''

HOW RARE CAN A VIDEO CLIP BE IF
ANYONE IN THE WORLD CAN ACCESS IT !?

II) With the ability to make perfect copies of CD's,
and MP3's its hard to say what it means to have a
`rare recording'.  If you have the original Vinyl
record or reel-to-reel tapes, that may be rare, but
I'd RATHER have the version put on CD or MP3.

III) Some paintings sell for gobs of money.  Do we have
the tech to reproduce those exactly (in 3D)? I suspect
no, but one day we will (holographs?).  When that day
comes, will the prices drop?  Maybe not- its already
an artificial market; `originals' may still be valuable.

IV) What music or video or TV shows or whatever bring
produced now will be considered `rare' in the future?
Note that even really bad TV shows and movies are on DVD.
Some really bad movies even have `directors cuts'.

V) So, what is the rarest thing in my collection now?
In 1976 I audio taped off of TV a satire- a Chrismas
song as if done by Bob Dylan.  I did not know who did
it.  I still don't.  I have not found it anywhere else.
It does not seem to be on vinyl, audio, CD, or MP3.
Since I have the largest Bob Dylan Satire Collection
in the world, (www.cs.umd.edu/~gasarch/dylan/dylan.html)
and this is known by that community (How large is that
community? Larger than the Gen Multidim Poly VDW
community) the fact that I can't find it, and nobody
has emailed me about it, means ... its rare! However,
I would rather FIND it on CD or some other medium and
know who did it than preserve its rarity.

READING PAPERS FOR FUN

Bill Gasarch guest blogging for Lance Fortnow

Jane: What you you been working on?

Bill: I've come up with an elementary proof of the
Gen. Multidim Poly van der Warden's theorem.

Jane: Is it new? Is it publishable? Does it have applications?

Bill: Its not new- People in the field already know this.

Jane: How many people are in the field.

Bill: Lets not go there. However, not new, not publishable as original research,
and no applications that I know of.  I got a guest post in Luca's Blog about it,
but that does not count for anything (should it?).
Anyway, here is a nice (known) corollary:

For any 2-coloring of the lattice points of the plane there exists d\in N
and a d by d^2 rectangle where all four corners are the same color.

Jane: Why did you spend time reading something with no hope for original research?

Bill: Jane, you ignorant ... (lets not go there either).

1) I was very curious about this theorem.  That is reason enough.
People don't watch Shakespeare plays for the sole purpose of getting
a paper out on them. Except English Professors.

2) Reading math or CS stuff that interests you is one way to find open
problems and new angles on things. So this is good in the long term.

3) Just because I did not plan to publish based on it does not mean that I won't.
By reading up on Ramsey Theory I have gotten out two papers, ideas for a third,
several (non publishable) ugrad and highs school projects, and a problem for the
MD Math Olympiad.

Jane: Do you always talk in lists?

Bill: Only in fictional conversations.

Is it valuable to read math of interest to you with no particular plan for application?
Clearly Yes.
But the real question is, compared to what?
Compared to reading articles more directed towards a particular problem?
Compared to working on Math Olympiad problems?
Compared to sitting and thinking?
Compared to browsing porn on the web?
The answers vary from person to person.
However, my sense is that reading for pure interest is underrated.

Complexity Papers

I am on vacation and off the internet for most of next week. Bill Gasarch will bring you his wit and wisdom in my absence.

A few of the accepted papers of the upcoming Computational Complexity Conference that caught my eye.

Extractors and Condensers from Univariate Polynomials, Venkatesan Guruswami, Christopher Umans, and Salil Vadhan.

Extracting nearly uniform random bits from weakly-random sources has been one of the solid lines of research in the past few years in complexity. This paper matches the best known bounds for extractors with a clever use of recently developed list-decodable codes.

On derandomizing probabilistic sublinear-time algorithms, Marius Zimand

I'm less excited by the title result than the tools Zimand develops, an extractor that produces bits that looks random even to circuits that can see part of the weakly random string.

Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems, Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay

When running a multiple proof system in parallel, the provers can sometimes do better coordinating between runs than treating each run separately. This paper gives an example when classically the provers can take advantage of the parallelism but quantumly they cannot.

There were several very interesting titles whose authors have not put those papers online. Shame on them.

Divestment

As an undergrad at Cornell in the early 80's, I witnessed the movement to encourage the university to divest their endowment holdings in companies that do business in South Africa, to protest the apartheid of the time. Some students went as far to create a "shanty town" of tents, sleeping outside to make their point. I didn't support their movement for a selfish reason—my mother worked for one of those companies and it seemed hypocritical to bite the hand that fed me.

Last week the University of Chicago president announced that the board of trustees would not change the investment strategies of the university in response to calls not to invest in companies doing business with the Sudanese government, despite the fact that several other universities including Brown, Harvard, Princeton, Stanford and Yale have decided to eliminate such investments. American companies are already barred from doing such business so a university could eliminate such investments reasonably painlessly but the University of Chicago didn't want to set a precedent.

Proposed NSF Budget

The president sent out his proposed budget for FY08 (starting October 1, 2007). The NSF in general and CS in particular do quite well. The CRA Blog has the details but for the tree we care about:

• The NSF received a 6.8% increase over the FY07 request.
• Research and Related Activities: 7.7%.
• Computer and Information Science and Engineering (CISE): 9.0%.
• Computing and Communication Foundation (CCF): A whopping 21.4%.

CCF is where the Theoretical Foundations cluster sits which includes Theory of Computing.

Also NSF would have a new agency wide program on Cyber-Enabled Discover and Innovation (CDI) to "Broaden the Nation's capability for innovation by developing a new generation of computationally based discovery concepts and tools to deal with complex, data-rich, and interacting systems."

The big caveat: The budget has to survive the congressional appropriation process.

The Interview Trip

A reader asks

You've told us what to wear and how to give the talk at my interview. Any tips for the rest of the trip?

Aside from your talk and a nice dinner, your interview will consist of a grueling series of half-hour meetings with faculty in and possibly outside the department. While you have passed the first test to even get an interview, you still have to distinguish yourself from the other candidates. Your job is to sell yourself particularly to people outside your field who don't know you or your research well.

Take the lead from the person you are talking to. If they start talking about their own research then listen intently and ask friendly intelligent questions. If they start talking about the town (indicating a belief that the two of you have no research interests in common) then have a nice talk comparing it to places you have lived in the past. If they ask about your own research then describe some results beyond your job talk.

Some will ask you questions. "Would you be willing to teach X, or organize Y?" Your answer is always "Yes, I'd be happy to." Some might ask why your research or even theoretical computer science in general is relevant. Make sure you have something intelligent to say and never apologize for your research. Some will ask about your ability to generate funding. Say you will regularly apply for grants at the NSF and other agencies. Acknowledge that theory grants aren't as large as more applied areas but your needs are also fewer.

You must avoid dead silence. Visit the web pages of the faculty you are meeting ahead of time and find some talking point for each of them. Have a list of questions about the department that you can always ask to keep the conversation going.

Act positively. Always show interest in what the other person says. Say only positive things about the place you are visiting and don't say anything negative about any other place. Don't complain how bad the market it. Don't complain about the hotel or the food. Don't complain about anything. Most importantly act like you really want the job whether or not you do.

Have good manners. Always firmly shake hands and thank the person you just talked to and firmly shake hands with the person you will talk with next. Act civilized at dinner. Send thank you emails soon after you return.

Good luck!

Up and Downs

I woke up to see one of my complexity submissions accepted. But soon the other two were rejected. Then the Bears lost.

The list of accepted papers for Computational Complexity has been posted. See you all in San Diego.

Bear Down, Chicago Bears

Only one topic dominates discussion in Chicago these days—the Bears in Super Bowl XLI, America's biggest sporting event. The Bears last played in the Super Bowl when I held my very first Super Bowl Party back in my first year of graduate school. The Bears won big that year and will do so again this Sunday.

I present to you Lyric Opera of Chicago's Bryan Griffin singing that famous aria Bear Down, Chicago Bears.

Or, if you prefer, the CSO Concert version.

Go Bears!

James Gray

Microsoft researcher and Turing award winner Jim Gray is missing at sea after taking his boat out on Sunday. The Coast Guard continues the search. We can only hope for the best.

More NSF News

CMU's Jeannette Wing named head of the CISE directorate. Hopefully she can put some of that Computational Thinking into the NSF.

Theory Candidates

Having looked at the applications of several theoretical computer science job candidates, I notice some interesting differences from even one year ago.

• Last year many of the stronger candidates were coming off of postdocs looking for tenure-track jobs. This year we see more strength from the fresh Ph.D.s.
• Last year there were a large number of outstanding cryptography candidates. This year no particular field dominates.
• Last year the strongest candidates were heavily weighted with MIT Ph.D.s. The degrees of this year's candidates are much more spread out.

The last two points are not completely uncorrelated.

There are some notable exceptions to the above and the differences are easily explained by statistical variations on small sample spaces. But still worthy to note how much variation we see in the theory market from one year to the next.

Good News for the NSF

A 6% increase for the National Science Foundation for the current fiscal year (via the CRA Blog). Now go write those proposals.

Thought of the Day

Life is just a big Markov chain, whose stationary distribution is death.

Rating Papers

Suzanne Zeitman, associate editor of AMS Mathematical Reviews (and on the web), would like to get suggestions from the TCS community on how MR "can do a better job at covering the literature (wherever it is) in theoretical computer science."

Looking at a random sampling of papers, the reviews seem to give a short description of the main results of the paper without much or any opinion on the quality of the paper though the fact the paper has a review indicates some positive view of the paper. Other than that the review doesn't seem to give more information than a well-written abstract.

As comments on this weblog show, many people will give more honest views if they don't have to reveal their identities. Anonymous reviews of papers might prove equally fruitful.

On this topic, David Bacon created a Digg-like site scirate.com for quant-ph. Kudos to Dave for bringing some Web 2.0 tools to highlight important papers.

Still researchers looks at papers more like movies—we like different genres and then have different preferences within these genres. Could some sort of recommender system for academic papers help us find good papers to read?

Too Useful to be a Computer Scientist

A conversation I heard about several years ago.

Physicist: Computer scientists have done nothing for quantum computing.

Computer Scientist: What about Shor's quantum factoring algorithm?

Physicist: Peter Shor is a physicist.

This becomes a self-fulfilling prophesy. Once computer scientists have done something physicists care about they cease to be computer scientists and are now physicists.

This view has changed a bit, now we do see a number of physicists (though certainly not all of them) seeing value in many of the tools, techniques and results from computer science. We are also making headway in other fields like economics and biology.

If we want computer science to continue to prosper we need to continue to reach out to other fields and do our best to make them understand the role computer science can play in helping understand their basic questions.

The Bourbaki Lecture

Hanging in the Indiana University Mathematics Lounge is a letter dated November 16, 1948 written to Max Zorn from Nicolas Bourbaki and cc'd to André Weil.

I am glad to be able to inform you that the American Consulate in Paris has now granted me a visa, and that I have booked passages, for my wife and myself, which should just enable us to reach Columbus, Ohio, in time for my scheduled talk to the Association for Symbolic Logic.

At the same time, I must say that I have learnt with no little surprise the rejection, on technical grounds which I do not understand, of my application for membership in the American Mathematical Society. Under such circumstances, it will be clear to you that I cannot but decline your kind invitation to attend a dinner which, I believe, is chiefly sponsored by that Society.

Perhaps the AMS rejected his application on the technicality that Bourbaki did not actually exist as a person, he was just a pseudonym for a collection of French mathematicians writing a series of books on modern mathematics.

Bourbaki did have an invited paper presented at the ASL Meeting in Columbus on December 31. Weil, one of the founders of the Bourbaki group, presented the paper at the conference.

If the same kind of story happened today would we hang a framed email on the wall?

Is it Morning or Mourning for American Science?

Last week Chicago Cosmologist Michael Turner gave a talk "Trends in Science Funding: From NSF to the ACI". Turner was head of the Mathematical and Physical Sciences, NSF's largest directorate, from 2003 until last summer (computer science is mostly funded from the CISE directorate). The slides describe the state and process of science funding in the US and argues for the importance of physical science funding.

In his position, Turner played a role in helping to push the American Competitive Initiative that Bush proposed at the State of the Union last year that would have, among other things, doubled the NSF budget over ten years, about a 7% increase a year. The ACI was "stillborn" with the continuing resolution that froze most of the government's budgets at last year's level. The continuing resolution has put a very tight squeeze at NSF and other governmental scientific institutions.

Still Turner has some reason for optimism. He expects the president to push for ACI again, if not in tonight's State of the Union, then in his budget for FY08 and has hopes congress will support ACI or a similar plan. Also several congressmen have signed a Dear Colleague letter requesting to add funding to the NSF for this fiscal year, though Turner was pessimistic that this request would be fulfilled.

Complexity Textbooks

A reader asks

What are currently considered to be the best textbooks for complexity? I know the choice is small (Papadimitriou is probably still the best even if it is very outdated and somewhat buggy), do most of the lecturers just write their own lecture notes? Is there a set of notes that is especially popular and also used by others. I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching?

You have more choices than you think with textbooks by Homer and Selman, Hemaspaandra and Ogihara, Ko and Du, Wegener, and several others. Also several complexity theorists have put their lecture notes on line, quite a valuable resource. Jin-Yi Cai has the makings of a textbook from his lecture notes.

The topics and style of a computational complexity course varies from instructor to instructor and no single book would work for all. You really just need to find what best works for you and your class.

I personally don't use a textbook when I teach graduate complexity. I've been so close to the field no book would fit my philosophy unless I write it myself. And that's not going to happen anytime soon.

Proceedings Papers

Grant Schoenebeck asked this question for the Q&A Podcast but we didn't get to it.

In proceedings, papers are printed in a hard-to-read two column format and are artificially cut off at (usually) 10 pages. Personally, I look for a more readable/extended format on-line before suffering through the conference format. However, if we no longer have printed proceeding (or even if we did, but also had on-line proceedings) then these restrictions would no longer need to apply. We could print things is a way that would be much easy to read and could have original versions of the papers that we not oddly missing some proofs or sections.

Is this a good idea? Why don't we start doing this now?

We have the two-column format in proceedings because it saves space, a paper typically drops 30-40% by moving to a two-column format. Less white space.

But I would go further than Grant and suggest that every author should have a complete version of their paper available on their web pages and/or an archive site before the conference. I hate the phrase "A full proof will be available in the full paper" when one doesn't exist. But I don't want to require the extra version or we may end up discouraging people from writing up their results properly with yet another deadline.

The Academic Road Trip

Jason Teutsch is an Indiana Math Ph.D. student who has been working with me via the CIC Traveling Scholars program. Tomorrow he defends his thesis so today I'm driving Jason and another faculty member and graduate student down to Bloomington. Road Trip!

In graduate school we took these trips quite often. Many conferences meet in the Northeast and we would pile into cars and drive out. A good chance to bond with your fellow students.

Fewer conference meet in the Midwest and in Chicago you tend to fly to travel. But we do have the occasional reason to take the long drive. We will be in a closed environment with no internet (assuming everyone stays off their cell phones). We'll actually have to talk to each other, maybe even try and prove a theorem. How quaint.

Computing Square Roots

My daughter learned about square roots and she did her homework taking those roots using a calculator. She asked me how to compute the square root without using a calculator.

I actually learned this procedure in the mid-70's, probably the last generation to do so. But unlike long division or Euclid's Algorithm, I quickly forgot how to compute square roots since the process was quite cumbersome, one didn't have to take square roots that often and reasonably priced calculators appeared soon thereafter. Almost no one even 50 years ago used the manual method for square roots, using slide rules or log tables instead.

I rarely even use calculators today. I find square roots like I find out anything else, praying to the Google Gods.

The Proceedings

It is a conference ritual as far back as I remember. Your arrive at the conference and receive the proceedings, all the papers to be presented at the conference many of which you are seeing for the very first time. I would take the proceedings to my room, smell that new proceedings smell and open it up, first checking that my papers looked fine, not that I could do anything if they weren't. Using the proceedings I would plan what talks I would attend the first day.

The proceedings would never leave my room until after the conference. I just hated lugging the heavy proceedings around. Sometimes when a speaker said something that didn't make sense to me, I would simply borrow a proceedings from someone sitting next to me.

When I returned home I would put the proceedings in its proper place on my office shelf, marveling at my complete collection of STOC, FOCS and Complexity proceedings back to 1986, incredibly useful for looking up recent papers.

How has technology changed how I use a proceedings? Not much during the conference, but I now rarely use proceedings to look up papers and no longer have complete collections of STOC and FOCS.

Other people use proceedings during a conference in different ways. Some never open them up. Some follow along in the proceedings during a talk. Some read the paper before or after the talk.

That's the important point to keep in mind when we have our debates on whether to eliminate proceedings, or put them on the web or on CD-ROMs. We all use proceedings in different ways and no single solution will address everyone's needs.

Events

Richard Ladner wants me to remind my readers about the SIGACT student research competition. From his chair letter in the last SIGACT news.

There will be a new event at STOC 2007, the Student Research Competition, which will be a poster and short presentation competition for undergraduates. The deadline for submissions is February 23rd, 2007. If you are working with an undergraduate on research, please encourage him or her to submit to this competition. Accepted students are provided up to $500 for travel to the conference. This competition is an excellent way to engage the next generation of theory researchers in our conference. I want to thank Brent Heeringa for chairing this new activity for SIGACT.

The TARK (Theoretical Aspects of Rationality and Knowledge) conference meets this year in Brussels in June mixing computer scientists, economists and philosophers discussing knowledge, rationality and how it all plays in CS and economic models. And I'm on the PC this year. Submission deadline is January 30.

The 27th Crypto conference will be held August in Santa Barbara, one of the few conferences held in the same location each year. Submission deadline February 19th. For those who feel Crypto focuses too much on applied research, the Theory of Cryptography Conference (TCC) meets next month in Amsterdam.

ICALP, the granddaddy of European theory conferences, meets in Poland in July. Submissions by January 25.

RANDOM/APPROX in Princeton in August. Deadline April 7. MFCS (Eastern European Theory) in Czech Republic in August, deadline April 2.

There are many many more. DMANET and TheoryNet will keep you on top on what's going on.

The Sum and Product Riddle

A cute problem that I got off Steve Fenner's door that he got from FOM.

Let x and y be two integers with 1<x<y and x+y≤100. Sally is given only their sum x+y and Paul is given only their product xy. Sally and Paul are honest and all this is commonly known to both of them.

The following conversation now takes place:

• Paul: I do not know the two numbers.
• Sally: I knew that already.
• Paul: Now I know the two numbers.
• Sally: Now I know them also.

What are the numbers?

The State Universities

While Luca suffers in Hong Kong, I am visiting beautiful Columbia, South Carolina. (The ribs are better here) Next week a day in Bloomington, Indiana and the following week a couple of days in Ann Arbor, Michigan as I visit the flagship universities of those states.

Over my life I have visited the flagship campuses in Arizona, Indiana, Iowa, Maryland, Massachusetts, Michigan, Minnesota, Nebraska, New Jersey (Rutgers), North Carolina, Oregon, Pennsylvania (Penn State), South Carolina, Texas, Vermont, Virginia, Washington, West Virginia and Wisconsin. (Illinois is conspicuously absent). I have also visited several campuses of the California and New York systems which don't have a specific flagship. I can more locations of flagship campuses than I can state capitals.

The state universities got a strong push from the Morrill Land Grant Act passed during the Lincoln administration after the southern states that objected (like South Carolina) had left the union.

One of the great strengths of the US higher education system are these state universities, independent and competing, instead of a system of nationalized universities that you find in many other countries.

Four Eyes

Why do so many scientists wear glasses? Thirty years ago this question was essentially equivalent to "Why so many scientists have bad eyesight?" I don't have a good answer to this second riddle, perhaps some genetic link between scientific ability and eyesight, perhaps scientists don't have worse eyesight than society in general and I just have biased beliefs.

But now the question "Why do so many scientists wear glasses?" has much less to do with eyesight. With advances in contact lenses and surgery most people can do away with their glasses. But most scientists seem to keep their glasses, even wearing them with pride. Is it really a fashion statement? I've asked some of my colleagues, they worry about the price or the risks, both of which are quite low once you do the research.

I couldn't wait to get rid of my glasses. I started wearing contacts in college in the late 80's and had LASIK surgery in 2002. I've had better than 20/20 vision and haven't needed to worry about my eyesight since. How do your glasses feel?

SODA and Funding

Suresh and Jeff cover the SODA Conference currently meeting in New Orleans. Suresh talked about a lecture given by Luc Devroye giving techniques that might help determine the actual constant factors in some algorithms. I usually ignore constants even in the exponents. Perhaps that's why you tend not to see me at SODA conferences.

Many readers pointed to a New York Times article discussing how the freeze on spending levels for 2007 will affect science funding, a problem I mentioned last month. The Times article mostly describes the affect on big science projects but those of us doing "small science" will be hit hard as well. The CRA recommends that you contact your representatives and senators.

Dress for Success

A graduate student asks

What should I wear for an academic job interview?

Most computer scientists won't notice and will completely forget what you wore when it comes to decision making time. But the wrong clothes might make a bad impression on some of them and you might meet administrators or faculty from other department with different standards of attire. You never want to give the appearance that you are not taking the interview seriously.

On the other extreme I have seen candidates looking uncomfortable in suits they clearly borrowed or bought off the rack. My suggestion, dress as nicely as you feel comfortable. To be specific, I'd suggest nice pants and a jacket with or without a tie for men. For women the best I can say is dress professionally.

Don't feel afraid to ask the person hosting your visit about these kinds of questions. The host generally wants you to succeed and can tell you about who you will meet and any expectations they may have.

2007 Celebrations

Jan van Leeuwen runs down many of the anniversaries coming up this year.

Reading your post 2006 Year in Review, I was reminded of a number of memorable things that are coming up in 2007.

Are there any commemorative facts to be noted in 2007? Most certainly there are, although it isn't anything like the Gödel year we just had. I'm not counting the Robert A. Heinlein Centennial to be held in Kansas City later this year, undoubtedly a major event for the science fictionists among us.

Staying closer to our field, in 2007 it will be 100 years ago that John Mauchly was born. Together with Howard Aiken and J. Presper Eckert he is one of the best known, early computer pioneers from the US. Together with Eckert he built the ENIAC and later the UNIVAC I (built between 1946 and 1951).

2007 also marks the 100 year anniversary of another computer pioneer, namely Antonin Svoboda from the Czech Republic. He was the main designer of the first Czechoslovak relay automatic computer SAPO (built between 1947 and 1951), working in the Research Institute of Mathematical Machines within the Czech Academy of Sciences.

From a more theoretical perspective, in 2007 it will be 100 years ago that Hassler Whitney was born. As a mathematician he made some highly original contributions to early graph theory, notably on the four color problem and on planarity (cf. Whitney's planarity criterion). He is also widely credited as the inventor of matroid theory, of which the foundations were defined in his 1935 paper On the Abstract Properties of Linear Dependence.

Other mathematicians whose centennials are coming up include H.M.S. Coxeter and Harold Davenport.

But 2007 also marks the 300 year (!) anniversary of the birth of Leonhard Euler. The math community is celebrating the Tri-Centennial Birthday of Euler in many ways.

• The journal IJMAS is devoting special issues to this year.
• The MAA devoted it Mathematical Study Tour for 2007 to an Euler tour, visiting his birthplace, Basel, and the two cities in which he spent his working life, St. Petersburg and Berlin.
• The city of Basel itself organizes The Leonhard Euler Tercentenary - Basel 2007 and celebrates it with a series of activities.

Solving Puzzles

An economist, a physicist and a computer scientist were sitting at a table. A true story, not the beginning of a joke. One of them said

We were solving fundamental problems twenty to thirty years ago. There is still much we don't understand but today we are only solving puzzles.

Any one of them could have said that, scientific insecurity runs through all fields. A similar set of scientists probably had a similar discussion twenty years ago as well.

At the end they all concluded that the future of their fields lied not in the cores of their fields but in the interaction between them and other fields not represented, like biology. They probably also said that twenty years ago.

Baseball and Opera

The New York Times reports on a possible merger of the two major US satellite radio companies. This would resolve one of the great dilemmas as XM carries the audio of every Major League Baseball game and Sirius has a station devoted to live and archival broadcasts of the Metropolitan Opera.

On the face of it, you would expect most baseball fans would rather watch paint dry than attend an opera and vice versa. But I'm not alone among the people who fanatically follow both. I can't pin down the exact connection between opera and baseball and one can make many philosophical comparisons (e.g. both require large teams but at most fixed times individuals rule the stage, both require a good attention span). Most lovers of both that I know are also scientists though that might just be my lack of a good sample. And I can't explain the Italians who seem to embrace opera and soccer.

In the academic world we get little choices about where we can live, so I find myself extremely lucky to be in a city with a great tradition in both baseball and opera. I've mentioned baseball more than opera in this weblog, but it was the baseball season tickets that I gave up once the kids were born.

If you are a great lover of baseball or opera you should give the other a try. And if you read the title of today's post and thought about the browser, shame on you.

The Job Talk

As we begin January so begins the hiring season. In January CS departments start sifting through candidates deciding whom to bring in for interviews. Don't wait until you get your interview call, now is the time to get your job talk ready.

A great job talk by itself won't guarantee you a job, but I've heard of many an instance where a bad talk has ruined a candidate's chances despite otherwise stellar credentials. A good job talk should achieve three goals.

1. Explain your results.
2. Explain why your results are important.
3. Explain how you achieved your results.

Fail to do the first two and you will not get the job. We theorists have a tendency to want to "wow" an audience with our clever techniques but first you must spend several slides carefully giving an intuitive description of your research and why those in the audience should care about the results. Be sure and mention what your own research is early in the talk and again at the end.

Know your audience, usually a broad spectrum of computer scientists. You give a different talk to them than you would in a regular theory seminar. Motivation and intuitive explanations of your research are key.

Repeat the following mantra as you prepare your slides: Formulas bad. Pictures good. Formulas bad. Pictures good.

Give a practice talk in your own department. Invite some people from outside theory. Listen to the comments. Revise your talk. Repeat.