Free Electronic Editions of New Collaborative Books

I am on vacation next week and I've lined up Bill Gasarch as a guest Blogger in my absence. But today we have a guest post from Kamal Jain. This is a long post but well worth reading through.

This post is prompted by recent development and discussions on electronic publishing, which themselves are prompted by book scanning initiative of Google and Open Content Alliance. Although, I am not talking about paper books being converted into electronic format, I like the idea of having the books available in a searchable electronic format. And certainly this is a must have feature for any newly written book.

Recently, I got two invitations to write for books. The first was to write a book on Network Coding. I felt that I was not the best person so I did not accept. If I had, then I would have insisted on a free electronic copy. Second, I got an invitation to co-write a chapter on Cost Sharing with Mohammad Mahdian for a book, Algorithmic Game Theory, edited by, Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani. I agreed to this because I felt that such a book is a great idea and I could make a positive contribution. My selfish motive was to spread knowledge of the subject to which I have contributed. And, I guess that was also the expected motive of the other contributors. This I could say because the explicit incentive offered in the invitation to the contributors was that the editors (originally Eva and Vijay only) have made an excellent deal with a publisher, Springer Verlag. The deal they have is $40 for up to six hundred pages. I am not sure whether it is a paper back or hard-cover. But that was not my focus anyway. My focus is the absence of any electronic publishing component in the deal. Because of that, I felt this is not such a good deal in today's electronic age. On one side we are talking about scanning paper books, starting electronic journals, writing wikis, blogs and on the other we do not even make a deal on electronic publishing of newly written books. I wrote an email back to the editors that I do not think Springer deal is a good one. I was hoping to get back a response and start a discussion with them on this, which IMO, was obligatory for them because I point blank disagreed with the incentive they explicitly offered. At this point I am assuming that there is no electronic publishing agreement with the publisher. This was the background.

Now, I realize that this is not something to discuss with the editors in private. This is an important issue which is likely to reoccur in other situations. So I requested this space from Lance so that I could discuss with the whole community. Following are some of my random thoughts and I like to hear everybody's thoughts too, random or not :-) Please press the comment button and put your thoughts in writing so that Springer and other publishers would know what we want from them.

There are at least two kinds of books. First kind, written by individual authors. Second kind, written collaboratively by the community like the above proposed Algorithmic Game Theory. Individual authors write books for various reasons and it is up to them what kind of deal they lock with the publishers. The books written by a community has a predetermined goal and that is to spread the knowledge of the subject. It is not up to one or two persons to lock whatever deal they think is great. So the community must form unspoken guidelines to facilitate the negotiation between editors and publishers. These unspoken guidelines must include minimum desires of the community. Such a set of guidelines would have resolved the prisoner's dilemma for me. I did not like the absence of electronic publishing agreement. If I decline the invitation then the book still has gone ahead without my contribution and if I accept the invitation, which I did, then I know that my efforts are not optimally used. But in case it were a common expectation from the editors to negotiate an electronic publishing agreement, then I know that I could reject the invitation because others invitee would also do the same, thereby insisting that the editors go back to the publisher and make an electronic publishing agreement. One would ask why publishers have any electronic publishing agreement. For information, Reinhard Diestel's book, Graph Theory, has a free searchable and hyperlinked electronic edition and further this book is published by Springer Verlag. Let us first discuss what Springer provides to us and what we provide to Springer. Then we should discuss whether we are getting the optimal deal.

1. Springer does the marketing which sells the book.
2. Springer provides the brand name which sells the book.
3. Springer provides the brand name which makes the line in our resume about the book a bit bolder.
4. Springer prints and binds the book, for which the buyer pays.
5. Springer gave peanut financial support ($2000) to pay to students to draw pictures. This fund is for those contributors who do not have their own funds.

We give to Springer

1. Free content and transfer copyright so that they can legally publish the content. I am assuming there is no royalties involved in a community written book.
2. Word of mouth marketing.
3. Use our own funds for other expenses.
4. Our university or companies resources.

What are the possible deals we could have:

1. Status Quo. Springer publishes the book and sells them. Takes the copyright and does not provide free electronic copy. In future, if Springer wants, makes more money from electronic copy too.
2. Reinhard Diestel model. Provides free searchable and hyperlinked electronic edition. A user can't conveniently print the pages.
3. Springer publishes the book and sells them. Takes an exclusive time bound license, say one year. After one year, Springer still keeps the exclusive license on the paper publishing, but we could put the free electronic copies on our webpages.
4. Springer publishes the book and sells them. Takes the exclusive right to publish the book in paper format — that's all it needs to legally publish the book. We keep all other rights. We put the book in electronic format on our webpages or at some cheap servers.

Note that in all the above 4 options Springer is still getting something for free — the content. So it still is a good deal for Springer. 1. is the best deal for Springer. The only reason Springer could insist on 1. is because we do not insist with unity (Reinhard probably insisted very hard). If we insist then we could possibly get them to agree on 4. It is an irony that this book is about Game Theory, and the game theory principles are not used to get a better deal. Mohammad suggested that even if Springer wins on getting the first deal, we could still put our chapters on our webpages. This does not make sense because of three reasons. First, there are going to be cross-references. Second, the chapters together provide a synergy and that's the reason we all agreed to put our chapters together. Third, if we could all put chapters on our webpages then why can't we compile them together and put on a single webpage. A book is more than the sum of its chapters. A question which is typically raised about free electronic version is the following. If people could download the book for free then why would they buy from Springer? I think people would still buy, libraries would buy, professors would buy and anybody who needs to read a significant part of the book would buy. Still, for a moment let us assume that people won't buy the paper book in the presence of a free electronic version. In this case, it simply means people want only the free electronic version and not the paid paper version. That is having only the electronic version is what everybody desires. Then, under this assumption, why even deal with Springer?

Because, as mentioned above, Springer provides some value. We could still avoid Springer and create these values ourselves. We anyway will be spending couple of thousand hours on this book (my experience on working with Vijay is that it takes at least few hours per page). There are at least two ways to avoid Springer.

1. We go to a small publisher and get the book published. Transfer the exclusive right to publish the book in paper format. We keep all other rights.
2. We publish only the electronic version.

What role would Springer play?

1. Springer does the marketing. We will discuss this later to see how we could do the marketing ourselves.
2. Springer provides the brand name to sell the book. I think the brand name of the editors and the authors is much more in this case. This is also the case with any good book written by a community.
3. Springer provides the brand name to make the line related to this book in our resume a bit bolder. First, most authors contributing in the book already have enough lines in their resume that they can do with one fewer line. Second, this line is minor for a community written book. Each person contributes a chapter, may be equivalent to writing one or two journal papers.
4. Springer prints and binds the book. I do not know how much it costs to print and bind the book. "The Search" by John Battelle is a three hundred page hard-bound book and available at 16 bucks at Amazon. Well The Search probably will sell more than this technical book. But it shows that $40 for Algorithmic Game Theory could very well be an optimum profit making point for Springer rather than a favor as they want to portray to us. A small publisher would be able to beat that even in the presence of competing free electronic version.
5. The last is the peanut financial support. I am sure we could arrange $2000 bucks without Springer. Even if we fail, grad student would be happy to contribute this for a credit. If I do not personally have time to draw pictures, then I do not mind having a co-author who does that for me. A picture is worth thousand words. If I am claiming authorship for writing thousand words then anybody who draws pictures deserves the equal credit.

So the only value Springer provides is marketing. There are various ways we could do that too.

1. We create a pamphlet and a poster which we distribute to the program chair of various conferences.
2. Put the electronic version at one place. Let each of the contributor links to it. If there are fifty links from places like, Cornell, Georgia Tech, Stanford then on searches related to the keyword in the book, the book should show up at the top.
3. Let Citeseer crawl the book, let Google crawl the book, let us upload it on Wikipedia.
4. Even if it is not sufficient then we could market for money via search engine paid listing. We could raise the money by having only one or two ads in the book, let us say in the content and index pages. If we have an electronic version we could even have Google Adsense ads at the book download page. Certainly Google Adsense would put ads for academic people. In this case, if we are anyway buying something we could buy through those ads.

One question which one could raise is that many people in the world still live on the other side of the digital divide. But such people do not have $40 bucks either. The solution for them is to have a publisher in India or China to publish this book and sells to these people.

Pre-bottom line is we give more to Springer than it is giving back in return. Game theoretically it is not a fair solution and we could do better. I am not sure whether there is any electronic publishing deal which the editors of this book have with the publisher, if they had then they probably would have told me. In any case this posting is about many others future books which will be written co-operatively. Bottom line is, any book which is not written for money must be available free of charge in an electronic format.

Theory at NSF

From Sanjeev Arora

Bill Steiger of Rutgers is the new NSF program officer in charge of Theoretical Computer Science (TCS) and he has assumed this position now. There appear to be other ongoing changes within the Theoretical Foundations cluster. As CCF director Foster explained at STOC, up to 30% of the funds in the cluster will be placed in a fund which will give out grants via a centralized mechanism. (It is still unclear what the final effect will be on TCS funding.)

