New Priorities for Computability Theory

Bob Soare, who wrote one of the great textbooks on recursion theory and then almost single-handedly changed the name of the field to computability theory, teaches an intense two-quarter class on the topic every other year in Chicago. To my surprise just now, halfway through the second quarter (15 weeks into computability theory) he is just proving the solution of "Post's Problem", the existence of incomplete degrees, that excited Gödel in his letter.

When I sat in on Soare's class in the early 90's, by this time he had covered much more complicated finite injury arguments and was starting the infinite injury constructions like the Sacks Density Theorem: Given r.e. sets A and B, such that A is reducible to B and B is not reducible to A, there is a set C that lies in between.

I asked Soare about this last week. He isn't dumbing down his class, rather he's acknowledging a change in direction in the field, more along the lines of looking at the complexity of reals (infinite sequences of bits), often by examining those defined by infinite branches of computable trees.

For example, many computability theorists today are studying notions of "random reals", infinite sequences that share some properties of randomly chosen numbers. They have shown neat connections to Kolmogorov complexity and connections to Chaitin's Ω. For any reasonable ordering, Chaitin's Ω is a computably enumerable random real and Kucera and Slaman show the surprising result that the converse is true as well.

One used to measure a recursion theorist by the difficulty of their constructions; now we see more a focus on the beauty of the theorems and their proofs.

Soare is working on a new version of his textbook that will differ in a couple of ways. He is changing terminology (recursive and r.e become computable and c.e.), but more importantly he changes the focus to more strongly develop the theory that drives computability today. A good lesson: Fields change over time and better to acknowledge and embrace those changes than to fight them.

The Home Stretch

If you have an academic job offer, what next? Don't forget to negotiate. I wrote a post on negotiating last fall and in particular you should read the Chronicle article. Worst mistake: Not negotiating.

If you don't have an offer yet, don't panic (at least not too much). We are just entering the home stretch of the CS academic job season. Many of the same few people get the initial interviews and once they get sorted out, more interview and offers are still to come. Don't be afraid to contact departments still in play and remind them of your continued interest.

My first time on the job market in 1989 I didn't get my first offer until June and still had an interview after that. The system has only become even more insane since.

Still you might start getting ready for Plan B. Consider lowering your sights, seeking temporary and/or overseas positions, or thinking about industrial jobs.

Searching for jobs is perhaps the most stressful time in one's academic career. Do your best to keep your spirits up and your options open.

Kurt Gödel (1906-1978)

Kurt Gödel came into our world one hundred years ago today. Gödel's incompleteness theorems changed the way we think about mathematics.
We reprint the translation of the now famous letter he wrote fifty years ago to von Neumann which was rediscovered in 1988. This letter describes something close to the P versus NP problem years before the field Computational Complexity even had its name. SIGACT and EATCS jointly sponsor a prize named after Gödel because of the letter.
Princeton, 20 March 1956
Dear Mr. von Neumann:
With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery.
Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = max_F ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n²), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since

1. it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem and
2. after all φ(n) ∼ k ⋅ n (or ∼ k ⋅ n²) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or (log N)²).

