Elsevier and TCS

My post A Referee's Boycott generated quite a discussion in the comments, particularly about Elsevier. Paul Beame asked about why the EATCS still sponsors the Theoretical Computer Science through Elsevier. Don Sannella, editor-in-chief of TCS-B (Logic, Semantics and Theory of Programming), responded to Beame and earlier comments. Paul sent me a response to Sannella's comments. I'm reposting Sannella's comment followed by Beame's response.

---

Don Sannella's Comment

Regarding the relationship between EATCS and TCS: EATCS is in the process of changing its statutes to say that it supports the spread of the results of research and exchange of information through scientific publications, without specific mention of TCS or any other journal. This decision has already been made and approved by the membership; the only thing holding up its implementation is the fact that EATCS is legally a Belgian organization so revision of the statutes involve lawyers etc. I think this is an appropriate change (speaking also as a member of the EATCS Council); the previous situation was simply a result of the way that EATCS and TCS grew up together and were set up by the same people, starting at a time when there were very few journals.

Regarding criticisms of TCS:

• Copyright: There is a lot of misinformation circulating about this issue. I have even caught one of the main advocates of open access publishing making plainly false statements in a public talk. I suggest that there would be more light and less heat if people would take the trouble to find out what the actual situation is before criticizing.
  I think the main practical issue is ability of authors to publish their work on their own websites. In this respect Elsevier's copyright agreement is not significantly different from the ACM's, or Springer's, unless there has been a recent change to these that I haven't noticed. There is an explanation of this aspect of the Elsevier copyright, by the Elsevier editor in charge of TCS, in the Bulletin of the EATCS number 75 (Oct 2001). The EPrints organization regards Elsevier as self-archiving-friendly ("green" status) and it reached that status before Springer did.
• Price: I know that TCS is expensive, probably the largest item in any Computer Science library's journal subscription budget. But it is also very large, with 12000 pages published per year. If you look at the price per page (here are 2004 figures from the AMS for mathematics journals which are by the way substantially different than the price comparison given by Wim van Dam) the cost is $0.42/page which is comparable with other journals. This doesn't take the thousands of pages in ENTCS, which comes free with TCS, into account. The whole issue of journal price is complicated because the primary mode of access these days is electronic, and prices for electronic access are negotiated on a case-by-case basis. If you discuss the issue with Elsevier, the statistic they will give you is that the per-download price of an article in TCS (computed by taking the total cost of subscriptions and dividing by the total number of downloads, I think) is considerably less than $1. According to Elsevier, this is the figure that librarians care about, and the fact that it is a fraction of the cost of interlibrary loan is the key point.
• Open access: The open access movement advocates journals that are free to readers. In this model, the author is the one who ends up paying; this fact is mentioned much less often and some people who advocate open access don't appear to be aware of it. (I know of one new open-access journal that is free to authors as well because the costs are covered by a university, at least for the moment. The point is that somebody needs to pay; running a journal is not a cost-free spare-time activity. See "Guide to Business Planning for Launching a New Open Access Journal" from the Open Society Institute.) There are major opportunities for unfairness in the editorial process with author-pays but otherwise the only problem I see is that with both models co-existing, few authors with an article that would be accepted by a "normal" journal will be willing to pay for publication in an open access journal. Springer has recently offered authors the choice of paying a fee in order to make a paper open access, or not paying and leaving it as paid access. I hope they publish statistics on how many authors decide to pay!
• Academic Press versus Elsevier: "Academic Press had its flaws but they were not predatory in their pricing." Well, compare AMS's 2004 figure for Information and Computation ($1.07/page, Elsevier-owned) with its 2001 figure ($1.92/page, Academic Press-owned).
• Quality of TCS: As editor-in-chief of TCS-B — which is admittedly probably not the main part of interest to readers of this blog — I am responsible for its quality. I think the quality is pretty good and improving. Opinions on this may vary of course. At least, it is not the case that the alleged decline in quality is because (as Paul Beame asserts) "TCS went to a highly distributed editorial board". The way that the TCS editorial board works has not changed since it was founded in 1975, as far as I know. I wonder where he gets his information. I am unhappy about the implied suggestion that the TCS editorial board members are not exercising proper editorial judgment.

Finally: I am not here to make excuses for Elsevier. My interest is TCS (and EATCS) and replying to some points above that are factually incorrect.

---

Paul Beame's Response

I am happy to hear about the EATCS change. Let me address the two main points, copyright and price, as well as open access journals.

Copyright I agree that copyright is no worse at Elsevier than at Springer (in fact Springer has gotten worse recently). Copyright transfer is apparently not required given the following text I received from Elsevier regarding a JCSS paper:

Recently, we sent you a Transfer of Copyright form relating to the above-mentioned. We note that you have not yet returned a completed form duly signed. In order to avoid any delay in publication, we ask that you do so immediately. Attached you will find a further copy of the form. Please return the completed and signed original of this form by mail or fax, or a scanned copy of the signed original by e-mail.

If we do not hear from you by return, the article will carry a line in place of the copyright line merely indicating that Elsevier published the article.

This sounds all right BUT when I have explicitly took advantage of the second option I noticed that when the article was published Elsevier still explicitly claimed copyright on it!

Price Thinking about things as price per page is exactly the problem. TCS was one of the top 2 or 3 theory journals and around 2000 pages annually until 1989 when it decided to go to bi-weekly publication and a much larger editorial board and upped its page count to 3500, raising its prices drastically overnight to keep the same price per page. The average quality declined markedly at this time as the good papers were swamped with more lower quality fare. TCS still publishes many good papers but it is nowhere near as high quality as it was in the 1980's when it got many of the top papers in the field.