NSF program directors would also like to make members of the theoretical computer science research community aware of the following upcoming proposal deadlines:

• Networking Technology and Systems (March 2)
• Cyber Trust (March 6)

Proposals that explore fundamentally new (emphasis mine) ideas about network design and information security are sought, and participation by the TCS community is welcome.

Realistically, these will probably involve TCS researchers teaming up with experimentalists to develop proposals that focus on rigorous approaches to well motivated problems in networking and security and that have a significant theoretical component as well as a significant experimental component.

What Arora leaves unsaid is that there are no NSF general programs in core theoretical computer science accepting new solicitations this year.

Favorite Theorems Preview

I have written up my ten favorite theorems for the decades 1985-1994, 1995-2004 and 1965-1974. This year we tackle the remaining decade 1975-1984, the second major decade in complexity and the decade leading up to when I started graduate school in 1985.

The first decade set the groundwork for computational complexity and the P versus NP problem. In the second decade attempts to understand and solve the P versus NP problem led to new and interesting questions that still challenge us today. But we most remember the second decade for analyzing different models of computation such as alternation, parallel, probabilistic, circuits, interactive proofs and the first hints of quantum computers.

Starting next month I will run down my favorite theorems of the decade that showed that the tools of computational complexity can help us understand efficient computation in whatever form it comes in.

Sports Droughts

We watched the Chicago Bears Football team lose to Carolina with some friends who were extremely pessimistic the entire game, even though the game remained close throughout. "We haven't seen the Bears win the Super Bowl in twenty years, they will continue to disappoint us."

Let's consider the twenty year statement. Let's assume that each year every team has an equal probability of winning and each year is independent of each other. Then the expected number of years between championships is equal to the number of teams, 32 in the National Football League. So the Bears are still ahead of the curve, not disappointing at all.

So how about the 86 years between the Boston Red Sox World Series championships in baseball, the 88 years between Chicago White Sox championships, and the 98 years since the Chicago Cubs last won? This is just the coupon collector problem where if one draws numbers 1 to n with replacement independently and uniformly, it will take an expected n ln n draws to see every number. For the thirty baseball teams, that makes 102 years. There was no curse for the Red Sox, White Sox and Cubs, just probability working as expected.

I'm cheating on many fronts. The number of teams in both football and baseball have grown dramatically over the past few decades. Each year is not independent; a good team one year will likely be good the following year. Teams do not have an equal probability; especially in baseball the richer teams have a higher chance of winning.

Nevertheless you have no one to blame for long losing streaks other than those evil gods of probability.

The Defense

In the third Complexitycast we talk about the Dutch Defense with new Ph.D. Troy Lee and several of the participants in his ceremony. MP3 (18 minutes, 3 MB)

Time to Write the Letters

Every year I seem to write more letters, letters for those applying to graduate schools, letters for those looking for their first postdoc or assistant professor jobs, letters for tenure cases. Why the continual increase? More and more we see young researchers taking multiple postdocs, where each round of searching requires a set of letters. Letters from senior people carry more weight, and each year I get another year senior.

But the Internet has led to an increase in requests because one can now have automated processes that send requests for letters. Harry Buhrman has two complaints about this model.

1. Often these automated requests seem cold. Even automated they could ask in a nice way, be grammatically correct and address the person directly.
2. Universities should pay at least some small amount of money to letter writers or their institutes. This will keep down the number of requests and reimburse the letter writers for some of their time.

I second Harry's first point, though for me I never even look at words in a request, I just want to know where to send the letter.

I don't agree with Harry's second issue. We have a responsibility to write letters for our students and colleagues. The marginal cost of a sending an additional letter for someone is rather small, though the universities should make the process as painless as possible. A URL I can click and then upload is best. Having to cut and paste a username and password sent in an email is already adding effort for me with no increased security. For one graduate program I had to go through ten web pages of forms to fill and verify; there is no excuse for that. Ideally I would like some place I can just deposit the letter which legitimate universities could just download as needed.

For tenure letters perhaps a payment scheme would make sense. These letters require much more effort and we only write one of them for each candidate.

My Second Home

My first trip to Amsterdam came during a whirlwind European tour in the summer of 1984 during my undergrad years. My second trip was for the 1994 Complexity Conference (then called Structures). I spent my sabbatical year in Amsterdam 1996-97 and have come back about once a year since.

For the past several years I have stayed at the same hotel (NH Tropen), rented a bike from the same shop with the same sarcastic woman behind the counter who now recognizes me when I arrive. I know where to jog, where to get groceries and gifts for the kids. I don't need instructions to get to the hotel from the airport or a map to get from the hotel to CWI or the CS department at the University of Amsterdam. Maybe there are better hotels or bike shops but familiarity makes life easier.

Some of the faces have been around since my sabbatical and well before: Paul Vitanyi, Leen Torenvliet, Peter van Emde Boas and Harry Buhrman, the last of which I have written more papers with than any other co-author. Some faces I see for the first time. Today I am going to my fourth Ph.D. defense in Amsterdam as a member of the opposition.

I don't visit the tourist sites, the museums, the "coffeehouses", the red light district. I come to see old colleagues, make new ones, hopefully prove some theorems and enjoy my second academic home.

Counting Go

This week I am making my nearly yearly visit to CWI in Amsterdam, where I spent a sabbatical year in the 90's. I will sit on the opposition on Troy Lee's Ph.D. defense on Wednesday. Troy was a paranimf at Hein Röhrig's defense where I also sat in the opposition two years ago.

At CWI we also find John Tromp who works on various puzzles. Now he is counting Go positions. Tromp and his co-author Gunnar Farnebäck show that legal positions are colorings of the grid to {white, black, empty} such that every white or black connected component borders an empty node. They have exactly counted the number of positions on boards up to 16x16 and have an asymptotic bound on larger boards.

If you really want to know the exact number of positions of the standard 19x19 board and have a server with ten terabytes of disk space to spare, John would love to hear from you.

A Search Without End

Finding the 5th moon of Jupiter was a big deal. Finding the 14th moon was a big deal. But it's hard to get excited about the 63rd moon. Now imagine if Jupiter had an infinite number of moons.

New York Times, August 29, 1989

After more than a year of computation, six researchers at a California computer company have found the largest known prime number, which is 65,087 digits long and would fill more than 32 double-spaced typed pages.

While the search for the largest prime may seem like an esoteric pursuit, one of the researchers, Landon Curt Noll, said the work that permitted them to discover the number has a wide variety of commercial and scientific applications.

Associated Press, March 31, 1992

Mathematicians using a supercomputer have advanced the quest of a 17th-century French monk (Mersenne) by discovering the largest known prime number. The number begins 174 135 906 820 087 097 325 and goes on and on and on for 227,832 digits, filling 32 pages of computer paper.

Jeffrey Lagarias, a mathematician at A.T.& T. Bell Laboratories in Murray Hill, N.J., said that the discovery might have some significance in pure number theory but that "it's not going to revolutionize anything."

New York Times, March 29, 2005

An eye surgeon in Germany has discovered the world's largest known prime number—or at least his computer did. The surgeon, Dr. Martin Nowak of Michelfeld, is among thousands of participants in the Great Internet Mersenne Prime Search, one of several big projects that tap idle computers worldwide. The number, rendered in exponential shorthand, is 2^25,964,951-1. It has 7,816,230 digits, and if printed in its entirety, would fill 235 pages of this newspaper.

"Finding an additional prime doesn't enlighten us very much," said Dr. Andrew M. Odlyzko, a mathematician at the University of Minnesota.

Associated Press, January 3, 2006

Researchers at a Missouri university have identified the largest known prime number, officials said Tuesday. The number that the team found is 9.1 million digits long. It is a Mersenne prime known as M30402457—that's 2 to the 30,402,457th power minus 1.

The team at Central Missouri State University, led by associate dean Steven Boone and mathematics professor Curtis Cooper, found it in mid-December after programming 700 computers years ago. "We're super excited," said Boone, a chemistry professor. "We've been looking for such a number for a long time."

Why?

A Classical World

We need to rewrite the traffic laws in this country because they don't handle flying cars. We don't have flying cars, you say. We might have flying cars in the next couple of decades so the current traffic laws no longer apply.

Keep that argument in mind as you read the following paragraph from David Bacon.

If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.

Dangerous indeed. Bacon is not the first one to make such statements, Gilles Brassard made much stronger pronouncements as far back as 1990.

Did the theory of relativity mean the hard work of classical mechanics was in vain? Of course not. When we drive a car we don't need to worry about relativistic effects, they simply don't amount to much at that level.

We don't know how quantum mechanics will actually play out in a computer that would require the entanglement and manipulation of tens of thousands of quantum bits. Maybe we can harness the full power of quantum computation, maybe we can't. At this point we simply don't know.

I support research in quantum complexity, as long as quantum computing remains a possibility we should try and understand its computational power. But not until we all have fast quantum computers on our desks should we even think of abandoning classical complexity. And in our current state of affairs, where creating a quantum computer that factors faster than my daughter is a pipe dream, classical computational complexity serves us very well indeed.

The Technology of Academic Papers