However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.
I do not know if you have heard that "Post's problem", whether there are degrees of unsolvability among problems of the form (∃ y) φ(y,x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear.
I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife,
Sincerely yours,
Kurt Gödel
P.S. I heartily congratulate you on the award that the American government has given to you.
[The text is taken from this page where you can also find the original German text and acknowledgments. John von Neumann, who received the Presidential Medal of Freedom in 1956, had cancer at the time of the letter and passed away in 1957.]

Richard Rado (1906-1989)

Tomorrow marks the hundredth anniversary of the birth of combinatorialist Richard Rado. Rado is the second most famous mathematician born on April 28, 1906 so we will celebrate him a day early.

In complexity Rado is best known for the Erdös-Rado Sunflower Lemma. A sunflower is a collection of sets S₁,…,S_k such that any two have the same pairwise intersection, i.e., for all 1 ≤ i < j ≤ k, S_i∩S_j=S₁∩S₂. A Venn diagram of these sets would look like a sunflower.

The sunflower lemma states that given any collection of m distinct sets of cardinality s with m>s!(k-1)^s, there is a subcollection of size k that forms a sunflower. The size of the universe plays no role in the statement of the lemma.

The proof is a nice induction once you figure out the right variable to induct on. Try it yourself or read it here.

The sunflower lemma has played a major role in many results in computational complexity, most notably in Razborov's proof that clique does not have small monotone circuits.

Overheard

"…which also gives better heuristics for the Traveling Salesman Problem."

"Don't you mean the Traveling Salesperson Problem?"

"No, the Traveling Salesman Problem. A traveling saleswoman would have asked for directions."

Theory and Systems

An anonymous graduate student asks

Why do theory students have to take systems courses?

Most American Ph.D. programs have distributions requirements where every student must take courses and/or exams in many different subfields of computer science. Why have these distribution requirements and in particular why should theory students need to know systems concepts they feel they will never use.

• If a student becomes an academic computer scientist they will have to evaluate systems candidates for hiring and tenure and better they can tell the difference between good systems and bad systems.
• Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality, all computer scientists should do some programming to get a better feeling about the concept of computation.
  The mission of computational complexity is to understand the power of efficient computation and how can one really understand efficient computation if they don't try to do it themselves.
• A good systems class will surprise many theory students by showing that much of systems have a strong theoretical underpinning and basic concepts like abstraction underlies both theory and systems. Some very good theoretical work has arisen from questions from the systems community and vice versa.

Many new Ph.D. students make the mistake of trying to fulfill all of their distribution requirements as soon as possible. But this makes the beginning of the Ph.D. program feel like an extension of undergraduate education. Better to take the courses over time and get involved in research as soon as possible.

I did receive my Ph.D. in Applied Mathematics and didn't have a systems requirement. But I did take systems classes as an undergrad and during my first year at Berkeley and I did extensive programming in high school and during my undergrad days. Programming has helped me tremendously in my research. Putting together old theorems to make new theorems is not unlike making different pieces of code work together.

One might also ask why theory students should take AI courses? I'll leave that to a future post.

One Miserable Year

Luca and his commentors get dreamy-eyed over Berkeley but not everyone has such fond memories of that place.

I arrived in Berkeley for graduate school in August 1985. When I went to the off-campus housing office, there was dead silence as hundreds of people looked over a small number of listings. A TV news crew arrived to interview some students who had been looking for months for a place. The ridiculous rent-control laws of the city led to an incredible housing shortage. I ended up moving into a dorm at Mills College, thirteen miles from campus.

The city had a horrendous homeless problem which meant you couldn't walk down the street without being constantly asked for money. Berkeley, home of the free speech movement, was in fact the most intolerant place I have ever been to. Many ads for housing, jobs and the school newspaper required applicants to be "politically correct". And my favorite: A man drops garbage on the front lawn of City Hall, calls it art, and there is an actual debate on whether the town has the right to remove it.

Initially I didn't fit in well socially with the other theory students, partly because I lived so far from campus and didn't have an office my first semester, and party because I didn't fit well into their culture. I broke my finger playing touch football with my dormmates. Some theory students thought I made the story up, how could I be so foolish to play such a game. Others said "serves you right".

I nearly dropped out of graduate school that year. When my advisor, Michael Sipser, decided to move back to MIT I happily followed him.

I did have some good experiences from that year in Berkeley. Many of my fellow graduate students at that time are now some of the leaders in their fields and I consider many of them good friends. MSRI had a special year that year on Computational Complexity with many visitors and seminars. Berkeley hosted STOC and the very first Conference on Computational Complexity (then called Structures), a conference that would become an important part of my life. And I can't deny Berkeley has great food.

The following fall at the MIT theory group picnic we played touch football. I found where I belonged.

Student Weblogs

A few days ago I put a look of horror into one of our graduate students when I went up to him and simply said "You should be careful about what you write in your weblog."

The number of weblogs continue to grow and more and more students are starting to put their thoughts online. Many of them write brutally honest opinions of some of their academic and non-academic experiences or just write very silly or nasty stuff about themselves or each other.

You might think that only the fellow students you have told about your weblog read your weblog, but chains of links are easily followed. Many of us also have automated searches; if you link to my weblog or use the phrase "Computational Complexity", I'll see what you have said. If you really want to limit your readership you can put in some password protection and I strongly suggest that you do so.

Luckily for the student above, I just laugh off such weblog entries, but they can come back to haunt you. When you apply for jobs, you will get Googled and your odd weblog entries can count against you. Deleting your entries off the internet does not necessarily make them disappear, they might have been downloaded or cached.

Just remember when you write your next post, the Internet never forgets.

Favorite Theorems: Small Sets

March Edition

In 1976, Juris Hartmanis and Leonard Berman defined the isomorphism conjecture: For all pairs of NP-complete sets there is a reduction from one set to the other that is 1-1, onto, polynomial-time computable and polynomial-time invertible. As a corollary to the conjecture all NP-complete sets must have many strings in them. They asked whether there could be any NP-complete sparse sets, where a set is sparse if the number of strings of length n is bounded by n^k for some k.

Steve Mahaney in 1982 settled this second question.

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis by Steve Mahaney, JCSS 1982.

Mahaney's theorem states that if P≠NP then there are no sparse NP-complete sets.

Before Mahaney, Piotr Berman (no relation to Leonard) in 1978 showed that there can't be NP-complete Tally sets, where a tally set is a subset of 1^*. Steve Fortune extended this work to show that co-NP cannot have sparse complete sets. (These results assume P≠NP.)

To adapt Fortune's techniques for NP-complete sets, Mahaney had to find a way to know when strings were not in the sparse set. If one knew how many strings were in the set, and one found all those strings then you knew the rest were not in the set. Mahaney then just showed you could try all possible sizes of sparse sets. This neat idea of finding what's not there by finding everything that is there played a role in many future results in complexity, most notably in the proof that nondeterministic space is closed under complement.

In 1991, Mitsu Ogihara and Osamu Watanabe give a simpler proof using Left Sets, the set of pairs (φ,w) such that w is lexicographically smaller than some witness for φ. Ogihara and Watanabe's paper also extends Mahaney's theorem to show that a reduction from SAT to a sparse set that asks only a constant number of queries would imply P=NP. Whether a reduction using O(log n) queries implies P=NP remains open, even in relativized worlds.

Ham Radios, Coding Theory and the Internet

Venkat Guruswami talked at TTI last week giving an overview of recent work in list decoding. Someone asked him about practical applications of his work and he mentioned ham radio operators now able to error-correct signals bounced off the moon.

My memories of ham radio go back to summer camp. As one of the activities, we could go to a trailer with the Ham Radio Guy (who looked something like this) and we would try, not always successfully, to reach other ham radio operators around the world using Morse code and occasionally voice. Plastered around the trailer were postcards from other ham radio geeks he did talk to.

Ham radio was sort of a precursor to the Internet, which begs the question—Why hasn't the Internet made ham radio obsolete? You get much better bandwidth over TCP/IP than bouncing signals off the moon and you don't need a license to use the Internet.

The iCal Effect

The iCal standard allows sharing of events and calendars. The standard has been around for many years and has been popular with Apple users but the new Google Calendar will become the first popular cross-platform system to support the standard. While several sharable calendars already exist, we should see a dramatic growth in the use of this standard.

How would I like to see the iCal standard work in our community?

• Academic Departments can put their seminar calendar in the iCal format. No longer would I have to subscribe to email list to see events and then have to enter the events that I care about into my calendar manually.
• Any email that announces an event or meeting should have an attachment I can click that adds it to my calendar.
• Conferences could create calendars listing the important dates (submission, notification, proceedings version, registration) as well as the dates of the conference, perhaps even having the schedule of talks in iCal format with links to the papers. (I don't think iCal supports links but hopefully some later version will).
• One might also want a theory iCal calendar listing all conferences but this would likely have too much information to be useful.
• I have wasted much time trying to schedule meetings. Ideally I'd like a system that searches everyone's calendars and finds a common free time.
• As with many standards there are some great applications not initially anticipated but will develop over times.

Google with this Calendar and also their Talk program embrace standards where other related companies have not. Early standards like FTP, SMTP (email), HTTP, and HTML have allowed the Internet to grow to the force it is today. The RSS standard has allowed sharing of information in unprecedented ways. The iCal standard will help us save time scheduling time.

Microsoft Academic Search

Microsoft just announced their Academic Search, a direct competitor to Google Scholar. Scholar is incredibly useful at tracking down electronic versions of documents but using it to find bibliographic information can be frustrating. Here Academic Search shines, hold your mouse over an entry and the right pane gives the bibliographic information including abstract and you can also get a Bibtex or Endnote version. But actually downloading a paper requires more clicks than Google.

I tried some random searching and Academic Search is missing many papers. But it does index some Elsevier papers, where Google never got the rights. But there is a back door in Google via ACM. For example, do a Google Scholar search on Occam's Razor, click on the Blumer et. al. paper and it will bring up the ACM Digital Library page that indexes the Information Processing Letters article. Click on the DOI bookmark and it will take you to Elsevier's page.

In short Microsoft has the much nicer interface but not yet the breadth of articles. If your sole goal is to download the paper, better to use Google.

A little less related to academics, you might want to check out Google's just released Calendar. Looks impressive.

Gödel Prize

The EATCS has announced the winners of the Gödel Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena for their paper Primes in P.

I started this weblog shortly after the announcement of the Primes in P result which was the topic of my third post. Now the result has won the award for best recent journal paper. Either that was a very quick process or I have been writing this weblog too long.

What Math to Take?

A good reader question.

I was curious if you had any discussions on what kind of math background new graduate students need to have? For instance, if the undergraduate institution did not have a good math program to support the CS curriculum, what specific topics should students self-study before going to graduate school?

Most importantly you should have some familiarity with mathematical proofs. Mathematical maturity is more important than specific knowledge in any single topic.

Theoretical computer science is mostly discrete mathematics and other areas of discrete math play an important role: Discrete probability, combinatorics, algebra especially group theory, logic and number theory.

Depending on your interests analysis, measure theory, topology and algebraic geometry might be important. Almost every branch of mathematics has played some role in theoretical computer science.

I don't mean to scare you. As I said best to take any real math course (one with proofs, not just Plug-and-Chug Engineering math) and you can later pick up more specific math knowledge when you need it.

Reviewer Ethics

When you are asked to referee a paper you need to follow a set of ethical guidelines that are rarely spelled out and often ignored. Here are the rules as I see them.

The same ethical rules apply to refereeing papers or reviewing manuscripts for conferences. By "editor" I mean whomever asked you to referee or review the paper.

You should not review a paper co-authored by yourself, a member of your institution, someone you are related to, or having relations with. It is fine to referee papers by recent co-authors or by your former advisor or students. The conflict rules are not transitive, you can referee a paper by someone else at your brother's institution. If for any reason you do not feel you can give an unbiased review of the paper, discuss your issues with the editor or just refuse to referee the paper.

You should only discuss the paper with the editor. The fact that you are a referee, or even that the paper was submitted is confidential information. You should not ask someone else to look at any part of the paper without the editor's permission. You must never ever contact the authors directly.

If the paper has not yet been publicly announced, you must follow Rule Number One

Other than reviewing the paper you must ignore the paper completely for any other purpose, including your own research, until the paper appears.

If you find a simple extension or simplification of the paper: Tell the authors through the editor, they will likely add it to their paper and give you credit through a nice acknowledgment to the "anonymous referee."

If you find a significant extension to the paper: Shame on you, you have already violated Rule Number One. Best thing at this point is to wait until the paper appears and then write your extension. If the authors or someone else beats you to it, or the papers never appears, that's what you get for violating Rule Number One.

You also have put yourself in a messy situation since you are now no longer unbiased in the outcome of the paper. If you think there is a significant extension, mention the possibility in your report or keep it to yourself but don't work on it. It only leads to trouble.

The Life of the Party

From Jay Leno's monologue on Monday's Tonight Show

Scientists have been working on a device that will tell when you are boring or irritating in social situations. Who really needs this device?…Scientists.

Normally I'd complain about such stereotypes, but social grace is just not one of our strengths.

How Many Students?

From an assistant professor comes a question

How many Ph.D. students should a professor advise?

There is no single answer. The usual constraints are time and money. It depends on one's teaching, administrative and other time constrains (such as advising Master's and Bachelor students) as well as the ability to fund such students. Also how do you count part-time students, students not in residence, students you officially or unofficially co-advise and students from other schools who are long-time visitors at your institution.

I ideally like to advise three full-time Ph.D. students at any one time. More and I find it difficult to find interesting research problems for the students and not enough time to properly help their research along.

Some professors can handle more students, some should never advise any students. Particularly in the more applied areas of computer science, professors need a considerable number of slaves graduate students to help them with their projects. It's much easier to tell someone what to code than what to prove.

The Terror of the Unabomber

Ten years ago today federal agents went to a remote cabin outside Lincoln, Montana to arrest one Theodore Kaczynski, also known as the Unabomber.

Just a couple of months before I started graduate school at Berkeley in 1985, one of the students in that department, John Hauser, picked up a package in the computer science lab that detonated and cost him some fingers and his vision. We all had heavy warnings about opening packages during orientation, what a way to start graduate school.

I didn't think much about the Unabomber again until 1993 when Yale University CS professor David Gelernter was injured when a package exploded in his hands. At this point the FBI sent major alerts to all of the CS departments including Chicago and started interviewing faculty about former students. The Unabomber became the main topic of discussion and many of us became very careful about opening any package until his capture in April 1996.

Many students today have never heard of Kaczynski or the Unabomber as he safely spends the rest of his life behind bars. But this mathematician turned bomber made us quite scared and paranoid back in the mid-90's.

Baseball is Back and All is Good in the World

The Chicago White Sox have raised their championship banner and started a new season with a rain-delayed win.

A team wins the World Series, their first in 88 years, and the main story in the following spring is whether they can win it all again. Similarly, you could prove a major theorem, answering an 88 year-old question, and a few months people will ask what you've done lately.

Uniform Derandomization Assumptions

In 1986 during the prehistory of Hardness vs. Randomness, Sipser showed that if time does not have nontrivial space simulations one can derandomize. Given a (later-proved) assumption about extractor constructions

If there is a constant c such that DTIME(2^cn) is not contained in DSPACE(2^.99cn) then P=RP.

Later results used hardness against nonuniform circuits to derandomize complexity classes. For example Impagliazzo and Wigderson show

If E does not have circuits of size 2^o(n) then P=BPP.

where E=DTIME(2^O(n)).

I recently discovered that Peter Bro Miltersen in his derandomization survey (page 56) notes that you can use a uniform assumption, a weaker version of Sipser's assumption.

If E is not contained is DSPACE(2^o(n)) then E does not have circuits of size 2^o(n) and thus P=BPP.

Miltersen's proof works by searching all circuits, using the local checkability of E to verify the correctness of the circuit.

You can even assume the circuits have access to QBF or Σ₂^p gates, the later an assumption we needed in a recent paper. Saying E is not contained in subexponential space is so much nicer than saying E does not have nonuniform subexponential-size circuits with Σ₂^p gates.

Technical Note: For all of the above you need to assume the separations at all input lengths.

Choosing Graduate Schools

An anonymous commenter asked

Many of us seniors are currently choosing among PhD programs. As you probably know, we are expected to come to a decision by April 15.

Would you mind sharing with us your advice on how an aspiring theorist should go about making this very difficult and important decision? I personally would find such a post very informative, and I'm certain many others would agree.

A great question but one where I have a conflict of interest—In my view you should all have Chicago as your first choice.

So instead I will post this advice from Bruce Maggs (from a 2001 interview via Higher Cohomology).

Choosing an university can be sometimes easy, sometimes hard. You may choose a university because there's a particular faculty member that you want to work with. That's risky, because often there's no guarantee that the faculty member will be able to take you on as a supervisor. As a general rule, it would be best to choose an university with a reputation for high-quality research results. This can be measured, well, by your opinion of different research papers. If you look at some papers, and you find some that you think are good, look where those authors are from. This may be difficult for a student who has yet to begin a research career: then the advice of faculty members at your undergraduate institution can help. I think it is generally a good idea, although I didn't follow this advice, to study for a graduate degree at a different school than your undergraduate institution, because you'll get a different point of view from the faculty, as you will meet many new potential collaborators. In choosing a graduate school the most important thing is that you understand what it is that you want to study.

Let me add that you should, if all possible, visit the schools you are interested in, talk to the faculty and current students. Make sure that you will feel comfortable in that environment, it will make for a much more enjoyable graduate experience.

Science Without Borders

Berkeley complexity theorist Luca Trevisan travels to China and you can read all about it in his new weblog In Theory.

But suppose you couldn't. A Slashdot reader asks What would we lose from a regionalized Internet?

If the internet was separated into regions, how much would you lose? How often do you visit other countries' web sites? How often do you e-mail people in other countries? What would foreigners lose by not being able to visit US-hosted sites, and how quickly would they be able to recreate what they lost? What other process that we are not normally aware of depend on a borderless internet?

As an academic an international internet has gone from being a useful tool to a critical part of scientific progress. Yesterday alone I had four conversations with different scientists abroad on topics like collaborations on conference and journal papers, conference organization and recommendation letters. Many of my co-authors live abroad and my research would greatly suffer if I could not so easily communicate with my colleagues. Right now I can collaborate with a researchers in Israel as easily as one in New York.

Beyond that I download papers off of researchers homepages abroad and they download my papers from mine. Archive and online journal sites would have to be sychronized on different parts of a separated internet, a difficult task to maintain. Tools like Citeseer which seek out online papers would not function as well. And many of you would not be reading this post—Nearly a third of the readers of this weblog reside outside the US. And how would Luca write to us from China about his travels there?

Speaking of Slashdot, Zeev Dvir writes

Just wanted to let you know about the current Slashdot poll on whether P = NP. The comments are hilarious.

Sigh.

Making Complexity a Spectator Sport

A graduate student recently said

Computational Complexity is not a Spectator Sport

meaning that to truly understand and appreciate computational complexity research you need to be an active researchers yourself.

But we can't keep the attitude that computational complexity can only be appreciated by complexity theorists or we become closed and irrelevant. We need to sell complexity and the rest of theory to the scientific community and the public at large.

We can learn some lessons from great spectator sports like baseball. One cannot truly and deeply understand baseball unless you have played the game on a regular basis. But professional baseball knows they wouldn't exist without their fan base. They make the game interesting to fans at different levels of understanding, from casual fans who barely know the basic rules of the game, to sophisticated fans who understand the nuances of strategy.

While I will never expect to see us proving theorems in front of fifty thousand screaming fans, we should aim to make our work understandable and interesting to fans of theory who have different levels of knowledge of the field.

Links for Friday

Bill Gasarch sends in some links on recent activities at Harvard. The Harvard alumni magazine has an "objective" (according to Gasarch) article The End of a Presidency. Also former Harvard College Dean (and Gasarch's Advisor) Harry Lewis has a new book Excellence Without a Soul with an excerpt in the Chronicle, Has Harvard Lost Its Way?

Meanwhile Nature has a online section 2020 – Future of Computing. An editorial about the section talks about an interesting relationship between science and the computer industry.

The computer industry knows that scientists can come up with strange ideas and requirements that may well, in time, have broader commercial application elsewhere. This is one of the reasons why Microsoft is engaging the scientific community with its new Towards 2020 Science report on computers in science. That report inspired this week's focus on computing in Nature. Microsoft is sponsoring free web access to our articles on the subject, although, as always, the content is exclusively Nature's responsibility.

As computing gets ever cheaper, quicker and more powerful, scientists would do well to remember that, by being a demanding and stimulating "user community" that engages the interest of companies such as Microsoft, Google and Intel, they can influence the development of the field, to everybody's benefit.

Large Search Problems for Small Inputs

At Dagstuhl last week Jehoshua Bruck gave a talk giving some interesting open combinatorial problems that have real-world applications. For example the following conjecture by Kotzig has applications to redundant disk arrays.

For every even n, one can partition the edges of the complete graph on n vertices into n-1 perfect matchings such that each pair of perfect matchings forms a Hamiltonian cycle.

Kotzig's conjecture is known to hold for n=2p and n=p+1 for all primes p and a few other special cases. The conjecture remains open for n=16. One would think we could solve the n=16 case by brute-force search but the search space is just too big.

This is an NP problem, one can check a partition quickly. For all those who think they have great heuristics for NP problems, go find the partition and then talk to me.

Bruck also asks how many gates does one need to solve parity on AND-OR circuits with unbounded fan-in. For n-bit inputs the answer is between 2n and 2.5n-2. The first open case comes when n=6 which requires either 12 or 13 gates. Six does not seem like a large number but still there are far too many circuits on 12 gates to check quickly.

Favorite Theorems: Relativization

February Edition
After the work of Cook and Karp popularized the P versus NP question, computer scientists immediately tried hard to prove P=NP or P≠NP. Baker, Gill and Solovay showed that most of their approaches were doomed to failure.

Theodore Baker, John Gill, Robert Solovay, Relativization of the P=?NP Question, SICOMP 1975.
Baker, Gill and Solovay noted that complexity proofs relativized, that is held even if all machines involved could make queries to some "oracle," i.e., making queries to some fixed set. They created oracles A and B such that

• P^A = NP^A
• P^B ≠ NP^B

If one had a relativizable proof that P ≠ NP then the proof would also show P^A ≠ NP^A, contradicting their theorem. Baker et. al. give a few more relativization results and we've seen hundreds more since.
The paper gives very little about the philosophical implications of their results. For a short while some researchers thought that these results could lead to true independence of the P versus NP question, but this thinking was quickly abandoned and later we have seen some theorems that do not relativize, particularly in the area of interactive proof systems.
Relativization results do help us understand what theorems to pursue, what techniques cannot solve our questions. Nearly all the techniques we know for time classes, outside of the algebraic techniques used for interactive proofs, do relativize. Only a very few of the known relativization results later had proofs in the opposite direction.
For more read my 1994 survey The Role of Relativization in Complexity Theory.

Avoiding South Dakota

Because the state recently banned nearly all abortions, there is a call to boycott South Dakota, coincidentally where my family vacationed last summer.

Suppose there was an interesting conference being held in South Dakota. Would you go? There is some precedence—I knew some computer scientists who refused to attend meetings in South Carolina a few years ago when they flew the Confederate flag over their State House.

By avoiding the conference you are mostly hurting the researchers in that state, who likely do not share the government's viewpoints and cannot easily move. Many scientists worldwide don't like much of current US foreign policy but I would hope they wouldn't avoid American conferences for that reason.

An Interview with Vardi

Alex Lopez-Ortiz points out that this month's SIGMOD Record has an interview with Moshe Vardi from Rice University that touches on several topics of interest to the readers of this weblog. Lopez-Ortiz picked out some highlights of Vardi's views.

1. On relevance of work and best-paper awards:

   We now have interesting tools to evaluate the success of work in the long term. Things like Citeseer and Google Scholar suddenly give us a view that we could not have had before. One thing that we discovered from these tools is that we are actually very poor in predicting the long term impact of work. There is very little correlation, for example, between the best paper awards that we give and the test-of-time awards that we give. Sometimes, miraculously, we have the same paper win the best paper and the test-of-time awards. But that is the exception rather than the rule. So I think people should focus on just doing the best work they can.

2. On highly selective conferences and low acceptance rates:

   I think the low acceptance rate is a terrible problem. I think that the idea that we are raising the quality is nonsense. I think that actually the quality goes down. I think we are very good at selecting about one third to one fourth of the papers; we do a pretty good job there. As we become more selective, the program committee gets larger, the whole discussion gets more balkanized, and the whole process gets more random. Nobody gets a global view.…Conferences are not scalable. They work nicely with up to roughly 300 submissions and a certain size of program committee. When you try to scale it up, very good papers get lost. It becomes more political. I think we are being held back by our own success.

3. On conference publication vs journal publication (Here I did some serious cut and pasting—Alex):

   We are very unique among all the sciences in how we go about publication. We have these selective conferences. (People have stopped calling them refereed conferences. They are not really refereed. You don't get good referee reports.) Our conferences worked well in the world we used to inhabit…I think we had a model that worked successfully for about 30 years, but now we see cracks in the foundations…I don't have a good solution to this problem. We don't even have a good forum in which to discuss the problem… We ought to rethink how we do it. Right now, people try to fix things incrementally by having a larger conference with a bigger program committee, a two-level PC, a three-level PC. Maybe we need to rethink the way we do scholarly communication in our discipline…How can computer science go about changing its publication culture? Are there areas that move just as fast as we do, and have journal papers and conferences, but conferences are not the primary vehicle? I have questions about the basic model of scholarly publications. And I find it fascinating that it is difficult to have a conversation about this on a big scale, and make changes on a big scale. We are very conservative. It is interesting that computer science has been one of the slowest disciplines to move to open access publications. Other disciplines are way ahead of us in using online publications.

There is much more, I definitely recommend reading the whole thing.

The Podcast of Uninformed Decisions

Live from Schloss Dagstuhl, the fifth Complexitycast. Our guest is Eldar Fischer who talks about his love and joy, Property Testing. For more read his survey The Art of Uninformed Decisions. MP3 (18:05, 3.1MB).

Another Approach to P ≠ NP

Last week's Numb3rs episode "Mind Games" centered on a purported psychic causing the mathematician Charlie Eppes to exclaim "Let's all sit down at the Ouija Board and try to solve P versus NP once and for all."

Resolving Dagstuhl

This week I am at the Dagstuhl seminar Complexity of Boolean Functions. Schloss Dagstuhl is an isolated conference center in Southwestern Germany that hosts weekly seminars in computer science. They have room and board at the center and it is difficult to go anywhere from here so we are forced to spend time with each other, a good thing for research.

Someone at the workshop pointed out that the STOC 2006 program has been posted and lists the award winners. The best student paper award is going to Anup Rao for Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources and Jakob Nordström for Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. The best paper award is (surprise, surprise) going to Irit Dinur for her PCP Theorem by Gap Amplification.

Nordström gave a talk on his paper Monday. A resolution proof of unsatisfiability of a CNF formula takes a clause containing x and another clause with the negation of x and resolves it into a clause containing the remaining variables of the first two clauses. A CNF formula is unsatisfiable iff there is a resolution proof that leads to the empty clause. In 1985, Haken showed that there are no polynomial-length resolution proofs for all unsatisfiable CNF formula.

The width of a proof is the size of the largest clause produced. The space of the proof is the number of clauses one needs to keep in memory. No immediately obvious reason that the two should be related but in fact the space is an upper bound on the width and conjectured to be the same up to constant factors. Nordström disproves the conjecture by giving a family of formulas where the width is constant but the space is not.

March Madness

It happens every spring, America's favorite binary tree, the NCAA Men's Basketball Tournament Bracket was announced Sunday night. This is a single elimination tournament; win and move up the tree. In offices across America, people print and fill out these brackets guessing the winners of each game.

How do you score a person's predictions given the final outcome of the games? One could simply give one point for each game, other pools double the points in each round so each round is worth a total 32 points. Or one could base the score on seeds—there are four regions where each has 16 teams in some predetermined order of strength. Some pools give more points to predicting an upset, like seed 13 beating seed 4.

Is there a mathematically ideal way to score the predictions in the tournament yet simple enough for the average American office worker to understand? Billions of dollars are wagered on the NCAA tourney, so creating the perfect scheme can make quite a splash in the world of office pools.

On P versus NP

I receive several requests to comment on various papers claiming to prove P = NP, P ≠NP, or the independence of the P versus NP question on this weblog. I have a healthy skepticism about all such claims and simply don't have time to carefully read and evaluate those papers. If there is verified significant progress towards the P versus NP problem you will read about in on this weblog (though the converse is not true).

Sometimes I get a flood of requests about a certain P versus NP attempt, such as the upcoming Berkeley math department Workshop on P vs NP. I don't have much to say, the workshop is not involving any of the Berkeley theoretical computer scientists and in the past we've seen other, sometimes famous, mathematicians who have believed they have an approach to the P versus NP problem that in the end don't pan out. To the organizers' credit, at least they acknowledge they don't yet have a proof.

Presidents and Faculty

University presidents come and go but Lawrence Summers announcement last month that he will resign as Harvard's president has and still continues to create considerable discussion in the media. Summers was best known in the non-Harvard academic world for his politically-incorrect suggestion that the low representation of woman in the sciences could be party due to biological difference between man and woman.

Within Harvard he managed to upset the faculty in other ways and the faculty's lack of confidence in Summers was a factor in his resignation. Many of the opinions I see point to the faculty as unfirable zealots unwilling to allow a reformer like Summers do his job. For example consider the excerpt from an Op-Ed piece in the New York Times.

It now remains to be seen whether Harvard's Faculty of Arts and Sciences is capable of self-critique. Will its members acknowledge their own insularity and excesses, or will they continue down the path of smug self-congratulation and vanity? Harvard's reputation for disinterested scholarship has been severely gored by the shadowy manipulations of the self-serving cabal who forced Mr. Summers's premature resignation. That so few of the ostensibly aggrieved faculty members deigned to speak on the record to The Crimson, the student newspaper, illustrates the cagey hypocrisy that permeates fashionable campus leftism, which worships diversity in all things except diversity of thought.

and this from a professor, Camille Paglia of the University of the Arts in Philadelphia.

The University of Chicago is getting near the end of its own presidential search as our current president Don Randel is moving on to head the Mellon Foundation. The Search Committee is a combination of trustee members and faculty, where the faculty members of the committee were chosen by election from the faculty at large. If the faculty doesn't like the new president then we will have no one to blame but ourselves.

Update 3/9: That was quick. Bob Zimmer, a mathematician, was just nominated for the University of Chicago presidency.

Computation and Geometry

Michael Nielsen returns to blogging after seven months since his last real post. He talks about his new Science paper Quantum Computation as Geometry with Dowling, Gu and Doherty. Last year Nielsen had an arXiv paper A Geometric Approach to Quantum Circuit Lower Bounds where he showed one can bound the minimal-size quantum circuit to implement a unitary operation U by the length of the minimal geodesic between the identity and U. The new Science paper shows the other direction, given a short path one can find an efficient quantum circuit.

While others are also trying geometric approaches to separate complexity classes, by having a tight result, the minimal geodesic gives us the right bound. Nielsen also shows that finding the minimal geodesic is as hard as solving a lattice closest vector problem, which means this approach might not have the constructivity requirement of Razborov-Rudich Natural Proofs. Since quantum circuits can simulate classical circuits, one can possibly prove classical lower bounds as well, maybe even an attack on P versus NP?

Well, I can dream, can't I?

Computational Thinking

In this month's CACM, CMU Chair Jeannette Wing wrote a neat Viewpoint column Computational Thinking (with related slides). In the article she argues that many of the techniques we use to reason about computation apply to much wider range of problems. She gives many aspects of computational thinking such as

Computational thinking is using abstraction and decomposition when attacking a large complex task or designing a large complex system. It is separation of concerns. It is choosing an appropriate representation for a problem or modeling the relevant aspects of a problem to make it tractable. It is using invariants to describe a system's behavior succinctly and declaratively. It is having the confidence we can safely use, modify, and influence a large complex system without understanding its every detail. It is modularizing something in anticipation of multiple users or prefetching and caching in anticipation of future use.

Wing goes out of her way to separate computational thinking from thinking about computers.

Computational thinking is a way humans solve problems; it is not trying to get humans to think like computers. Computers are dull and boring; humans are clever and imaginative. We humans make computers exciting. Equipped with computing devices, we use our cleverness to tackle problems we would not dare take on before the age of computing and build systems with functionality limited only by our imaginations.

Jeannette Wing makes a strong case that computational thinking should be as important a part of the learning experience as the three R's, though in CACM she preaches to the choir. She suggests that computer science professors teach a course "Ways to Think Like a Computer Scientist." But how do we convince students they should take it?

Computer-Assisted Proofs

Thomas C. Hales talked at the recent AAAS meeting about his proof of the Kepler conjecture. From a New Scientist item

In 1998 Hales submitted a computer-assisted proof of the Kepler conjecture, a theorem dating back to 1611. This describes the most efficient way to pack spheres in a box, wasting as little space as possible. It appears the best arrangement resembles the stacks of oranges seen in grocery stores.

Hales' proof is over 300 pages long and involves 40,000 lines of custom computer code. When he and his colleagues sent it to the Annals of Mathematics for publication, 12 reviewers were assigned to check the proof. "After four years they came back to me and said they were 99% sure that the proof was correct and they said were they exhausted from checking the proof," Hale says.

As a result, the journal then took the unusual step of publishing the paper without complete certification from the referees.

Should we trust such a computer-assisted proof? I have more faith in a computer properly executing its code more than a mathematician verifying a proof. But what should constitute a legitimate proof when part of that proof is verified by a computer?

In most mathematical papers, we don't give formal logical proofs of our theorems. Instead we give a detailed proof that gives all of the necessary ideas to convince the reader that a formal proof would be possible. But, at least with our current technology, that level of informality will not work with computer code. So any proof using computer verification should have a formal proof of the correctness of the code.

This would require significant work from the author, but we are talking about establishing mathematical truths. When the other alternative is publishing the solutions to major open questions without being fully refereed, what choice do we have?

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.