Moreover TCS is just one Elsevier journal. Their behavior with others is part of the problem: In the early 90's I was deciding between publishing in Annals of Pure and Applied Logic (Elsevier) and Journal of Symbolic Logic (ASL). I was told that longer papers were more appropriate for APAL and so submitted there. I made the mistake of not checking prices: JSL was 12 issues a year, each over 300 pages, and cost $400 or so annually. APAL had 4 issues per year, each about 250 pages, and cost more than $2000. The quality of the two was similar.

I speak with librarians who have to purchase journals. The pricing for electronic journals that Elsevier sets are bundled in such a way that they feel forced to subscribe electronically to many journals that they do not want to purchase. The comparison with inter-library loan is absurd.

The price comparison should be with society-published journals such as the ACM and SIAM journals. These do provide the main office editorial staff that for-profit journals provide.

Open Access I agree that the long-term soundness of the open access model is not yet fully established. (There are some things that need to be paid for without voluntary investment beyond refereeing and it is not yet completely clear how to do this long-term.) However, if you want an example of an open access journal that does not seem to suffer from the flaws you describe, consider JAIR (the Journal of Artificial Intelligence Research) which has been operating for more than a decade and is one of the top couple of journals in AI.

(It may be too soon to tell about Theory of Computing is in its infancy but it already has a very high quality of papers.)

Why is it that Elsevier regularly emphasizes the comparisons with nascent open access journals but regularly ignores comparisons with high quality society-published journals such as SIAM and ACM journals?

The Internet Never Forgets

The ACM announced the 2005 Award Recipients. Looks like it is for real this time, here is the press release on Peter Naur's Turing Award.

What happened last week? I got an email pointing to the awards site and suggesting that I congratulate Omer Reingold in the weblog. I agreed and put up the post and mentioned a few other winners as well. It wasn't until several hours later that I discovered, via an anonymous comment on the post, that the awards site went up by mistake. By that time the damage had long been done so I decided to just leave the post.

Inadvertent announcements have always occurred but the Internet makes the news travel faster and further and impossible to undo.

Class Times

At the University of Chicago most courses on Monday-Wednesday-Friday run 50 minutes each and on Tuesday-Thursday run 80 minutes. Many other universities have similar timings. Most professors seem to prefer the longer classes especially for graduate courses: You only have to teach two days a week, you don't have to recap as much and you get an extra ten minutes a week.

I prefer the 50 minute lectures. Many theorems fit nicely into these smaller lectures. These lectures are easier to prepare. But most importantly I remember struggling to keep focused as a student in those longer lectures and I don't want to subject my students to the same.

There are variations on the theme. I took a graduate cryptography class with Silvio Micali that went for three hours once a week. We did have a muffin break in the middle and Silvio has the personality to pull it off.

During my sabbatical year in Amsterdam I taught a short course that had 90 minute lectures. The students insisted on having a break in the middle. Most Dutch movies theaters inserted an intermission in the middle of movies. Apparently the Dutch have an attention span no longer than half of a soccer game. My kind of people.

NSF Theory Solicitation Announced

The NSF posted the new Theoretical Foundations program solicitation, due date May 25.

The solicitation divides the program into three areas, "Scientific Foundations for Computing", "Scientific Foundations for Communication" and a new area "Scientific Foundations for Internet's Next Generation" (SING) part of the GENI Initiative. Computational Complexity falls into the first area though all of these areas ask important theoretical questions.

The NSF now allows you to submit via Grants.gov instead of Fastlane unless you have a (A) Collaborative Proposal or (B) Subawards. They should also add (C) Don't use Windows.

Deal or No Deal Redux

The NBC game show Deal or No Deal resumes with new episodes tonight. I described the game when it first ran in December where we discussed the game from the player's perspective. Now let's look at the game from the view of the Banker.

Suppose the Banker always offered the expected value of the remaining cases. Could a player somehow make smart choices to increase his or her expected winnings? No. Let X be the random variable representing the value of the briefcase held by the player. Let Y be the random variable describing the briefcases open so far. A well known equality states E(E(X|Y))=E(X), i.e., the expectation of the expected value of the briefcase given the current game situation is just the original expectation of the briefcase. Any strategy by the player will yield exactly the same expected winnings, about $131,477.54.

Usually the Banker gives an offer below the current expected value of the briefcase. Why? As I mentioned in the previous post, the players are risk adverse and may accept a smaller guaranteed amount now. But more importantly a lower amount will increase the chances that a player will not accept the deal and play longer. The Banker pays an expected $131K per player not per episode and thus pays out less per episode the longer each player plays.

Computational Complexity Accepts

The accepted papers for the 2006 Conference on Computational Complexity have been announced. Some very exciting looking papers. I'll highlight some of them in a future post.

See you all in Prague.

Globalization and Offshoring

The ACM released a report today Globalization and Offshoring of Software. The New York Times has coverage. Definitely read over the executive summary of the report that dispels the myth that offshoring is leading to lesser need of information technology workers in the US. The overview has advice for current and future IT professionals.

One might wonder whether IT is still a good career choice for students and workers in countries that offshore software and IT services work. Despite all the publicity in the United States about jobs being lost to India and China, the size of the IT employment market in the United States today is higher than it was at the height of the dot-com boom. Information technology appears as though it will be a growth area at least for the coming decade, and the US government projects that several IT occupations will be among the fastest growing occupations during this time. There are some things that students and workers in this field should do to prepare themselves for the globalized workplace. They should get a good education that will serve as a firm grounding for understanding the rapidly changing field of IT. They should expect to participate in life-long learning. They should hone their "soft skills" involving communication, management, and teamwork. They should become familiar with an application domain, especially in a growth field such as health care, and not just learn core technical computing skills. They should learn about the technologies and management issues that underlie the globalization of software, such as standard technology platforms, methods for re-using software, and tools and methods for distributed work.

Update 3/1: The New York Times now has an editorial based on the report.

Oh Canada