The Internet has led to a complete shifts in how we deal with storing and sharing information, but when it comes to academic papers the changes we see are ad hoc and added in a piecemeal basis.

Suppose we could start from scratch and create a proper system for research papers. Here is how I would envision such a system.

XML has become the standard for storing information on the internet; it gives a simple machine-readable method for creating tree structures. Academic papers have such a tree structure (Sections, subsections, theorems, proofs, etc.) that would lend it itself well to XML. Mathematical equations should also be written using XML, we already have a MathML specification for doing this.

A academic paper XML file would only have content information, not any formatting information. For this we would use XSL files, themselves XML files that describe how to format the document. You would use different XSL files depending on whether the paper is viewed on the screen or printed, and different publishers can develop their own XSL files to have consistent looking papers. LaTeX, the system used by most theoretical computer scientists, has similar capabilities but because LaTeX does not enforce any standards, changing style files often requires considerable editing.

Researchers will not have to create these XML files directly (unless they want to) but can use word processors that will save the documents according to those standards.

For citations we should just point to a unique identifier for a paper, no longer should we need to cut and paste bibliographic information. The formatting program can go online based on the identifier to get the information to create a human readable bibliography with web links if appropriate. Most publishers already use Digital Object Identifiers (DOI), we just need DOIs to point to an XML file giving bibliographic information, have DOIs for unpublished papers and have a method for DOIs to point to a later version of a paper.

The author information on academic papers are often useless (like my postal address) or out of date as academics change locations. Each academic research should get their own DOI-like number that points to an XML file giving personal and contact information and then we only need add these DOIs to the academic papers.

Most importantly we need to have enforced standards for each of these XML documents (via XML schemas). If we can truly separate the content from the formatting of documents, and make that content available in an easy machine-readable forms, not only can researchers focus more on the writing and less on the style but will also open the door to applications that we cannot even imagine today.

A Year of Incompleteness

Edited from an email by Jan van Leeuwen and Jiri Wiedermann

The year 2006 will be a special year for the foundations of logic and theoretical computer science because on April 28, 2006 it will be 100 years ago that Kurt Gödel was born.

In 2006 it will also be exactly 75 years ago that Gödel's incompleteness theorem was published and 50 years ago that he wrote his famous letter to von Neumann which is now recognized as one of earliest recognitions of what we now know as the P-versus-NP problem.

Gödel's 100th birthday is beginning to receive some attention among logicians. There will be an International Symposium commemorating "the 100th jubilee of the birth of Kurt Gödel" in Brno (Czech Republic), the city where he was born, a Gödel Centenary 2006 Symposium in Vienna with a special lecture by Roger Penrose, and also at CiE 2006 there will be special attention for Gödel's "legacy for computability".

We note that 2006 also marks the 100th birthday of Richard Rado (well known as a great combinatorial mathematician and born on the same day as Gödel) and also of the well-known statistician William Feller.

Year in Review

Paper of the year goes to Irit Dinur's PCP Theorem by Gap Amplification. We will never teach the PCP theorem the same way again. Concept of the year goes to the Unique Games Conjecture, with its applications to hardness of approximation and metric embeddings. We've also seen the settling of the complexity of Nash Equilibrium in matrix games, list decoding better than we had hoped for and much more.

This was the year that Theory Matters and we welcomed several new bloggers in our community including Scott Aaronson and D. Sivakumar.

A good year for math in the media. The year started with a series about a crime-solving mathematician and ended with a game show about probability, with both shows continuing into 2006. Walk into any bookstore and you'll see a number of popular books on mathematics like Mario Livio's The Equation That Couldn't be Solved and Stephen Hawking's God Created the Integers. Perhaps the biggest disappointment came from the movie Proof which never had enough traction to get a wide release in the US.

Did I mention the White Sox won the world series?

Thanks to guest bloggers Rahul Santhanam and Ryan O'Donnell, guest posters Boaz Barak, Ron Fagin, Bill Gasarch, Michael Mitzenmacher, Rocco Servedio, Rakesh Vohra and my first two podcast guests Bill Gasarch and Scott Aaronson. Thanks to all of your for your comments, emails, support and just reading my rambling thoughts.

In Our Memory: George Dantzig, Seymour Ginsburg, Frank Harary, Leonid Khachiyan and Clemens Lautemann.

Have a great New Year's. More fun in 2006.

Start Your Engines

Many fields, like mathematics and economics, have a civilized recruiting process. They have their annual conferences in January with organized meetings between graduate students and postdocs looking for academic positions and members of the faculty recruiting committees from many departments. Some serious weeding is done in both directions and then only a small number of candidates are then considered for positions in each department. The whole hiring season is mostly over in a month or two.

Computer science has no such civilized process. We have no annual meeting that can serve to bring job candidates and recruiters together. So we have a much more haphazard process that starts in earnest in January and doesn't wind down until May or June. We need a better process.

Some advice to the job seekers.

• Apply early and often. Get your applications out by the end of December even if there is a later stated deadline. Faculty start looking at applications in January and you want your name to be there. Don't take the lack of an announcement or lack of mention of a theory position to deter you from applying to an institution.
• If you are not sure whether to apply then apply. You don't have any decisions to make until you have two offers in hand.
• Make a web page that sells you. Make the page visually appealing. Put links to all your recruiting material (CV, Research and Teaching Statements) as well as electronic versions of all of your papers. Just as important remove the embarrassing pictures at least until you have your offers.
• Use personal contacts. Contact professors you know and let them know you are job hunting and ask if they know of positions at their school or others.
• Start working on your job talk now. Make it accessible to a general computer science audience while convincing the theorists you have some meat in your results. Practice the talk with your fellow graduate students and faculty in your department.
• Be patient. Many positions are tied up for a few months until the top few candidates make some decisions. The market will shake out, just give it time.

Deal or No Deal

A new US game show started last week, Deal or No Deal hosted by Howie Mandel (the same Howie from this post). A New York Times article describes the game as a exercise in probability.

Twenty-six briefcases are distributed to 26 models before the show begins. Each case contains a paper listing a different dollar amount, from one penny to $1 million. At the start of the game, a contestant chooses one case, which becomes his; he is then allowed to see the sums in six of the remaining cases. After these have been disclosed, a mysterious figure known as the Banker calls the set, offering to buy the contestant's case for a sum derived, somehow, from the cash amounts that are still unrevealed.
The contestant can take the offer and cash out, or move on to the next round, during which he's allowed to open five more briefcases before the Banker's next offer. The second offer might exceed or fall short of the first offer, but it clearly reflects the newly adjusted odds about what the contestant is holding. If the contestant refuses it, he requests to see the contents of four, three, two, and then one more case, with offers from the Banker coming at the end of each round. Each time the contestant can accept and end the game, or proceed to the next round. If he doesn't accept any of the offers, he is left with the sum in his own case.
Is it wise to take a bank offer when it's below the mathematical expectation, as it always seems to be? As the game goes on, the offers asymptotically approach mathematical expectation; maybe contestants should wait.

If the contestant just wanted to maximize the expected value of their winnings they should always turn down the Banker, but many do accept the Banker's offer. Are they acting rationally?
When the amount of money involved becomes a significant fraction of the contestant's net worth, a contestant becomes risk averse and is often willing to accept a sure amount rather than an expected higher amount.
Economists model this phenomenon using utility theory. A person has a utility function of their net worth, usually with first derivative positive and second derivative negative (think square root or logarithm). They aim not to maximize expected net worth, but expected utility which leads to risk aversion. For example, if you had a square root utility then you would be indifferent to having a guaranteed net worth of 360,000 and playing a game that would give you a net worth 1,000,000 or 40,000 with equal chance.
Economists can't afford to run these experiments at their universities; they can't offer enough money for serious risk averse effects to kick in. But television game shows like this do give us a chance to see risk aversion in action.

All I Want for Christmas is a Proof that P≠NP

For the first time in my lifetime, Christmas and Chanukah land on the same day. So to all my readers, Happy Holidays!

And what do we find under our theory Christmas tree? Our first present is a new randomized polynomial-time algorithm for linear programming from Kelner and Spielman. The card reads

In this paper, we present the first randomized polynomial-time simplex method. Like the other known polynomial-time algorithms for linear programming, the running time of our algorithm depends polynomially on the bit-length of the input. We do not prove an upper bound on the diameter of polytopes. Rather we reduce the linear programming problem to the problem of determining whether a set of linear constraints defines an unbounded polyhedron. We then randomly perturb the right-hand sides of these constraints, observing that this does not change the answer, and use a shadow-vertex simplex method to try solve the perturbed problem. When the shadow-vertex method fails, it suggests a way to alter the distributions of the perturbations, after which we apply the method again. We prove that the number of iterations of this loop is polynomial with high probability.

Our next present is a list-decodable code from Guruswami and Rudra. Back in October I posted about the Parvaresh-Vardy code that list decode a 1-ε fraction of errors using a code of rate O(ε/log(1/ε)). Guruswami and Rudra, for any constant δ>0, create a code with rate ε-δ.

