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.