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.

2006 Year in Review

The paper of the year goes to Settling the Complexity of 2-Player Nash-Equilibrium by Xi Chen and Xiaotie Deng which finished characterizing the complexity of one of the few problems between P and NP-complete. The paper won best paper award at FOCS.

The story of the year goes to Grigori Perelman, his proof of the Poincaré Conjecture, his declining of the Fields Medal and Shing-Tung Yau's portrayal in the New Yorker and the lawsuit threat that followed. Science magazine named Perelman's proof the Breakthrough of the Year.

Meanwhile the theory-friendly number theorist Terrence Tao accepted his Fields medal and CMU cryptographer Luis von Ahn and Tao won MacArthur genius awards.

My post FOCS Accepts and a Movie received over 200 comments mostly about the state of the theory conferences. Sadly the movie and the rest of the science.tv site have disappeared. I also finished my favorite complexity theorems, at least for now.

In 2006 we celebrated the centennials of the births of Kurt Gödel and Richard Rado and mourned the early death of Mikhail Alekhnovich.

Thanks to guest blogger Claire Kenyon, guest posters Eldar Fischer, Jérémy Barbay, Janos Simon and podcast guests Luis Antunes, Eldar Fischer, Troy Lee and his opponents. The biggest thanks to Bill Gasarch who did all of the above several times.

Happy New Years to all my readers and let's look forward to an exciting FCRC and a renewed US commitment to increased funding in the basic sciences.

Foundations and Impacts

As we start thinking about our Theoretical Foundations proposals, a few related items from the theory community.

Joan Feigenbaum and Michael Mitzenmacher have written a report "Towards a Theory of Networked Computation" available on the group's web page. The report is still under revision and Joan welcomes your comments.

SIGACT Chair Richard Ladner writes in the latest SIGACT News about the importance of the required Broader Impacts criteria in NSF proposals.

One way to think about the Broader Impacts criterion is that when we receive money from the people of the United States through NSF, the people would like to know ahead of time of what benefit the research may or will be to society. If there is little or no benefit then why should the people continue to support NSF? When NSF goes to Congress to ask for money, it is going to the people's representatives, who ask for justification to spend the people's money on scientific research. Basically, NSF's funding, and ours indirectly, depend on the belief by the public that broader impacts come from our research. Some people have said to me that a focus on Broader Impacts is a move away from basic research to more mission oriented research, or research with strings attached. If we look at the ways that we can satisfy the Broader Impacts criterion, they are very general, and relate to education, broadening participation by underrepresented groups, and other benefits to society. Please read the representative activities for concrete ideas for how to include Broader Impacts in our proposals.

As SIGACT Chair, I am trying to help increase the funding for computer science theory research. The best way to increase funding for research is to convince people it is important to them and the people around them. There is a difference between "important" and "useful". Artists are able to convince people to buy art, not because it is useful, but because it inspires them. Astronomers convince people to pay them to study the stars, not because they are useful (except for our own star, the sun), but because the stars are fascinating in their own right. Understanding the birth and possible death of the universe is of no practical value, but is just a fundamental question.

All this said, I am a firm believer in serendipity. Often, research leads to unexpected results and unanticipated applications. Unfortunately, this phenomenon is quite rare and probably not common enough to convince people to provide large amounts of research money. The best approach is to have a great story about the benefits of theoretical computer science research and its promise for the future. This will generate enough money for all of us so that rare serendipitous events will happen naturally in the course of doing our research.

An Internet-Free Week

From about early December to late January the academic world takes a little breather as many universities end their fall quarters and start their spring. Many students and faculty are away, the universities are ghost towns. A time for rest, a chance to catch up on some of those tasks we've been putting off for the fall. A chance to get ready for the next quarter or semester. This week between Christmas and New Years marks the nadir of activity: Absolutely nothing interesting should happen this week.