This week I'm in Vancouver visiting Simon Fraser University which has a nice complexity group: Valentine Kabanets, Arvind Gupta, Gábor Tardos who just moved here from Hungary, Funda Ergun who visited the NEC Research Institute often when I was there and several postdocs including my former student Rahul Santhanam.

One of the big stories in Canada this week (besides the Olympics which will be held in Vancouver in 2010) are the legal problems of Research in Motion, the Canadian company famous for the Blackberry. Many of my lawyer/banker friends have these devices which they religiously check every time they get the comforting buzz of new email. There is a chance Blackberry users in the US may have their service cut off as early as Friday after a judicial hearing on a patent dispute.

Most academics have avoided the Blackberry craze but still the company plays an important role in computer science. Research in Motion executives have been heavy funders of the Perimeter Institute for Theoretical Physics and the Institute for Quantum Computing which have made Waterloo a major center of quantum computation. The IQC employs a large number of computer scientists in quantum computing such as fellow blogger Scott Aaronson.

So when you ride on the bus and hear your neighbor's Blackberry buzz, remember it's buzzing for science.

ACM Awards

The 2005 ACM Awards have been announced. Omer Reingold received the Grace Hopper Award given to the best "outstanding young computer professional of the year, selected on the basis of a single recent major technical or service contribution" in this case for his log-space algorithm for undirected connectivity. The previous theoretician to receive the award was Shafi Goldwasser in 1996 and before that Donald Knuth in 1971. Congratulations Omer!

Peter Naur won the Turing Award (the closest CS has to a Nobel Prize) for his work on Algol 60.

Gerald Holzmann, Robert Kurshan, Moshe Vardi and Pierre Wolper won the Paris Kanellakis Theory and Practice Award for their use of automata theory in program verification.

Thanks to Moni Naor for the pointer.

Accuracy of Predicted Probabilities

I stumbled upon the so called College Admissions Services which will give, for a fee, your percent chance of being admitted to undergraduate colleges in the US. I can't vouch for or against this service but I did catch an interesting claim of being 98% accurate. What does 98% accurate mean when you give probabilities? There are some reasonable answers to this question but not the one used by this site.

They do give the formula they use, roughly the fraction of people who didn't get refunds. Someone is eligible for a refund if the prediction was at least 51% and they didn't get in or the prediction was less than 50% and they were accepted.

What's wrong with this picture? Suppose everyone who was eligible for a refund got one. Consider people who they predict have a 60% chance of acceptance. This means 40% of them should not be accepted. But if they are all accepted they would have considered this a perfectly accurate prediction though it clearly is not. Conversely if 60% of them were accepted, this is what you expect but they would consider that only a 60% accuracy rate. And if they predict 50% the formula counts this as an accurate prediction even if all or none of them were accepted.

Either we have the very unlikely scenario that the rounding to zero or one of the prediction is a very good predictor or more likely that not many people claim the refunds they are entitled to. When you make a claim to accuracy that doesn't match the service you provide you end up giving no claim to accuracy at all.

Why Computer Science Theory Matters?

At the AAAS Annual Meeting on Friday, the CRA organized a session Computer Science Behind Your Science. Bernard Chazelle gave one of the talks Why Computer Science Theory Matters? based on an essay he wrote for the undergraduate magazine Math Horizons. In a pre-talk interview Chazelle argues that algorithms can help us explain scientific ideas in a fundamentally different way than simple mathematical formula.

Computer science is a new way of thinking, a new way of looking at things. For example, mathematics can't come near to describing the complexity of human endeavors in the way that computer science can. To make a literary analogy, mathematics produces the equivalent of one-liners – equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing — computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.

When one asks scientists in other disciplines what role computer science has for them, one usually sees CS as a way to solve their large computational problems, like large matrix computations. The more enlightened realize the importance of algorithmic issues and even have a rough understanding of NP-completeness and what that means for the problems they would like to solve. But we haven't on a large scale made scientists in other fields realize that computation exists within the systems they study. Protein folding, economic markets, the ways astronomical bodies interact are all computational processes and once we can make this case, the ideas and tools of computational complexity and theoretical computer science can help them understand the strengths and limitations of these processes.

Suresh and Jeff have more on Bernard's talk and Scott has an interesting and not-unrelated post.

Great NSF Theory News

Sanjeev Arora has some good NSF news in the first post on a new moderated mailing list tcs-funding.

There will be a call for proposals in the NSF theory program this spring and grant sizes are expected to be larger than before. So please apply and send good proposals.

A SIGACT funding committee report outlines things you can do to help improve funding for TCS (please read and act upon). It also describes initiatives launched by the committee to help bring more funding to TCS.

Looks like I jumped to conclusions last month. Never happier to have been wrong.

A Referee's Boycott

As an editor of Information and Computation I made a request to a scientist to referee a paper. I got the following response.

I while ago I decided that I would no longer provide my unpaid referee services to certain publishers like Information & Computation's Elsevier, so I can't help you with this.

Be careful what you wish for. JCSS floated a proposal to pay editors and referees but rescinded it after backlash from the editorial board and the community.

The authors have submitted their paper to I&C, a respected journal, and deserve to have their paper properly reviewed. We all have a responsibility to do our fair share of refereeing and it takes no more effort to referee a paper for I&C than for any other journal.

If you truly dislike a certain publisher then don't submit your papers to their journals. But to take a symbolic stand by not refereeing papers only hurts the authors and our community.

Favorite Theorems: Alternation

Introduction

Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question three decades ago: Space is just alternating time.

Chandra, Kozen and Stockmeyer, Alternation, JACM 1981. Based on two 1976 FOCS papers.

An alternating Turing machine is a nondeterministic machine with states marked either existential or universal. Consider a game where player 1 chooses the next legal configuration from existential states and player 2 chooses the next legal configuration from the universal states and player 1 wins if the machine halts in an accept state. The machine accepts those inputs where player 1 has a winning strategy.