Many more presents under the tree, presumably many STOC and Complexity submissions. No proofs (at least correct ones) that P≠NP this year but maybe Santa will come through for us in time for next Christmas.

A Second Helping of Numb3rs

I've been catching up on my Tivo on the second season of Numb3rs, the CBS television series about a math professor Charlie Epps who uses math to help his brother at the FBI.

Most of the episodes this season do a nice job explaining mathematical concepts including several relating to theoretical computer science (see below), though the connections between the math and the plot get more and more tenuous.

A couple of Numb3rs related web sites give more details on the mathematics described in the show. Texas Instruments created a site giving high school level descriptions and activities on the topics discussed in the show including Voronoi Diagrams, Entropy, Eulerian Tours, Steiner Trees, Error-Correcting Codes, The Art Gallery Problem and Pseudorandom Numbers. Also, a Northeastern professor writes a weblog giving more detailed mathematical explanations of the topics on the show.

In my favorite episode of the season Convergence, a rival mathematician gives a talk finding a hole in the proof of the Epps Convergence, Charlie's best work. This causes Charlie to go through an introspective phase questioning whether his FBI work keeps him away from doing his real research as a mathematician. He considers the importance of being a mathematician while being part of a larger world, philosophical issues that many real mathematicians also contemplate.

Pulling Out The Quantumness

A recent comment made the mistaken assumption that if NP is in BQP (efficient quantum algorithms) then the whole polynomial-time hierarchy lies in BQP. We do know if NP is in BPP (efficient probabilistic algorithms) then PH is in BPP. Why the proof doesn't work for BQP illustrates an interesting difference between probabilistic and quantum computation.

How do we prove NP in BPP implies PH in BPP? Let me just do NP^NP ⊆ BPP, the rest is an easy induction. We use the following inclusions.

NP^NP ⊆ NP^BPP ⊆ BPP^NP ⊆ BPP^BPP = BPP

The first and third "⊆" are by assumption, the "=" is by simulation. To get NP^BPP ⊆ BPP^NP we first make the error of the BPP algorithm so small that a randomly chosen string will give, with high probability, the correct answer for every query made on every computation path of the NP algorithm. We can then safely pick a random string r first and then make an NP query that simulates the NP algorithm which will use r to simulate the BPP queries.

Now suppose we wanted to show NP in BQP implies PH in BQP. We just need to show NP^BQP ⊆ BQP^NP, the rest works as before. Like the BPP case we can make the error of the BQP algorithm very small, but we have no quantum string that we can choose ahead of time. In probabilistic algorithms we can pull out randomness and leave a deterministic algorithm with a random input but we don't know any way to pull the quantumness, even with quantum bits, out of a quantum algorithm.

Whether NP^BQP ⊆ BQP^NP remains an open question. Showing NP^BQP ⊆ BQP^NP or finding a relativized world where NP^BQP is not contained in BQP^NP would give us a better understanding of the mysterious nature of quantum computation.

Favorite Theorems: First Decade Recap

After I chose my ten favorite theorems in the decades 1985-1994 and 1995-2004, I went back to the first decade in complexity. Here is a recap of my ten favorite theorems in computational complexity from 1965-1974.

• The Seminal Paper (Hartmanis-Stearns)
• Efficient Computation (Cobham-Edmonds)
• NP-Completeness (Cook)
• Combinatorial NP-Complete Problems (Karp)
• The Polynomial-Time Hierarchy (Meyer-Stockmeyer)
• P = NP for Space (Savitch)
• Abstract Complexity (Blum)
• NP-Incomplete Sets (Ladner)
• Logical Characterization of NP (Fagin)
• Defining the Future (Cook-Reckhow)

I wrote the first two lists at the end of their respective decades but for this last one we have over thirty years of perspective. For example, at the time one might have included some of the difficult results that related the complexity of different Turing machine models (number of tapes, number of heads, number of dimensions of tapes and others) that seem less important today.

We have one missing decade, so some more list making next year.

SIGACT News

In the chair's letter of the December SIGACT News, Richard Ladner points to this and other weblogs for discussions about the FOCS Business meeting panel discussion. In case you have come here for that reason, you can find those posts here, here, here, here, here and here.

Also in this month's SIGACT News, Neil Immerman writes a guest complexity column on Progress in Descriptive Complexity (which defines complexity classes using logical structures), Karp publishes his committee report on TCS funding, Tim Roughgarden interviews the STOC best student paper award winner Vladimir Trifonov and much more.