But over recent years this season seems far less quiet. We also work in a more global society and many countries, like Israel and India, treat this week not much differently than any other week. We can access the internet from anywhere and more importantly, we know everyone else can access the internet from anywhere. Taking time to visit relatives and friends or even going on vacation for many does not mean a break from email. Yesterday, Christmas Day, I received several actionable emails almost at the level of a typical workday.

We need an internet-free week. We should just shut down the whole network for seven days. Some people would use the time to relax and take a break knowing they will not be missing anything important. Others would continue to work finding themselves surprisingly much more productive than usual.

A Recommendation Letter

December 22, 2006

Dear Recruiting Committee:

George Henry is among the top fifty computational complexity theorists on the market this year and you should consider him for any faculty, postdoc or janitorial position in your department.

Computational Complexity compares complexity classes representing different amounts of complexity resources among different computational models. There are hundreds of complexity classes and thousands of variations on those classes. Henry's best result shows that for two of these classes, one of them is not contained in the other assuming that some third class is not contained in some fourth class. This work appeared in a theoretical computer science conference you've never heard of.

For service, George Henry has wasted his money joining the ACM, IEEE, AMS, MAA, ASL and SIAM. He's even (under duress) refereed a paper or two.

Henry gave a seminar once and nobody ran out screaming, probably because they were too busy sleeping. Henry also taught a course once. He was not actually convicted on any harassment charges.

George Henry has no two body problem since he's never had a relationship last more than three days.

In short, there are several great complexity theorists on the market this year but since your department has no chance of hiring any of them you might as well look at Henry.

Sincerely,

Lance Fortnow
Professor of Computer Science

The Necessity of Engineering for Science

Last month the University of Chicago faculty received an email from new president Robert Zimmer and soon-to-be-provost Thomas Rosenbaum about discussions on creating a program in Molecular Engineering.

The boundary between science (as the study of natural phenomena) and engineering (as the development and study of man-made artifacts) has become much more porous and in certain areas has virtually vanished. Historically, the University of Chicago has had a major international presence in science, but with a few special exceptions, has not systematically developed programs in engineering. With this important and evolving paradigm shift in the relationship between science and engineering, there are important questions regarding how the University should respond. These questions arise both because of exciting and important new areas of investigation at the science/engineering interface and because a lack of an explicit investment in engineering may hamper the development of our science.

Does science need engineering because engineering problems lead to important intellectual scientific questions or because engineering provides the tools needed by the scientists to carry on their research? Perhaps a bit of both.

Entertainment Tidbits

Can a CS degree propel you to a major acting role on a popular new TV series? Worked for this person.

I heard a complaint that in the movie Deja Vu they used face-recognition algorithms to find a suitcase in a large city in a matter of seconds. Because it's important to keep the computer science accurate in a time-travel movie.

In the last Numb3rs, Charlie the mathematician was seen carrying a copy of the SIAM Journal on Computing, a prominent TCS journal. Was he reading my paper or yours? At the end of the episode Larry the physicist left on the space shuttle to spend six months on the International Space Station while the actor, Peter MacNicol, moves over temporarily to the show 24. Couldn't Larry just have gone on a normal sabbatical?

On a more serious note we finally got around to watching Al Gore's documentary An Inconvenient Truth. Gore seriously impressed me with how he laid out the arguments and effects of global warming. The movie really affected my daughters leading to some interesting family discussions about warming and what we can do. I highly recommend watching the movie for those who haven't yet done so.

Show Us Your Research

Now that most of the FCRC Deadlines have passed, I would again suggest that you post your papers on a public archive like the Electronic Colloquium on Computational Complexity or the Computing Research Repository. The world wants to know about your research.

Which one should you choose? You don't have to, you can freely submit to both ECCC and CoRR. But how do they compare? [Disclosure: I am on the ECCC Scientific Board.]