Chandra, Kozen and Stockmeyer show

• ATIME(t(n)) ⊆ DSPACE(t(n)) ⊆ NSPACE(t(n)) ⊆ ATIME(t²(n))
• ASPACE(s(n)) = ∪_cDTIME(c^s(n))

Alternation causes a shift in the time-space hierarchy of classes: P = AL, PSPACE = AP, EXP = APSPACE, EXPSPACE = AEXP, etc. More importantly the two fundamental resource bounds of time and space are really just the same concept on different models.

Alternation allows us to show the PSPACE-completeness of many game-based problems. Also alternating machines set the stage for interactive proof systems which led to probabilistically checkable proofs, perhaps the most productive line of research in complexity over the past fifteen years.

The paper also characterizes the polynomial-time hierarchy using bounded alternation and shows that alternating finite automata still accept just regular languages (with a double-exponential blow-up in the number of states).

Weapons of Math Instruction

Making the rounds.

At New York's Kennedy airport today, an individual later discovered to be a public school teacher was arrested trying to board a flight while in possession of a ruler, a protractor, a compass, a slide rule, and a calculator. At a morning press conference, the attorney general said he believes the man is a member of the notorious Al-gebra movement. He is being charged by the FBI with carrying weapons of math instruction.

"Al-gebra is a fearsome cult," a Justice Department spokesman said. "They desire average solutions by means and extremes, and sometimes go off on tangents in a search of absolute value. They use secret code names like 'x' and 'y' and refer to themselves as 'unknowns', but we have determined they belong to a common denominator of the axis of evil with coordinates in every country. As the Greek philanderer Isosceles used to say, 'there are 3 sides to every triangle'."

When asked to comment on the arrest, President Bush said, "If God had wanted us to have better weapons of math instruction, He would have given us more fingers and toes".

Advanced Placement

The CRA notes that while the number of students who take Advanced Placement exams has surged over the last few years, the number taking the Computer Science AP exams has dropped a bit, perhaps foreshadowing an even more dropping interest in undergraduate CS.

In many American high schools one can take AP courses that lead to standardized exams in a variety of topics that many universities will use to allow students to place out of some introductory courses. At least that was the purpose when I went to high school, but since then the AP exam has become a mainstay of the high school curriculum. Nearly a quarter of all high school students take at least one of 35 different AP exams. Student applying to good universities had better have several AP courses and exams on their record. Bush made AP exams a goal in his state of the union and Newsweek uses the AP test to rank high schools.

I have nothing against the AP exam in its original form, I took exams in math, physics and chemistry in high school and they saved me from some courses in college. But these exams have their drawbacks, as one has to teach to the exam. Gone in these course is the ability of teachers to experiment and students to excel in different ways.

We have this particular problem with the AP Computer Science A and AB exams. These exams force teaching in a specific language, currently Java, where teachers might have found other languages betters suited for presenting a variety of computer science concepts. The CS A exam focuses mostly on programming in Java, the CS AB exams does add some data structures and running-time analysis.

In high school (before the AP CS exam existed) I had a wonderful course that combined computer programming and probability. We don't see these kinds of interesting classes where the advanced classes in US high schools have to focus on exams.

Advising

David Molnar asks about how to evaluate an advisor. There is no objective method to evaluate advisors, faculty have different students to start with so one cannot directly compare the quality of their Ph.D.s. It's easy to advise a very intelligent hard-working student; it's advising the others that really separates the great advisors from the good ones.

To best evaluate an advisor, ask their students—both the successful ones and the ones that struggle. Keep in mind that an advisor's style that works with one kind of student might not work with another so listen to why a particular advisor is good or bad. These are especially good questions for undergrads to ask current Ph.D. students when the visit potential graduate schools.

Molnar also notes that he hasn't found many resources on how to be a good advisor. We all have different approaches and one could write a book on the topic but here are general techniques (many of which I learned from my own advisor Michael Sipser).

Have students work on problems that interest them not just you. I like to hand them a proceedings of a recent conference and have them skim abstracts to find papers they enjoy. However if they stray too far from your research interests, you will have a hard time pushing them in the right directions. And don't work on their problems unless they want you to.

Keep your students motivated. Meet with them on a regular basis. Encourage students to discuss their problems and other research questions with other students and faculty. Do your best to keep their spirits high if they have trouble proving theorems or are not getting their papers into conferences. Once they lose interest in theory they won't succeed.

Feel free to have them read papers, do some refereeing and reviewing, give talks on recent great papers. These are good skills for them to learn. But don't abuse them too much.

Make sure they learn that selling their research is as important as proving the theorems. Have them write the papers and make them rewrite until the paper properly motivates the work. Make them give practice talks before conferences and do not hold back on the criticism.

Some students will want to talk about some personal issues they have. Listen as a friend and give some suggestions without being condescending. But if they have a serious emotional crisis, you are not trained for that; point them to your university counseling services.

Once it becomes clear a student won't succeed working with you, or won't succeed as a theorist or won't succeed in graduate work, cut them loose. The hardest thing to do as an advisor is to tell a student, particular one that tries hard, that they should go do something else. It's much easier to just keep them on until they get frustrated and quit, but you do no one any favors that way.

Surprising Gasarch

In the fourth Complexitycast, Bill Gasarch returns and discusses his Surprising Results post and his recent guest blogger experience.   MP3 (25:42, 4.4MB)

Sauer's Lemma

The recent post Discovering the Discovered reminded me of one of my favorite combinatorial lemmas known as Sauer's Lemma.

Sauer's Lemma roughly states that if a collection of sets has VC dimension bounded by d then any set of n elements can only be split n^d ways. More precisely

Fix a collections Φ of subsets of U such that for all x₁,…,x_k in U, |{S∩{x₁,…,x_k} | S∈Φ}| < 2^k then for all x₁,…,x_n in U, |{S∩{x₁,…,x_n} | S∈Φ}| ≤ O(n^k-1)