For a mere $18 ($9 for students), you can become a SIGACT member and get SIGACT News in print and online, online access to some other ACM theory publications, reduced rates at conferences and feeling good about just helping out the theory community. (Full disclosure: I'm currently vice-chair of SIGACT. You should join anyway.)

I'll end with the Quarterly Quote from the latest issue.

I'd like a large order of FiboNachos.

Okay sir, that'll cost as much as a small order and a medium order combined.

What is PPAD?

Christos Papadimitriou gave an overview talk at the NIPS conference last week and mentioned the new result by Chen and Deng showing that, given the payoff matrix, the complexity of computing a 2-Player Nash Equilibrium is PPAD-complete.

NIPS is mainly an AI conference and some of my Machine Learning friends, who have a good understanding of NP-completeness, went around asking who knew what PPAD-complete meant. They got many blank stares and a few confusing answers.

So what is PPAD? Let's start with TFNP (Total Functions in NP). Consider a polynomial-time computable predicate P(x,y) where for every x there is at least one y such that P(x,y) is true. A TFNP function is the problem of given an input x, finding a y such that P(x,y).

The interesting TFNP functions come from combinatorial theorems that guarantee solutions. One such theorem, called the Polynomial Parity Argument (PPA), is given a finite graph consisting of lines and cycles (every node has degree at most 2), there is an even number of endpoints.

The class PPAD is defined using directed graphs based on PPA. Formally PPAD is defined by its complete problem (from an earlier post): Given an exponential-size directed graph with every node having in-degree and out-degree at most one described by a polynomial-time computable function f(v) that outputs the predecessor and successor of v, and a vertex s with a successor but no predecessors, find a t≠s that either has no successors or no predecessors.

Besides two player Nash, arbitrary k-player Nash and a discrete version of finding Brouwer fixed points are also complete for PPAD.

So how do we explain this Nash Equilibrium result say when we try to explain the result to economists and AI folk. Just say Nash Equilibrium for 2-player games has the same complexity as k-player Nash and finding fixed points and we have some evidence that no efficient solutions exist for such problems.

Physicists and Complexity

In my second Complexitycast, Scott Aaronson and I try to answer the question "What should physicists know about computational complexity?" MP3 (21:52, 3.8MB)

Intellectuals and Science

Nicholas Kristof writes in a New York Times op-ed column The Hubris of the Humanities (paid subscription required) that the lack of appreciation for science comes not only from the masses but even from the intellectual elite.

The problem isn't just inadequate science (and math) teaching in the schools, however. A larger problem is the arrogance of the liberal arts, the cultural snootiness of, of … well, of people like me – and probably you.

What do I mean by that? In the U.S. and most of the Western world, it's considered barbaric in educated circles to be unfamiliar with Plato or Monet or Dickens, but quite natural to be oblivious of quarks and chi-squares. A century ago, Einstein published his first paper on relativity – making 1905 as important a milestone for world history as 1066 or 1789 – but relativity has yet to filter into the consciousness of otherwise educated people.

Most of the intellectuals I know are well-versed in the sciences but that is the company I keep. But we do expect the well-learned computer scientist to have read their Shakespeare and we don't expect English professors to know diddly about NP-completeness (or calculus for that matter).

After giving the usual statistics like 40% of Americans don't believe in evolution Kristof ends with the following.

But there's an even larger challenge than anti-intellectualism. And that's the skewed intellectualism of those who believe that a person can become sophisticated on a diet of poetry, philosophy and history, unleavened by statistics or chromosomes. That's the hubris of the humanities.

UG-Hard

We have seen many exciting papers based on the unique games conjecture for example that improving the Goemans-Williamson approximation algorithm for Max-Cut would imply P=NP if the unique games conjecture is true.

Many complexity theorists have told me that they have doubts and in some cases outright don't believe the unique games conjecture. What good are results based on a conjecture that complexity theorists won't stand behind?

The unique games conjecture states that a certain unique games problem is NP-complete. Even if unique games is not NP-complete, it still might be difficult to solve, a situation we believe for some other famous problems like factoring, graph isomorphism and Nash equilibrium. We've seen hardness results based on reductions from these later problems so perhaps we can do the same for unique games.

Most, if not all, of the theorems based on the unique games conjecture actually prove something stronger, they reduce the unique games problem to the approximation problem, e.g., improving the Goemans-Willamson bound would yield an algorithm that solves the unique games problem.

Let me suggest the term UG-Hard for the class of problems to which we can reduce the unique games problem. Theorem: Improving the Goemans-Williamson algorithm for Max-cut is UG-Hard. No conjectures necessary.

If the unique-games conjecture is true, the UG-hard is the same as NP-hard. If unique games are not solvable in polynomial-time then the UG-hard problems will not have a polynomial-time algorithm. And as long as we don't have a polynomial-time algorithm for unique game then finding an efficient algorithm for any UG-hard problem would imply settling the now major open question of the complexity of the unique games.

Texas Ice and Ribs

This week I am visiting the University of Texas in Austin. Yes, another football school, but they also have a boffo complexity group with Anna Gál, Adam Klivans and David Zuckerman as well as theorists Greg Plaxton, Vijaya Ramachandran and Tandy Warnow.

But what the school can't handle is the weather. Yesterday's high temperature in Chicago was 15ºF, low was 0 (-18ºC). People in Chicago bundled up and went to work as usual. Never in my memory has the University of Chicago closed due to weather.

In Austin, the temperature was a balmy 30ºF with a little rain. So they shut down the university and much of the rest of the town. Drivers in Austin cannot handle a little ice. Pathetic.

But the night was not a loss. Adam Klivans and his fiancée Jean took me to their favorite ribs place in Austin, The County Line. When we got there the restaurant had also shut down due to the weather. But Adam made such a good plea to the manager ("My friend came all the way from Chicago for your ribs"), that they gave us, free of charge, a tray full of beef and pork ribs, chicken and sausage (pictured below). We took them back to Adam's place and a good time was had by all.

Photo by Jean Kwon

Surprising Results

Guest Post by Bill Gasarch with help from Harry Lewis and Richard Ladner.

What are the surprising results in theory? By surprising we DO NOT mean surprising that they were PROVEN (e.g., PRIMES in P) but surprising that they were TRUE. Some results are surprising since people thought the opposite is true, but some results are surprising because people didn't even think in those terms. The latter we call BIG surprises. I will note which ones are BIG. Here is a list of results that were surprising on some level.

While compiling this list and talking to people one (obvious) thing really struck me: what people consider surprising is very much a function of WHEN they were in graduate school. For example, Median Finding in Linear time was a big surprise at the time, but we now teach it to undergrads who are not impressed. And neither are we.

1. Gödel's Inc. Theorem. (1931) REALLY surprised Hilbert and others. BIG Original Version Modern Version
2. HALT is undecidable. (1931–though in a different form). BIG
3. Multiplication in subquadratic time (Toom-1963, Cook-1966). Later improved to n log n loglog n (Schonhage-Strassen 1971) People did it in O(n²) for so long! BIG
4. Matching in Polynomial Time. (Edmonds 1965, Canadian Journal of Mathematics) Poly time seen as important. BIG.
5. Matrix Multiplication in O(n^2.87) time (less than n³ !!) (Strassen 1969).
6. The Speed Up Theorem–There are decidable sets that cannot be assigned a complexity intelligently. (M. Blum STOC69, JACM71)
7. Savitch's Theorem (JCSS 1970): NSPACE(T(n)) ⊆ DSPACE(T²(n)).
8. Cook's Theorem. (1971 STOC) EVERY NP-problem is reducible to SAT! (Cook also had CLIQUE–so I've left off Karp's 22 problems). BIG.
9. Equivalence problem for Regular Expressions with Squaring is EXP-SPACE complete (Meyer, Stockmeyer FOCS72). A `natural' problem proven to NOT be in P!
10. Median in Linear time (Blum,Floyd,Pratt,Rivest,Tarjan STOC72, JCSS73).
11. Super-Exponential Complexity of Presburger Arithmetic (Fischer-Rabin, 1974). A new way of looking at Hilbert's program and its difficulties.
12. Amortized Union-Find in Θ(nINVACK(n)). (Tarjan- 1975). Inverse Ackerman comes up naturally! First time?
13. P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975). BIG
14. Public Key Crypto (Diffie Helman, 1976, IEEE Trans Inform Theory, Rivest-Shamir-Adleman, 1978). Establishing shared key without meeting. In retrospect solved 2000 year old problem. BIG.
15. Permanent is #P complete. (Valiant 1979) BIG–Introduced #P.
16. Linear Programming in P. (Khachiyan 1979).
17. Integer Programming with fixed number of variables in P (H.W. Lenstra 1983) Note that the range of the variables is unbounded.
18. Shortest Path problem on planar graphs BETTER THAN O(n log n) (Fredersickson, 1983, FOCS). You don't need to sort!
19. Bit commitment⇒SAT in Zero Knowledge (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91) if φ in SAT, can convince you that φ in SAT without giving you a clue on how to satisfy it. Result did not relativize.
20. NSPACE(n) = coNSPACE(n). (1987-Szelepcsenyi-BEATCS, Immerman-1988-IEEECCC, SICOMP).
21. Fixed Parameter Tractability material—Hard to pin down ONE result. I was surprised at Vertex cover for fixed k in O(f(k)n³) via Graph Minor Theorem. Other candidates are solid evidence that Dominating Set and Clique are NOT Fixed Point Tractable. More progress on Vertex Cover (down to something like n+(1.34)^k + O(1)) and Subgraph Homeomorphism for fixed graphs in O(n³) (Robertson and Seymour).
22. Under assumptions, P=BPP (Nisan, Wigderson FOCS 1988, JCSS 1994). People had thought P ≠ BPP. BIG.
23. PH in P^#P. (Toda FOCS89, SICOMP91) PH is the Poly Hierarchy. #P REALLY powerful!
24. IP=PSPACE (Lund-Fortnow-Karloff-Nisan, Shamir FOCS90 JACM 92). Bonus: Proof did not relativize. BIG.
25. Connection between PCP and Approximation. (Feige,Goldwasser,Lovasz,Safra,Szegedy FOCS91, JACM96). BIG.
26. Factoring is in QUANTUM P (Shor 1994 FOCS). Natural candidate for QP-P ! BIG.
27. Limits on what we can prove about circuits (Razborov and Rudich STOC94, JCSS97).
28. Randomized approx algorithms for MAX CUT which are .87856.. OPT (Goemans, Williamson, 1995).
29. Grover's Quantum O(n^0.5) search algorithm (STOC 1996, Phy Review Letters 1997)
30. HALT is truth-table reducible to RAND, where RAND is Kolmogorov rand strings (Kummer STACS 96). All the people working on this problem (granted, not many) thought it was false.
31. Planar TSP has a PTAS. (Arora FOCS97, JACM98). Most people thought false.
32. Assuming Unique Game Conjecture Max Cut algorithm of GW is optimal unless P=NP (Mossel, O'Donnell, Oleskiewicz 2005FOCS)

How I Became a Theorist

Someone asked me recently how I became a complexity theorist? After all most high school students don't say they want to be a theoretical computer scientist when they grow up. Every one of us has a story. Here's mine.

In high school I wanted to be an engineer. "Using science to help society" read one brochure I saw in junior high. I applied to several engineering programs and matriculated at Cornell.

During my first semester in an engineering math class, the professor writes an equation on the board. I raised my hand "Why is that equation true?"

"We don't do that in this class" the professor responded.

I then dropped out of engineering and transferred within Cornell to the College of Arts and Sciences and started my life as a math major. My mother, convinced I would become an unemployed mathematician, talked me into a double major in math and computer science, which was a relatively easy double major at Cornell.

In my junior year, as part of the CS requirements, I took an introductory theoretical computer science class with Juris Hartmanis. I had found my calling and the rest, as they say, is history.

The Day After

Many of you submitted papers to the Complexity conference by yesterday's deadline, now you should let the world see them. Submit your papers to an archive center like CoRR and/or ECCC. It's never too late to submit your STOC submissions as well.

Talking about the ECCC, Xi Chen and Xiaotie Deng have posted a new paper that apparently shows that 2-player Nash Equilibrium has the same complexity as finding fixed points (PPAD-complete), extending the 4-player result I mentioned in October. A bit surprising, most of us thought that 2-player Nash would be easier to solve.

Complexity in the Mid-80's

Luca asked about the topics in the complexity courses I took in 1985 and 1986. I dug up my old course notes and wrote down what was covered. Some more in the intersection than I remembered.

Cornell University CS 682–Theory of Computation
Spring 1985
Juris Hartmanis

Recursion Theorem, Rice's Theorem, Myhill's theorem that all r.e.-complete sets are recursively isomorphic, Kolmogorov complexity, Relativization, arithmetic hierarchy leading to the polynomial-time hierarchy, Ladner's theorem, oracles for P=NP and P≠NP and some other hypotheses, Blum Speed-Up Theorem, Cook's theorem, isomorphism conjecture for NP-complete sets, Mahaney's theorem (Sparse NP-complete sets imply P=NP), Blum's axioms, probabilistic classes, random oracle hypothesis, E=NE iff no sparse sets in NP-P, Karp-Lipton, Union Theorem, Elementary and Primitive recursive functions.

Much of this course revolved around the isomorphism conjecture that Hartmanis felt at the time could lead to a proof that P ≠ NP.

On 2/18/85 Hartmanis stated that whether there is an oracle where PH is infinite is an open question and on 3/13/85 Hartmanis announced that Yao found such an oracle but no mention of how Yao's proof worked, i.e., no circuit complexity.

UC Berkeley CS 278–Machine-Based Complexity
Spring 1986
Michael Sipser

Turing machines, Cook's Theorem, Savitch's theorem, Path is NL-complete, alternation and PSPACE-completeness, Circuit valuation is P-complete and P/poly, Oracles and Random Oracles, Probabilistic classes, Undirected path in RL (now known to be in L), Graph Isomorphism in co-AM, Kolmogorov complexity, using Kolmogorov complexity to show BPP in the hierarchy, Karp-Lipton, Mahaney's theorem, Parallel Computation (NC and AC), CFL in NC², Parity not in AC⁰ (Furst-Saxe-Sipser, 4 lectures with mention of Yao and Hastad's improvements), Connections to oracles and bounds on depth-k circuits, Razborov's proof that CLIQUE does not have poly-size monotone circuits (6 lectures), Barrington's Theorem (bounded-width branching programs=NC¹).

Sipser ended the course talking about his approach to showing NP ≠ co-NP by trying to find a finite analogue of a combinatorial proof that the analytic sets are not closed under complement.

Many of the theorems in Sipser's course were proven after the start of Hartmanis' course such as graph isomorphism in co-AM and Razborov's theorem.

The First Saturday in December

This Saturday comes the annual William Lowell Putnam Mathematical Competition. The contest is open to undergraduates at American universities. Any number can compete but each university picks three members ahead of time to serve as the team for that school.

As a freshman I did well on practice exams and made the 1981 Cornell University Putnam team. I rewarded their confidence by scoring the median score that year, a zero. Needless to say they didn't put me on the team again and I didn't even bother taking the exam my senior year.

Some members of our community have done very well on national and international math competitions. Some have done not so well but have turned into strong scientists nevertheless. Other people who have excelled at these competitions have not had success as mathematical researchers.

What conclusion can we draw? It takes more than mathematical problem solving to make a good mathematician.

The Graduate Complexity Course

After my post on teaching PCPs, a reader questioned the wisdom of spending 6-8 lectures on PCP and asked what topics should be taught in an introductory graduate complexity course. This is not a new issue. In the spring of 1985 I took a graduate complexity course with Juris Hartmanis at Cornell and in the spring of 1986 took a graduate complexity course with Michael Sipser at Berkeley with only the polynomial-time hierarchy in the intersection of the two courses.

Here is my list of the topics and theorems that should be covered in a graduate complexity course. Depending on the school, some of this material is covered in undergraduate courses. More material should be added based on the interests of the instructor.

• DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪_cDTIME(c^f(n)).
• Basic time and space hierarchies.
• NSPACE(s(n))⊆DSPACE(s²(n)) and NSPACE(s(n)) = co-NSPACE(s(n)).
• The P versus NP problem and NP-completeness. SAT is NP-complete.
• The polynomial-time hierarchy.
• Alternation (Alternating polynomial-time = PSPACE).
• Probabilistic Complexity Classes (BPP, RP, ZPP). BPP ⊆ PH.
• Counting (PH ⊆ P^#P).
• The PCP theorem. Even if you don't do the proof, state the theorem and the implications for hardness of approximation.

Game Theory Finds Computer Science

Dear Game Theorist/Computer Scientist:

In keeping with our mission "to facilitate cross-fertilization between theories and applications of game theoretic reasoning," Games and Economic Behavior has decided to expand its publications of papers in the interface of game theory and computer science. To this end, we are pleased to announce that the following individuals have accepted our invitation to join the editorial board:

• Joseph Halpern, Cornell University
• Michael Kearns, University of Pennsylvania
• Noam Nisan, Hebrew University
• Christos Papadimitriou, University of California at Berkeley
• Moshe Tennenholtz, Technion - Israel Institute of Technology

Submitted papers will be subject to the journal's high standards of evaluation. In particular, they must be of interest and must be readable to researchers in other fields. Given the differences in the publication processes of different fields, GEB is not opposed to publishing expanded versions of papers that were originally published in conference proceedings (provided they satisfy copyright law).

We hope that you see GEB as a venue to reach a broad group of readers for your publications.

Sincerely yours,
Ehud Kalai
Editor GEB

Chess and Poker

Two very different articles in today's New York Times about battling the decline of interest in Chess. In the Op-Ed section, Jennifer Shahade, a recent US women's chess champion argues that chess should learn lessons from Poker.

How can chess save itself? No doubt it would make purists protest, but chess should steal a few moves from poker. After all, in the past few years, poker has lured away many chess masters who realized that the analytical skills they've learned from chess would pay off in online card rooms.

And that's a shame. There are plenty of smart people playing poker (and I love playing it myself), but there's no denying that when it comes to developing mental acuity, chess wins hands down, so to speak. Dan Harrington, a former world poker champion who quit chess because there wasn't enough money in it, laments that poker is thin and ephemeral in comparison.

Meanwhile in the Style section, Dylan Loeb McClain discusses the World Chess Beauty Contest which has the stated goal of raising interest in the game.

Why has chess been undergoing a decline in interest in recent years? Perhaps after Deep Blue defeated Kasparov in 1997 the world views the best chess player as a machine, reducing interest in the game for humans.

And we shouldn't lament poker so. Prime time coverage of a game that uses probabilities, Bayesian analysis and complex strategies can't be completely a bad thing.

Goodbye Computing Chris

Chris Leonard, Elsevier editor of the CS theory journals is leaving Elsevier to be head of communities of the digital music service Digimpro. Theory loses a friend in Chris who talked with many of us about our Elsevier concerns and ran his own weblog at Elsevier (and will continue blogging at a new site). Chris helped push through the free year of Information and Computation.

As he leaves he presents his list of important aspects of the "perfect" CS journal. Many good ideas to think about, though we need to ensure a proper peer review of every journal article.

Thanks for your work for our community Chris and good luck in your new career.

Teaching PCPs

Two years ago for the first time, I gave the proof of the PCP (Probabilistically Checkable Proof) theorem in my graduate complexity course. The result, first proved by Arora, Lund, Motwani, Sudan and Szegedy, shows that every language in NP has a proof where a randomized verifier requires only a logarithmic number of coins and a constant number of queries to the proof. The result has helped show hardness of approximation for a large number of optimization problems.

I worked off of Mahdu Sudan's lecture notes and spent 8 fifty-minute lectures and still required a considerable amount of hand waving.

This year I used slightly less than 6 fifty-minute lectures with much less hand-waving based mostly on Irit Dinur's new proof of the PCP theorem. The six included a lecture by Jaikumar Radhakrishnan on expander graphs on a day I was out of town. I departed from Dinur's writeup in two ways:

• I used Radhakrishnan's version of Dinur's gap amplification argument.
• I used the proof that NP has a PCP using a polynomial number of coins and a constant number of queries in Sudan's notes (Lecture 3, Part II) instead of the long-code test in the appendix of Dinur's paper.

With experience I should be able to cut the number of lectures to five and the expander graphs lecture will help with many other theorems in complexity, not the least of which is Reingold's construction putting undirected graph connectivity in logarithmic space.

If the students already know expander graphs, the proof takes half as much time as before. Thanks Irit. But still that one lecture proof of the PCP theorem remains elusive.

Complexity Deadline Approaching

The December 4th paper submission deadline for the Computational Complexity Conference in Prague is fast approaching. Get your papers ready.

Other deadlines: Computational Geometry (Abstracts Nov. 23), Electronic Commerce (Dec. 6), COLT (Jan. 21), ICALP (Feb. 10), SPAA (Mar. 6). Leave a comment if I left out your favorite conference.

The accepted papers for STACS and LATIN have been posted.

Introducing a Speaker

When a scientist visits another university to give a seminar, someone gets assigned as host who during the talk introduces the speaker, makes sure the talk doesn't go too long and the post-talk questions don't get out of hand.

So how do you introduce a speaker? I've seen everything from "Let's start" to a reading of the speaker's CV. A few memorable ones (names have been changed):

• Jane Smith needs no introduction so I'll introduce myself instead…
• Last week we had a terrible talk on ABC, today we will learn whether it was the speaker or the area.
• John Doe is famous for proving the XYZ theorem. Today he will talk about something far less interesting.

Often the host gets much more anxious about the introduction than the speaker does about the talk. The host worries the speaker will get insulted if given the wrong introduction. Just find a couple of nice things to say and you'll be fine.

Don't ask the speaker how he would like to be introduced, as it puts the speaker in an awkward position. Last time my host asked me, I suggested he introduce me as "The person who put the 'W' in AWPP," but he didn't bite.

Another Satisfied Customer

You attend the University of Chicago for three years, take a few years off and come back to finish your Bachelor's degree in Chemistry. You worked really hard to get that degree but you have trouble finding a job afterwards. What do you do? How about setting small fires in a number of University of Chicago buildings including the elevator in Ryerson Hall, home of computer science.

Luckily no one was hurt and there was very little property damage. Thanks to Nita Yack, our department administrator, and others who quickly put out the fire before it caused any real damage. Thanks also to the university and Chicago police who quickly caught the culprit.

Relativized Collapse of P and NP

When we teach relativization, we often ask the class for a set A such that P^A=NP^A. The usual answers we get are an NP-complete A (which doesn't work unless the polynomial-time hierarchy collapses) or a PSPACE-complete A which does work: PSPACE ⊆ P^A ⊆ NP^A ⊆ NPSPACE = PSPACE the last equality by Savitch's theorem.

According to Steven Rudich, a student at Carnegie-Mellon suggested using A=K, the halting problem. Does this work? This led to an interesting email discussion between Rudich, Richard Beigel, Lane Hemaspaandra and few more of us getting cc'd on the messages.

We need to use a reasonably dense encoding of K, such as the set of Java programs with no input that halt. Then in fact P^K does equal NP^K, but the proof is not as obvious as one would imagine. Think about it.

And if anyone knows the original reference to P^K=NP^K, let us know.

Cornell versus Intelligent Design

As a Cornell University alum I get the occasional email from the president talking about the great things going on on the Ithaca campus. Today's email I received from Hunter Rawlings, the old president who's minding the store while the university finds a replacement for Jeff Lehman.

This strength and stability of purpose allowed me to use this year's state of the university speech to address a matter I believe is of great significance to Cornell and to the country as a whole, a matter with fundamental educational, intellectual, and political implications. The issue in question is the challenge to science posed by religiously-based opposition to evolution, described, in its current form, as "intelligent design."

This controversy raises profound questions about the nature of public discourse and what we teach in universities, and it has a profound effect on public policy.

I believe the time has come for universities like Cornell to contribute to the nation's cultural and intellectual discourse. We must be willing to take on a broader role as defenders of rational thought and framers of discourse about culture and society. In this spirit, I have asked our three academic task forces, on life in the age of the genome, wisdom in the age of digital information, and sustainability, to consider means of confronting the following questions: how to separate information from knowledge and knowledge from ideology; how to understand and address the ethical dilemmas and anxieties that scientific discovery has produced; and how to assess the influence of secular humanism on culture and society.

Makes me proud to see my alma mater taking a proactive approach to this important debate.

The History of RAM

Janos Simon gives a history of RAMs expanding on my recent Favorite Theorems post.

A single paper is like a snapshot of the state of research at one point in time. Research itself is a dynamic, changing, live stream of results and ideas, and a single snapshot often cannot do justice to the richness of the topic. The RAM paper is an excellent summary of definitions and problems, and worth reading today, but, at the time, it seemed to me more like a crystallization of concepts that were "in the air" and a clear and precise summary of important known questions rather than trailblazing exposition of new ideas. The theory of RAMs is fascinating, and I'll try to summarize some of the relevant work that preceded Cook's.

The RAM formulation dates back to von Neumann (after all the "von Neumann architecture" IS a RAM). von Neumann uses the RAM formulation to derive instruction counts for some programs for his first computer. So "unit cost RAMs" were well known from the beginning of computers, and counting the number of operations was known to be important. Knuth was a very strong advocate of the idea of analyzing the running time of algorithms using instruction counts: the first edition of the first volume of The Art of Computer Programming is from 1968.

Theoreticians interested in computability theory have published extensively on RAMs: an example of an early paper is Sheperdson and Sturgis JACM 1963. It has a bibliography of earlier work. These papers came from two different motivations: one was to find further examples of formalisms equivalent to Turing machines, as a kind of experimental evidence for Church's Thesis (see the book by Brainerd and Landweber for an exposition of a few dozen formalisms—Markov Algorithms, Post Systems, λ-calculus, and so on). The other was to find "better", more realistic theoretical models for real computers.

For example, one of the novel features of the ENIAC was that the program actually resided in the computer's memory (as opposed to outside fixed set of instructions as in the earlier Harvard Mark machines). Much was made of this feature of "stored program" that allows for the program to use itself as data and modify itself on the run, something that was judged to be "good for AI." Of course, the existence of a two-state universal Turing machine is a clear illustration that at a fundamental level of computability there is no difference between "hardware" and "software". Still, there was a great deal of interest to model such "ease of programming" features at a theoretical level. For example, Juris Hartmanis has an elegant result showing that there is a function that can be computed faster on a RASP (random access stored program machine) than on a RAM (Math Systems Theory, 1971).

So "RAM complexity" was alive and well. What made things confusing was that fixed length register RAMs are uninteresting, but if one allows unbounded length registers, it is unclear whether unit cost is a realistic measure, and, if not, what would be reasonable. A natural option is to charge for the length of the register that is effectively used, the log of the value stored. Of course, there is the problem that determining the complexity of an algorithm becomes even harder. Even peskier questions appear if one asks whether addition and multiplication should have the same cost, and if not, should one use the schoolbook (quadratic) cost, or perhaps the Sconhage-Strassen cost? Most researchers opted to use the unit cost, and avoid all these complications.

To make things worse, many algorithms in optimization are expressed naturally in terms RAMs with real numbers registers. Note that fundamental questions about this latter model are still very much open.

To summarize, measuring number of RAM steps as a complexity measure was not a novel idea. What made the Cook paper relevant was exactly the proliferation of RAM measure results. In particular the Stockmeyer-Pratt-Rabin vector machine paper (and the later Hartmanis-Simon multiplication RAMs) as well as RAMs holding reals used in the OR community made it important to be precise about the exact meaning of "number of RAM instructions" measure. The community was quite aware that logarithmic cost was polynomially equivalent to Turing machines, and these papers showed that unit cost likely wasn't. Cook and Reckhow wrote down precisely what was likely a kind of unwritten consensus among the researchers in the area. This was necessary and useful, but it did not "set the stage to make RAMs the gold standard". The stage was already set, people were using RAMs to analyze algorithms, and Cook and Reckhow was a precise and meticulous description of what this meant.

In short, if one wants a picture of what great things got started in the period, the paper is an excellent choice, but, as usual, the actual history is complicated, dynamic, and, I hope, interesting.

Acceptance Rates versus Competitiveness

The acceptance rates at conferences for theoretical computer scientists tend to run higher than acceptance rates at conferences in other areas of computer science. Does this mean that theory conferences are less competitive than their counterparts in other areas? In a word, no.

Researchers look at their papers and for a given conference, either feel they have a very good chance of acceptance, a possibility of acceptance or a long shot of acceptance and tend to submit only if their paper falls in one of the first two categories.

In non-theory areas like artificial intelligence, the committee must take a subjective look at the papers which means many more papers fall into the second "possibility of acceptance" category. Many more people therefore take the risk and submit their paper because they can't immediately put the paper in that third "long-shot" category. This leads to more submissions and a low acceptance rate.

For theory we do a much better job putting our papers into these categories, as we can self-judge the hardness of the results and have a good feeling of the importance of the results for the conference. Theorists can tell when their papers won't have much of a chance of acceptance and will, usually, not waste their and the program committee's time in submitting these papers to the conference. This leads to a relatively higher acceptance rate in theory conferences.

A similar analysis would also explain why the funding rates for the theory NSF program also tends higher than the funding rates at many other programs in CISE.

The Enemy of the Good

Alice (not the real name) has a STOC submission with Bob and wanted to put the paper on a public archive. Bob insists that the paper not go public until the "exposition is perfect", which if taken literally means never. I told Alice about a phrase my wife liked to use

Don't let perfection be the enemy of the good.

I hesitate to write this post because we far too often have the opposite problem, authors who take their hastily written deadline-driven conference submissions and just put them out on the web in its messy state. But aiming for that impossible perfection in the exposition spends considerable time making tiny changes to an abstract that, in most cases, no one would have noticed. One can better spend their time in other ways, like doing research for the next paper.

So take a little time to clean up the conference submission but then don't worry about every little detail. As soon as possible make it available for all to see. If there are problems in the exposition, people will let you know (especially if you fail to cite their research) and you can fix the paper accordingly. Psychologically you will feel better getting that conference submission you had spent that hard concentrated effort on out of your mind, until it (hopefully) gets accepted and you have to work on the proceedings version.

Favorite Theorems: Defining the Future

October Edition

We end the list of favorite theorems from 1965-74 with two seminal papers by Cook and Reckhow.

Stephen Cook and Robert Reckhow, Time-bounded random access machines, STOC 1972, JCSS 1973.

Stephen Cook and Robert Reckhow, On the lengths of proofs in the propositional calculus, STOC 1974, JSL 1979.

The first paper developed the random-access machine (RAM) for measuring the time complexity of algorithms. "Random" here has nothing to do with probability, it just means we can access the memory in an arbitrary order.

Up to that time the multitape Turing machine was considered the model of choice for complexity but one had to access memory in a sequential fashion. The RAM model allowed quick access to all memory and much more accurately captured how real-world computers operated that previous models. Most algorithms papers give their time bounds in the RAM model and RAM is the gold-standard for proving lower bounds.

The second paper had a more delayed effect on complexity. Cook and Reckhow formalize a proof system for Tautologies as a polynomial-time computable function f whose range is exactly the set of tautologies. If f(p)=φ, p is said to be a proof for φ. They show that NP=co-NP iff there is some proof system such that every tautology φ has a proof polynomial in the length of φ.

This suggests an approach to separating NP from co-NP (which would imply P≠NP): Show that tautologies cannot have such proof systems. In 1985, Haken showed that the pigeonhole principle, encoded as a tautology, did not have polynomial-size resolution proofs. This led to a very active research area on proof complexity that finds lower bounds for various classes of tautologies on different proof systems, though we still remain quite far from NP≠co-NP.

Paul Beame and Toni Pitassi have a nice though slightly dated 1998 survey on propositional proof complexity.

Negotiating Your Job

An excellent Chronicle article on negotiating your job offer. I fully agree with the article that you lose out considerably by not negotiating and that you focus more than anything else on salary. An extra $5000 now will grow through the years as salary increases are usually a percentage of the current salary. Universities try to hold down the salary for similar reasons.

Once a department makes an offer, even if it was a tough decision, they then try as hard as they can to get the candidate to accept. Losing a candidate looks bad in their university and in the CS community. Take advantage of this and negotiate hard. Remember that once you agree to a contract your negotiating power goes to zero and remains zero for years to come.

For computer science, the Faculty Salary section of the Taulbee Survey can give you some idea what kind of income to aim for.

After salary, try to negotiate larger startup (or individually money for summer salary, students, travel), course reductions and any special needs you might have. As a rule, anything is negotiable.

If you have two offers, even if one offer dominates the other you should keep both offers open to be in a better negotiating position. This isn't good for the community as it keeps two positions tied up, but you need to think about yourself. Try to wrap up the negotiations as quickly as possible though so you don't keep jobs away from other people.

And, of course, if you get an offer from Chicago, ignore all of the above and just accept our initial offer immediately.

Games for Girls

This notice came into my inbox last week.

ChicTech, an outreach program of the University of Illinois Department of Computer Science, extends an open invitation for college women to participate in the second annual Games for Girls Programming Competition (G4G).

G4G was conceived in response to research indicating that boys enjoy a relatively greater degree of confidence with computers because they spend more time as children playing computer games. The research suggests that this difference in confidence contributes to the gender imbalance seen in the field of Computer Science.

So the gender imbalance in CS is due to the fact that girls don't play enough computer games. Guess that makes me a bad father for limiting the amount of time my daughters spend on the computer.

I do see at least one of my daughters more confident talking anonymously in a virtual world than in her real classroom. So suppose we had some virtual classrooms where students were represented by avatars (cartoon characters) and nobody knew the mapping from real students to avatar. Then the women (and the men) might be more willing to participate if they felt they had no risk from speaking up. But is this the environment we really want to teach in?

Bringing Complexity to Your iPod

Welcome to ComplexityCast, the first of a very occasional podcast, an audio version of this weblog. First up, Bill Gasarch and I talk about the P versus NP problem. Download the MP3 (3.4MB, 20 minutes) or subscribe to the Podcast Feed.

Whither to Compete

A guest post by Rakesh Vohra.

Fortnow's post on competitive ratio's has prompted a number to speculate on the `right' number of people who should engage in competitive analysis. I took Fortnow's post as an invitation to revisit the arguments in favor of doing this kind of analysis. As I see it there are four arguments:

1. The argument from beauty: Truth is beauty and beauty is truth. The first direction I buy, the second, except in the case of Grecian urns, requires a proof. In any case, I am prepared to accept the aesthetics (or wit, cunning) of competitive analysis as sufficient justification for engaging in competitive analysis. Perhaps competitive analysis is to CS what number theory is to Maths. There are, however, shared aesthetic standards (otherwise the criterion has no bite), so only some kinds of work can be justified in this way. My guess is that the analysis of problems that can be stated with a minimal of fuss, have an immediate appeal and seem simple in the first telling (pretty much what makes for a good number theory problem) meet this criteria. So, TSP, SAT, clique, coloring, max-cut are in. However, the stochastic, dynamic traveling dog and pony problem with piecewise linear costs is out.
2. The argument of fine distinctions: Not all NP-complete problems are alike. Some really are easier than others. Therefore one would like a device to make distinctions between them. The bounds from competitive ratios appear to do a nice job in this regard. Knowing that a problem can be approximated to within a log factor but not within a constant factor does tell us about its difficulty relative to others. Notice that order of magnitude of the ratio suffices for this purpose and not the best possible ratio.
3. The argument from ignorance: If we do not know what the distribution of problem instances looks like what choice do we have? The assumption of complete ignorance is an extreme one and can be justified in some but not all cases. If one adopts this justification for engaging in a competitive analysis one must first argue that the assumption of complete ignorance is reasonable to make. One can imagine natural situations where partial information is available. In these cases it seems reasonable to expect error bounds that incorporate such information. Bounds that are data dependent are not as pretty as ones that are independent of the data, but may be more useful.
4. The beneficial spin-off argument: This is the argument that Vazirani makes. Putting a man on the moon is a Quixotic task but we received non-stick frying pans as a by product. However, we might have had non-stick frying pans by focusing on non-stick frying pans and saved ourselves the trouble of putting a man on the moon. The point is that this argument does not rule out other ways of achieving the same benefits.

The arguments do not provide a universal defense of a competitive analysis but justifications to be used on a case by case basis. I think the question to be asked is this: if an exercise in competitive analysis cannot be defended on aesthetic grounds, reveals/verifies no new and novel distinction, inhabits an environment in which complete ignorance is an unreasonable assumption and has no identifiable beneficial spin-off, why is it being done?

Competitive analysis is now an export business. One of the areas it is being exported to is game theory. This raises a new problem not present in the clean optimization framework. That is, does the notion even make sense when what one is comparing are preferences rather than objective function values?

Losing the Office Phone

About a month ago I had the phone in my office removed. The number was one digit off from both maternity and a nurse's station at the U of C hospitals and if you Googled "Chicago Ballroom Dancing" my office phone number came up. About 90% of the phone calls were wrong numbers and I had gotten to the point of not answering the phone unless I recognized the Caller ID.

I could have had the number changed but I spend enough time outside the office (at TTI, other universities, working at home) that calling me at the office was not a reliable way to reach me. So I just eliminated the office phone and put my mobile number on my home page and in the university directory.

I don't rack up lots of minutes; we are primarily an email-based community and I get on average about one work related phone call a week. I made the change not because I want to use the phone less, rather to make myself more accessible. Our community relies on email too much, there are sometimes the old telephone still comes in handy.

• Calendar coordination.
• Convincing someone to do something. It's much harder to say "no" on the phone than on email.
• Sensitive information. Email leaves an electronic trail and one little typo in the email address can send your scathing comments who knows where.
• Some people like to use the phone for research. I prefer email because it forces you to think about what to write and you get a record of the discussion. But if there is a technical point you disagree on, a phone call can often quickly resolve the issue.
• Handling a disagreement, particularly when one or both sides are emotional over the issue. This situation is even better handled in person, if possible.
• Catching up. At the end of a phone call we often talk about other things going on in our lives. Happens far less in email.

More and more of our community are beginning to use instant messaging for many of these purposes. Also with VOIP services like Skype becoming more popular, the rest of you might lose your office phones sooner than you expect.

Competitive Analysis

When you cannot achieve the optimum solution of a problem, how do you measure the performance of an algorithm? If you knew the distribution of instances, you can see how well the algorithm performs on average. But most theoretical computer scientists prefer a worst-case analysis that tries to minimize the ratio of the optimal solution to the algorithmic solution. But many algorithms achieve seemingly large ratios that don't seem practical.

Vijay Vazirani defends this competitive analysis of algorithms in the preface of his 2001 book Approximation Algorithms.

With practitioners looking for high performance algorithms having error within 2% or 5% of the optimal, what good are algorithms that come within a factor of 2, or even worse, O(log n) of the optimal? Further, by this token, what is the usefulness of improving the approximation guarantee from, say, factor 2 to 3/2?

Let us address both issues and point out some fallacies in these assertions. The approximation guarantee only reflects the performance of the algorithm on the most pathological instances. Perhaps it is more appropriate to view the approximation guarantee as a measure that forces us to explore deeper into the combinatorial structure of the problem and discover more powerful tools for exploiting this structure. It has been observed that the difficulty of constructing tight examples increases considerably as one obtains algorithms with better guarantees. Indeed, for some recent algorithms, obtaining a tight example has been a paper in itself. Experiments have confirmed that these and other sophisticated algorithms do have error bounds of the desired magnitude, 2% to 5%, on typical instances, even though their worst case error bounds are much higher. Additionally, the theoretically proven algorithm should be viewed as a core algorithmic idea that needs to be fine tuned to the types of instances arising in specific applications.

But still why should a practitioner prefer such an algorithm to a heuristic that does as well on "typical" instances but doesn't have a worst case bound? Our usual argument says that we don't really know what "typical" means and we can promise you something no matter what happens.

Besides approximation algorithms, theoreticians have taken competitive analysis into other arenas, like comparing on-line versus off-line job requests and auctions that make a constant factor of the optimal revenue where achieving a competitive factor of 2 can mean a serious loss of income.

Sometimes these algorithms will allow themselves to do poorly when the optimum is bad in order to achieve the best ratio. If we truly want to sell these algorithms to the practitioners, should we focus on doing well on the situations they care about and then, only secondarily, worry about the performance in the worst case?