• ECCC focuses on computational complexity though often contains papers across theoretical computer science. CoRR broadly covers all of computer science (with tags for subfields) and is part of the arXiv project covering physics and math as well.
• An article has to be approved by an ECCC board member to meet a minimum standard before it can appear. CoRR only checks for relatedness to the topic area.
• Both plan to have papers posted forever. ArXiv is currently run by the Cornell Library that gives stronger backing to this promise. However every paper on the ECCC and CoRR should later appear in a conference proceedings and/or journal.
• ECCC takes postscript submissions. CoRR prefers LaTeX submissions and processes them with hypertex.
• Both systems allow revisions and all versions remain available.
• ECCC has a (not-so-user-friendly) discussion system and email announcements of new papers. CoRR has RSS feeds for each subject class. Both systems plan to continually update their interfaces and features.

The Mega-Conferences

Chicago will be invaded by economists in early January, coming to the American Economic Association's Annual Meeting. At the same time the mathematicians meet in New Orleans. The physicists meet in March and April. We computer scientists all get together…never.

Most fields have their big annual get togethers with their plenary talks and many parallel sessions. New Ph.D's meet with potential employers often in a very organized way. Most importantly the entire community comes together to discuss the fundamental scientific and political issues of their discipline.

We don't have those meetings in computer science. The ACM has an annual get together where they give out awards but that is relatively small. Every four years we have the Federated Conference, a joint meeting of several conferences but they don't span the field, usually lacking a major AI presence.

So why don't we have a CS Annual Meeting drawing tens of thousands from across the discipline? Many of the other annual meeting started in a time when travel was more difficult and a single, or small number, of large general meetings made sense. We are a much more conference-oriented field and few of us would like to take yet another trip to a larger conference.

We lose something by not having a single regular meeting across computer science. We rarely meet people outside our field who are outside our departments. Different subfields in CS have developed different cultures. We lack the cohesiveness of other fields. When someone says "I am a Physicist" we know what that means. When someone says "I am a Computer Scientist", do we?

Motivation

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

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

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

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

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

Science a Victim of Politics Again

The NSF has a new Theoretical Foundations solicitation. Due date is February 19. Theory of Computing has its own component within this cluster.

But not all NSF news is good. Remember how Bush announced an American Competitive Initiative in his State of the Union back in February. ACI promised to double the NSF budget over ten years and the president's proposed budget included an NSF increase of 7.8% for FY 2007 that started October 1. The ACI had good support among both political parties in congress. So what happened?

Congress couldn't pass most of the budget resolutions before the elections. Monday Congressional democrats announced they won't finish the spending bills left unfinished by the current congress leaving budgets at last year's level until the beginning of FY 2008 next October.

In a joint statement, the incoming Democratic chairmen of the House and Senate Appropriations Committees said the urgency of new business and the administration's next spending request for the war in Iraq gave them little choice but to abandon efforts to pass the overdue bills.

The increases for NSF and other scientific agencies weren't singled out but science was one of the few programs slated for a long-needed budget increase this year.

More from the CRA.

You Ask, We Answer

In the ninth Complexitycast, Bill Gasarch and I answer reader's questions. MP3 (25 minutes, 4.3MB)

In the podcast we mentioned posts on finding jobs and the tradeoff between working on reasonable versus difficult problems.

Favorite Theorems: Second Decade Recap

This past year I listed my favorite computational complexity theorems from 1975-1984.

• Alternation (Chandra-Kozen-Stockmeyer)
• Relativization (Baker-Gill-Solovay)
• Small Sets (Mahaney)
• Primality Algorithms (Solovay-Strassen, Miller, Rabin)
• Probabilistic Complexity (Gill, Sipser)
• The Permanent (Valiant)
• Unique Witnesses (Valiant-Vazirani)
• Parity (Furst-Saxe-Sipser, Ajtai)
• The Yao Principle (Yao)
• Nonuniform Complexity (Karp-Lipton)

I have now completed my favorite theorems cycle for the first four decades of complexity including 1965-74, 1985-94 and 1995-2004.

Next favorite theorems in 2014. Will your name be on that list?