This lemma has many important applications, most notably a famous result of Blumer, Ehrenfeucht, Haussler and Warmuth showing that if you don't care about computation costs then one can PAC learn a concept class iff the VC dimension of that class is bounded.

Why is Sauer's lemma connected to Discovering the Discovered? According to Till Tantau,

Vapnik and Chervonenkis appear to have been the first to discover it. They published it in 1968 in Russian and 1971 in English. Sauer, whose paper was published in 1972, claims that Erdös was the first to have conjectured the lemma. Subsequently, Sauer's Lemma has been rediscovered by Clarke, Owings, and Spriggs, and later again by Beigel.

Computational Complexity: A Modern Approach

Sanjeev Arora has posted a draft of his new textbook. A welcome addition to those who wish to learn or teach complexity.

Discovering the Discovered

Gina Kolata has a New York Times article Pity the Scientist Who Discovers the Discovered. The article had its genesis from a SODA invited talk by Rakesh Vohra. I like the closing quote from Larry Shepp, "Yes, but when I discovered it, it stayed discovered." Reminds me of the Christopher Columbus principle.

We have often seen theorems proven multiple times in our field, because the result was proven on both sides of the iron curtain (e.g. Cook and Levin), sometimes it is just easier to prove a lemma then work through the literature, or we just simply didn't realize someone else had thought about the same problem. We have a considerable number of published work in our field and you cannot hope to know every "known" result, even in an area where you are considered an expert.

There is no ethical breech if you reprove someone else's theorem as long as you make good once you learn the result already existed. Although I have occasionally reproven theorems I had seen previously in talks or papers I've reviewed and that's just downright embarrassing.

Announcements

How do we announce important activities in theoretical computer science? With research results we have pretty good systems through various paper archives. But how about conferences (deadlines, accepted papers, registration), grants, jobs, deaths and other information important to the community. With the Internet we expect easy ways to distribute such information and we have several such schemes but none really do a great job.

• Email Lists such as Theorynet and DMAnet will deliver all sorts of news directly to your inbox. Though moderated both lists have pretty high volume so many people don't subscribe.
• Search Engines. Want to know the upcoming deadline for ICALP? Just Google on "ICALP 2006". This only works for conferences you already know and won't help with other information.
• Websites like the Theory Calendar and CRA Job Announcements. These sites are not always up-to-date or complete and only cover a small segment of announcement topics.
• Newsletters like SIGACT News have a time lag and not everyone is a SIGACT member (though shame on your who aren't).
• Graduate Students. Some professors use their students to filter the Internet for them. But students are imperfect filters and not everyone has them available.
• Weblogs. Some people use this and other weblogs to keep up with what is happening in the community. While I try to make sure important news gets heard I certainly am not comprehensive and you might not share my biases.

What we need is a VGS (Virtual Grad Student), an intelligent program that scours the Internet and reports back to me exactly the information that I would find relevant. Until such agents exist, you'll have to choose your poison from the above or just remain blissfully ignorant.

Science in the Union

From Bush's State of the Union address last night.

And to keep America competitive, one commitment is necessary above all: We must continue to lead the world in human talent and creativity. Our greatest advantage in the world has always been our educated, hard-working, ambitious people—and we are going to keep that edge.

Tonight I announce the American Competitiveness Initiative, to encourage innovation throughout our economy, and to give our nation's children a firm grounding in math and science.

First: I propose to double the federal commitment to the most critical basic research programs in the physical sciences over the next 10 years. This funding will support the work of America's most creative minds as they explore promising areas such as nanotechnology, supercomputing, and alternative energy sources.

Second: I propose to make permanent the research and development tax credit, to encourage bolder private-sector investment in technology. With more research in both the public and private sectors, we will improve our quality of life—and ensure that America will lead the world in opportunity and innovation for decades to come.

Third: We need to encourage children to take more math and science, and make sure those courses are rigorous enough to compete with other nations. We have made a good start in the early grades with the No Child Left Behind Act, which is raising standards and lifting test scores across our country.

Tonight I propose to train 70,000 high school teachers, to lead advanced-placement courses in math and science, bring 30,000 math and science professionals to teach in classrooms, and give early help to students who struggle with math, so they have a better chance at good, high-wage jobs.

If we ensure that America's children succeed in life, they will ensure that America succeeds in the world.

Preparing our nation to compete in the world is a goal that all of us can share. I urge you to support the American Competitiveness Initiative and together we will show the world what the American people can achieve.

As part of the initiative the budget of several agencies including the National Science Foundation will double over ten years and be raised over 9% in the upcoming year.

There is a long road from SOTU to reality, but this looks like good news for science in America. More from the CRA and USACM.

Update 2/2: The NSF will have a 7.8% increase in the White House proposed budget for next year.

STOC Papers

The accepted papers of STOC have been posted. A few on the list I have mentioned before including Daskalakis, Goldberg and Papadimitriou on Computing the Nash Equilibrium (see also this extension that appeared after the STOC deadline), the Kelner-Spielman and Guruswami-Rudra papers and of course Irit Dinur's new proof of the PCP theorem, surely a lock for best paper.

There are several other interesting looking papers, including Zuckerman's Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Ambainis, Spalek and de Wolf on Quantum Direct Product Theorems and Charikar, Makarychev and Makarychev with Near-Optimal Algorithms for Unique Games. I can't find the latter online but here is the result from a talk abstract.

We present new approximation algorithms for unique games that satisfy roughly k^-ε/2 and 1 - O((ε log k)^1/2) fraction of all constraints if 1 - ε fraction of all constraints is satisfiable. These results show limitations on the hardness bounds achievable using UGC. In particular, they disprove a stronger version of UGC that was conjectured in a recent paper. Somewhat surprisingly, even a slight improvement of our results (beyond low order terms) will disprove the unique games conjecture.

Many more interesting papers, be sure to look the list over yourself.

More from Suresh and PC member Scott.

Quality versus Quantity

A graduate student asks

Is it better to have a large number of good papers or a small number of great papers?

The answer is both, great papers to show you have depth and many good papers to show that the great papers were not flukes.

But suppose Fate gives you two roads and you had to choose. History will only remember your best work, so you'll want great papers or the world will eventually forget you. But a CV with many solid good papers will sell better and should help you land better jobs and grants. You'll be perceived as an expert in the field based more on breadth more than depth.

Underlying the question is whether a graduate student should take aim at very hard questions hoping for an award-winning paper. Unless you have some specific new approach that might work or you can still get reasonable results even if the big problem does not fall, you should try to focus more on tractable problems that will build up your research reputation.

Too Many Conferences, Too Little Time

First thanks to Bill Gasarch for his interesting takes on academic life. Another person who should have his own blog.

I missed SODA again this year, but Suresh and Jeff had it covered. Actually I've never been to SODA and have never missed Complexity, which says much more about me than about the conferences.

I also missed the QIP (Quantum CS) conference a week before (I have been to a couple of QIPs in years gone by). Would have been worth it just to see Scott Aaronson's dinner speech but I had to settle for hearing it instead.

And a shout out to everyone at the Kolmogorov Dagstuhl just underway. Let's hope the roof stays on this time.

Speaking of conferences, the STOC accepted papers list should come out this week. Keep tuned.

LUDDITES Revisited

 

 
GUEST BLOGGER: Bill Gasarch
 
This is my last day guest blogging, so I'll end where I began,
THREE points on LUDDITES
 
I) Janos Simon corrected my history of Luddites, for which I thank him.
If you are interested, go to HIS comment on MY post from Monday Jan 23
for a link to a very nice article.
 
II) My father and father-in-law offer an interesting contrast:
 
FATHER-IN-LAW (Engineering Major, career mostly in Business, now retired):
LUDDITE: Does not program his VCR. Not sure if he doesn't know how to or just
doesn't want to.  So he HAS to be home on Sunday to watch Desperate Housewives
(a show I found distasteful- My father in law is hipper than I am).
 
NON-LUDDITE: Took a course on C at a local community college when
he was 70.  Pays all his bills on line.
 
FATHER (English Major, High School English Teacher and Vice Principal, now retired)
LUDDITE: Got a computer recently and still can't get email or pay his bills on line.
 
NON-LUDDITE: Uses his VCR to tape ALOT of shows.  He needs it since he watches ALOT:
West Wing, My Name is Earl, The Sopranos, Sex in the City when it was on (a show I find
distasteful- My dad is hipper than I am), 6 feet under, Deadwood, all four Law and Orders,
and all three CSI's, Without a trace, other stuff I can't recall. This from the man
who restricted me, wisely, to no more than an hour of TV a night when I was a kid.)
 
III) Stuart Kurtz emailed me some more questions for my Luddite quiz.  I asked him if I
could post them and he suggested asking for other inputs.  No one replied, so here are his:
 
STUART BEGIN:
9) Do you write emails (or blog posts) in
    a) variable width fonts with formatting,
    b) variable width fonts without formatting,
    c) fixed width fonts,
    d) What's a blog?,
    e) What's email?, or
    f) What's writing?
 
10) Do you indicate emphasis by
    a) using italic or slanted font,
    b) using a bold faced font,
    c) metadiscourse, i.e., "I want to emphasize that... ",
    d) ALL CAPS, or
    e) Shouting and waving your arms.
 
11) Does your mouse have
    a) four buttons,
    b) three buttons,
    c) two buttons,
    d) one button,
    e) control characters are good enough for RMS, and they're good  enough for me, or
    f) four feet and a tail.
 
12) What's your favorite programming language?
    a) Ruby or Python,
    b) Java
    c) Lisp,
    d) C++,
    e) Awk,
    f) IBM-360 assembly language,
    g) C,
    h) Lisp, or
    i) graduate student.
 
[I know Lisp occurs twice, but c and h are still different answers. Note that there's no
point asking for Perl -- as Perl programmers can only write, not read.]
STUART END.
 
                                                bill g.
 
P.S. I am supposed to say ``Now that I've guest blogged for a week I'm even more
impressed with Lance getting a topic out every day'' But this is NOT TRUE.
I was SO IMPRESSED with Lance in the first place that I can't be ``more impressed''
 
 

 

How Much are we effected by non-scientific criteria?

GUEST BLOGGER BILL GASARCH

TOPIC: How much is what we do influenced by non-scientific criteria?

(BEFORE I START TODAYS BLOG- A REQUEST.  EMAIL ME OTHER
LUDDITE QUESTIONS- I WILL POST THE BEST ONES ON FRIDAY)

I) AN INCOMPLETE SUMMARY OF
Thomas Kuhn's book The Structure of Scientific Revolution:

For long periods of time a field of science will agree on the basic terms
and problems of the field and will all work with that worldview (also called a paradigm).
This is called Normal Science. This is GOOD since if people were working with different
paradigms progress would be hard.  BUT there comes a time when some problems just cannot
be solved using the usual techniques. There will be an effort to jam this problem and
some approaches to it into the current paradigm, but eventually, the old paradigm will
fall and a new one will take its place. The new one will help to answer some old questions,
and pose new ones that could not have even been asked in the old one.

Newtonian Phy vs Einstein is the usual example, though there are others
on a much less cosmic scale. 

II) People after him have misconstrued his work to saying that science has NO
objective truth, that it ALL depends on the Paradigm.  This is, of course, hogwash.
More so when they claim that its a tool by the elite to dominate the masses, or some
such (look up SOKAL HOAX on google for one view of this view).

III) But a fair question CAN be raised along these lines:

How MUCH of what scientists do depends on political or personality or
other factors VERSUS how much is driven by objective scientific principles?

A few examples

a) What if in response to Russell's paradox the math world essentially
axiomized what set theorist now call V=L (every object is constructable).
Then we would know LOTs more about L, we would KNOW that the Axiom of Choice
is true, and we would know that Cont Hyp is true.  We might know that there
were these weird other models that are unnatural where CH is false, but we
wouldn't care.  (Some Set Theorists tell me this could never happen- that
people would be interested in other models. They are wrong.)

b) What if in response to the Banach Tarski paradox mathematicians rejected
some version of the axiom of choice? This would have  
been quite possible before AC began being used in so many places.

c) The people who believe in constructive methods only (e.g, Brouwer) are
portrayed as cranky old men holding onto an old paradigm that no longer worked.
But if they had won then people like Hilbert would be viewed as crazy rebels who
fortunately were never taken seriously. (This one I am less sure of- nonconstructive
techniques are SO powerful that I think they may be inevitable.)
d) If Computing Devices were invented either earlier or later then they were
would have a drastic effect on Theory.  While we think that P vs NP
is a natural problem, it only came out once the technology was in place.
Was it inevitable that it arise? Probably
Was it inevitable that it be considered important? Hard to say.

e) There is ALOT of work in Quantum Computing because
(i) Peter Shor proved FACTORING in Quantum P hence giving the problem new interest, or
(ii) There is (or actually was) lots of Grant money in it.
(of course these two are linked)

f) Do schools like MIT have too big an influence on what gets studied?
(They have less influence now than the used to.)

        MORE GENERALLY, if I had the time and the energy I would do
research on history/phil of math asking the question

HOW MUCH DO EXTERNAL FORCES EFFECT WHAT IS STUDIED ?

and I would do it WITHOUT an ax to grind.

A Theorem that should be better known

GUEST BLOGGER: Bill Gasarch

(BEFORE I START TODAYS BLOG- A REQUEST.  EMAIL ME OTHER
LUDDITE QUESTIONS- I WILL POST THE BEST ONES ON FRIDAY)

If u,v \in \Sigma^* then u is a SUBSEQUENCE OF v if you
can obtain u by taking v and removing any letters you like.

EXAMPLE: if v= 10010  then
e,0,1,00,01,10,11,000,001,110,0010,1000,1001,1010,10010
are all of its subsequences

Let L be any language-- a subset of \Sigma^* SUBSEQ(L)
is the set of subsequences of all of the strings in L.

The following three could be easy problems in a
course in automata theory:

a) Show that if L is regular then SUBSEQ(L) is regular

b) Show that if L is context free then SUBSEQ(L) is context free

c) Show that if L is c.e. then SUBSEQ(L) is c.e.
(NOTE- c.e. is computably enumerable- what used to be called
r.e.- recursively enumerable)

Note that the following is not on the list:

Show that if L is DECIDABLE then SUBSEQ(L) is Decidable.

Is this even true?  Its certainly not obvious.
THINK about this for a little bit before going on.



There is a theorem due to Higman (1952), (actually a corollary of
what he did) which we will call SUBSEQ THEOREM:

If L is ANY LANGUAGE WHATSOEVER over ANY FINITE ALPHABET
then SUBSEQ(L) is regular.

This is a wonderful theorem that seems to NOT be that well known.
It's in very few Automata theory texts.  It is not heard much.
It falls out of well quasi order theory, but papers in that
area (is that even an area?) don't seem to mention it much.

This SEEMS to be an INTERESTING theorem that should get more
attention, which is why I wrote this blog.  Also, I should point
out that I am working on a paper (with Steve Fenner and Brian
Postow) about this theorem.  BUT to ask an objective question:
Why do some theorems get attention and some do not?

1) If a theorem lets you really DO something, it gets attention.
There has never been a case of `OH, how do I prove L is regular?
WOW- its the subseq language of L' !!'
By contrast, the Graph Minor Theorem, also part of well quasi
order theory, lets you PROVE things you could not prove before.

2) If a theorem's proof is easy to explain, it gets attention.
The SUBSEQ theorem needs well quasi order theory to explain.
(`needs' is too strong- Steve Fenner has a prove of the |\Sigma|=2
case that does not need wqo theory, but is LOOOOOOOOOOOOOONG.
He things he can do a proof for the |\Sigma|=3 case, but that will be
LOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOONG.
Can be explained to an ugrad but you are better off going through
wqo theory.)

3) If a theorem CONNECTS to other concepts, its gets attention.
There are no real consequences of the SUBSEQ theorem.
Nor did it inspire new math to prove it.

4) If a theorem has a CHAMPION it may get attention.  For example
the SUBSEQ Theorem is not in Hopcroft-Ullman's book on automata
theory- one of the earliest books (chicken and egg problem- its
not well known because its not in Hopcroft-Ulman, its not in HU
because its not well known). The SUBSEQ theorem had no CHAMPION.

5) Timing.  Higman did not state his theorem in terms of regular
languages, so the CS community (such as it was in 1952) could not
really appreciate it anyway.

Yet, it still seems like the statement of it should be in automata
theory texts NOW.  And people should just know that it is true.

Are there other theorems that you think are interesting and not
as well known as they should be? If so I INVITE you to post them
as comments.  The theorem that gets the most votes as
SHOULD BE BETTER KNOWN will then become better known and hence
NOT be the winner, or the loser, or whatever.

NOTE: The |\Sigma|=1 case of Higman's theorem CAN be asked in
an automata theory course and answered by a good student.

Making up Problems

Guest Blogger: Bill Gasarch

HW AND EXAMS:
1. While making up the lecture notes problems may arise naturally. Such as ``OH, I don't want to bother proving this, but it would make a good HW'' or ``OH, I can do example 1 in class and leave example 2 for the HW, and 3 for exam''
2. OR the reverse- I want to ask THIS HW/exam problem, so I'll cover THAT in class.
3. If a paper you are reading for your research says `by a trivial induction XXX' then XXX might make a fine HW or exam problem. Same for other `easy' things that papers skip.
4. Do you allow your students open books? A sheet of notes? Calculators? Whichever it is, tune your questions to it, and view it as an OPPORTUNITY, not a restriction.
5. Just changing the numbers around might not be sufficient. Better to change the concepts around. EXAMPLE In class and HW I do Given Random Var X, and Dist D, find Expected value. On exam do Given Random Var X and you want Exp Value E, what should be the distribution.
6. Exams: Make it clear that you take off for clarity. This way you don't have to try to figure out if a complete mess has some idea in it.
7. Scoring: On a 20 point problem I tend to give either a 0 or a 10 or a 20. Getting the base case of an induction is NOT worth anything. Making an obvious typo is not worth taking ANYTHING off. This makes grading easier, but also you are spared having to make arbitrary distinctions that don't mean much. Do you really want to say ``On the way to a proof that wouldn't work'' vs ``On the way to a proof that might work'' vs ``On the way to a proof that would work'' are worth diff values? And then try to discern which it was? ALSO, If one student really didn't know much, and another one knew alot, I would rather the point DIFF by 20 points, rather than give 5 sympathy points, and take off 5 points for minor things, and end up with a 10 point difference.
8. There are two kinds of questions (actually I'm sure there are more) Those that test MASTERY of the material Those that test CREATIVITY- going beyond the material. I tend to ask more MASTERY questions, especially on exams.
9. What to do about students getting help from the web?
   1. Ask old questions in new ways to avoid the usual search terms.
   2. Tell students they must TELL you the sources they used. The problem here is if they DO tell you, then what do you do? You wanted them to do it on their own.
   3. HW not worth much, but ask similar questions on exams. For lower level courses you can also have short quizes.
   4. For a graduate course you can even say ``If you can understand the paper this came from and write it in your own words, AND UNDERSTAND IT then you will get full credit. But be forewarned, it may be easier to just DO it on your own.'' This WORKS for MASTERY type questions, not for problems that just need one insight, and you want the students to get that insight on their own.
RESEARCH PROJECTS:
1. ``Code it up and see what happens'' could be a basis for a research project.
2. As a warmup and confidence builder I would have a student read and UNDERSTAND two (maybe more) papers and COMBINE them. This could lead to very good research, but might not. But in any case the student KNOWS something and has DONE something.
3. If a problem dawns on you that you think someone else MUST have worked on then LOOK INTO IT. You may well find that nobody has worked on it--- what dawns on you as an `obvious' problem to work on might not dawn on others as such. Peoples motivations differ.
4. If there is some paper you've always wanted to get around to reading but never did, have a graduate student read it and explain it to you. This will be good for him and for you. Can also work with very good ugrads. Might result in survey papers if they read a series of papers. WARNING: You may end up doing more work in correcting the student, and seeing what he really meant, etc. But in the end you'll both learn the paper.

Are you a Luddite?

GUEST BLOGGER: Bill Gasarch
(I will be guest blogging this week while Lance is on Vacation.)

Are you a Luddite?
The original Luddites were workers who, scared of lower wages
via technology, destroyed factory machines. This was around 1811.
Their leader was General Ned Ludd. (Not sure if General was an honorary title)
TODAY the term has come to mean someone who does not adapt to technology
or does not like technology.
If you are NOT one, you can use Google to find out more about them.

Are you a Luddite?
I offer the following questions and let you score yourselves.

1) At a conference do you use
        a) Powerpoint with fancy animation and pictures off the web.
        b) Powerpoint with nice backgrounds, but nothing much else
        c) pdf files
        d) physical slides made using latex
        e) physical slides made using magic markers and overlays
        f) physical slides without overlays
        g) chalk
        h) draw diagrams in the sand with a twig

2) Same as question 1 but for  large classroom lecture (over 50),
small classroom lectures (under 10), seminars (8 people who actually
know something).

3) For writing papers do you use
        a) LaTeX (or some other package)
        b) Typewriter
        (YOU HAVE A TYPEWRITER? MIGHT BE WORTH SOMETHING ON EBAY!
        c) Handwritten and give to your secretary to type
        (YOU HAVE A SECRETARY? MIGHT BE WORTH SOMETHING ON EBAY!)
        d) Quill pen and inkwell on parchment.

4) When listening to talks do you
        a) Take notes with an e-pen that automatically puts it online
        b) Take notes in an e-notebook 
        c) Take notes in a p-notebook (thats paper)
        c) Not take notes at all
        d) Fall asleep

5) When you applied to grad school did you
        a) Check out the website of the school
        b) Ask your roomate who also majored in CS and Math
        c) Ask your roomate who majored in Political Science
        d) Apply to schools you heard were good
        e) Apply to schools randomly (time bounded Kolmogorov Random)

6) If you need a result that is already known do you
        a) Goto Google
        b) Goto the library
        c) Goto your own file cabinet
        d) Rederive the result by yourself

7) Which of these might you most likely say?
        a) When is the next version coming out so I can update?
        b) I'll update in 2 years (and you do)
        c) I'll update in 2 years (but you don't)
        d) You can have my chalk when you pry it from my cold dead hands.

8) Do you play music on
        a) MP3's
        b) CD's
        c) LP's
        d) 78's
        e) Wax Cylinders
        (WAX CYLINDERS! MIGHT BE WORTH SOMETHING ON EBAY!)

                                        bill g.

Postscript: Thanks to my collegue Jack Lutz for catching that I spelled Luddite wrong
originally. I used him instead of a spell checker, and note that the error he found
would not have been discovered with a spell checker.

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.