2006 Year in Review

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

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

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

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

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

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

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

Foundations and Impacts

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

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

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

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

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

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

An Internet-Free Week

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

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

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

A Recommendation Letter

December 22, 2006

Dear Recruiting Committee:

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

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

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

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

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

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

Sincerely,

Lance Fortnow
Professor of Computer Science

The Necessity of Engineering for Science

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

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

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

Entertainment Tidbits

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

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

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

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

Show Us Your Research

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

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

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

The Mega-Conferences

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

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

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

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

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

Motivation

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

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

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

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

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

Science a Victim of Politics Again

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

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

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

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

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

More from the CRA.

You Ask, We Answer

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

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

Favorite Theorems: Second Decade Recap

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

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

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

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

Reductions To SAT

Standa Zivny asks

I'd like to ask you about CLIQUE→SAT reduction. The reduction 3-SAT→CLIQUE is a standard one from undergrad course. Since SAT is NP-Complete, every problem from NP, i.e., CLIQUE as well, is reducible to SAT. Is this reduction "known", i.e. defined by some "natural way" as the reduction 3-SAT→CLIQUE is? Is that true for all NP-C problems?

The reduction in Cook's paper create formulas with variables that represent the entire computation of an NP machine accepting CLIQUE. We can often do much better. Consider the problem of determining whether a graph on n vertices has a clique of size k.

Variables: y_i,r (true if node i is the rth node of the clique) for 1 ≤ i ≤ n, 1 ≤ r ≤ k.

Clauses:

• For each r, y_1,r∨y_2,r∨…∨y_n,r (some node is the rth node of the clique).
• For each i, r<s, ¬y_i,r∨¬y_i,s (no node is both the rth and sth node of the clique).
• For each r≠s and i<j such that (i,j) is not an edge of G, ¬y_i,r∨¬y_j,s. (If there's no edge from i to j then nodes i and j cannot both be in the clique).

That's the entire formula that will be satisfiable if and only if G has a clique of size k.

While simple, an optimized Cook-Levin style reduction can produce smaller formula for large k. This reduction has Θ(n²k²) clauses. Using Robson's reduction one can create formulas of size O(n²log^O(1)n).

We can get similarly nice reductions for many other NP-complete problems like 3-COLORING and HAMILTONIAN CYCLE. But there is no general procedure for producing simple formula, especially if there are calculations involved like SUBSET SUM.

Save the Mathlete, Save the World

An Off-Broadway tale of beauty and the geeks.

Vickie Martin is über-popular. She's also wicked smart. Victoria Martin: Math Team Queen demonstrates that chaos theory rules when the third most popular sophomore is roped into joining the all-male, all-nerd Longwood High School math team, upsetting the axis of symmetry of boys becoming men. Will Vickie Martin invert the curve or become the coefficient for her team winning the state math championship? Can this goddess of π possibly become the common denominator that makes the mathletes victorious? Totally.

The Efficient Church-Turing Thesis

The Church-Turing thesis roughly states that everything computable is computable by a Turing machine. I strongly believe the Church-Turing thesis and have vigorously defended the thesis in this weblog.

Sometimes we hear about an efficient or strong version of the thesis, for example in the Bernstein-Vazirani paper Quantum Complexity Theory.

Just as the theory of computability has its foundations in the Church-Turing thesis, computational complexity theory rests upon a modern strengthening of this thesis, which asserts that any "reasonable" model of computation can be efficiently simulated on a probabilistic Turing machine (an efficient simulation is one whose running time is bounded by some polynomial in the running time of the simulated machine). Here, we take reasonable to mean in principle physically realizable.

You mostly hear about the thesis from the quantum computing folks as they use the thesis to justify why quantum computing changes everything we believe about efficient computation. But did anyone actually state such a strong version of the Church-Turing thesis before quantum computing came along? The closest I can find comes from Steve Cook's 1982 Turing Award Lecture.

The identification of P of with the tractable (or feasible) problem has been generally accepted in the field since the early 1970's…The most notable practical algorithm that has an exponential worst-case running time is the simplex algorithm for linear programming…but it is important to note that Khachyian showed that linear programming is in P using another algorithm. Thus, our general thesis, that P equals the feasible problems, is not violated.

But not even Cook in 1982 seemed to believe that P captured all the "physically realizable" efficient algorithms as he goes on to describe probabilistic and parallel algorithms.

By no means does computational complexity "rest upon" a strong Church-Turing thesis. The goals of computational complexity is to consider different notions of efficient computation and compare the relative strengths of these models. Quantum computing does not break the computational complexity paradigm but rather fits nicely within it.

Having said all that, as of today the strong version of the Church-Thesis as described by Bernstein and Vazirani seems true as we are not even close to physically-realizable quantum computers. We don't even need "probabilistic" since we believe we have strong pseudorandom generators. Maybe someday we will build those quantum machines or create other physical devices that will efficiently compute problems beyond polynomial time. But we are not there yet.

Shifting Time

At a community concert last Sunday the host said he was pleased with the attendance given the competition with the Bears game. He also said someone had instructed him not to reveal the score. Why not? Because some people in the audience were saving the game and would want to watch it after the concert.

I flew during the last game of the World Series. After we landed I checked the final score on my mobile phone (cool enough that I can do that) and told it to the St. Louis fan sitting across to me. But the person behind me got upset since he was planning to watch the game later.

In my youth you had to watch a sporting event live or you couldn't watch it a all. Everyone watched TV shows at the same time. We even all saw movies at roughly the same time, if you missed a movie in the theater the few weeks it played you would have to wait years until it played in a retrospective or came to TV. You could safely have a discussion about the latest game, TV show or movie knowing that everyone had either seen it or won't get the chance to.

Technology has changed the notion of time itself. Events, particularly entertainment, don't happen at the same time for everyone. They just have an earliest time. Events happen when we want, or have time, for them to happen. This freedom of time makes life more convenient but harder to talk about events that have occurred for some people and not others. Even email causes time shifting. How often have we tried to talk to someone who can't because he "hasn't read that email yet."

The local cable company taped the concert for later broadcast. People could have watched the football game when it happened and the concert later. Their choice.

On Paper Titles

How do you take a twenty page research paper and condense its essence into a few words? A couple of title don'ts with some (made up) examples.

• Starting a title with "On", "Towards", "New" or "Improved" or ending with "?"

  You are announcing that you have failed to solve the problem you really care about and this is the best you can do. Nobody would title a paper proving P≠NP "On an Open Problem of Cook".

• "Breaking the … Barrier"

  Either it wasn't a barrier after all or you cheated and changed the model.

• Cutesy Titles

"A slice of π"

• Ending with a Roman Numeral

  "Pig Complexity I". Does the world need more than one paper on pig complexity?

• Out of Context Titles

  "Three rounds suffice"

• Technical Terms

  Don't use highly technical terms or complexity classes in the title. Any computer scientist should at least understand the words in the title.

• Formal Statement of Result

  "A O(n^3/2log n log log n/log^* n)-time one-sided randomized algorithm giving a O(n^1/3/(log n)^4/3) approximation to 12-sided 3-way 20-dimensional hypergraph coloring."

• Long Titles

  Ditto.

What makes a good title? Short and to the point. Some of several titles I liked from the last FOCS: "Cryptography from Anonymity", "Fault-Tolerant Distributed Computing in Full-Information Networks", "Planar Point Location in Sublogarithmic Time". Enough to give you the idea of the paper and the desire to read more.

I went through my bibtex file trying to find great papers with lousy titles. Except for a few "On"s (On computable numbers, with an application to the Entscheidungsproblem), great papers seem to have at least reasonable titles. A lesson for all of us paper titlers.

My International Day

Friday morning I IM'd a co-author in India, in the evening I Skyped to Hong Kong. A Dutch professor emailed me about a paper we have with co-authors in Russia and the Czech republic. A New Zealand professor asks me a complexity question. On the train ride home I worked on a paper with Portuguese co-authors.

What amazes me is not just the international connections but that I usually don't even realize when I deal with someone overseas. Academic research has gone truly global, where I can call, instant message, email and send papers to colleagues across oceans as quickly and easily as across campus. And as we get more used to this technology the smaller the world becomes and at some point we stop connecting people to countries but rather to points on the internet.

On the other hand these colleagues didn't get to share my experience with Chicago's first blizzard of the season. Too bad I couldn't IM the snow to India.

The Social Scientist

Last month Yisroel Brumer wrote a Newsweek My Turn column Let's Not Crowd Me, I'm Only a Scientist. Brumer talks about how he has become a "social superstar" since taking on a job at Homeland Security's Science and Technology Directorate.

It wasn't always this way. Just a few years ago, I was a graduate student in chemical physics, working on obscure problems involving terms like quantum mechanics, supercooled liquids and statistical thermodynamics. The work I was doing was fascinating, and I could have explained the basic concepts with ease. Sure, people would sometimes ask about my work in the same way they say "How are you?" when you pass them in the hall, but no one, other than the occasional fellow scientist, would actually want to know. No one wanted to hear about a boring old scientist doing boring old science.

People want to hear only about how there's now a cell phone that plays iTunes, or maybe about cool communications that will facilitate emergency responses. But think about all the science that goes into making a cell phone work. Someone had to figure out the equations of electromagnetic waves, circuitry and myriad other scientific details. People have to figure all that stuff out, people who could have made more money and garnered greater prestige had they applied their skills in fields like patent law, business or medicine.

I sympathize with the old Brumer. Even among academics, I remember the political scientist who had the great opening line "My business is war, and business is good", or even my friend the food scientist who did his doctorate on starch. Much as I get excited about the P versus NP problem and its great importance to all science and society, trying to express these ideas to uninterested laypeople always seems to end up with "Should I buy an Apple or a Windows machine?"

The Campers and the Bread

Marilyn vos Savant writes a weekly column for Parade Magazine instered into many US papers. She's best known in the math community for the popularization of the Monty Hall Problem. Here is a question from her November 19th column (names added).

Carol get lost in the woods, where she ran into two campers, Alice and Bob, who also were lost. Alice had three loaves of bread and Bob had two loaves. They all agreed to share the bread equally. Carol was so grateful that, when they found their way back to town, she gave the campers $10,000 for saving her life. Alice said she should get $6,000 because she contributed 3/5 of the bread. Bob said that all had eaten an equal amount so the campers should split the reward. To settle the argument they visited the local wise man, a retired math teacher. Which camper was right?

Think about the problem. Here is my short version of Marilyn's answer.

Neither. Carol paid $10,000 for 5/3 loaves or $6000 per loaf. So Alice gets $8,000 for her 4/3 loaves she gave up and Bob gets $2,000 for his 1/3 of a loaf.

This solution makes sense mathematically but not economically. Suppose Alice and Bob were poor graduate students. Bob would be willing to eat less bread and undercut the price of Alice's bread. To make this point clearer suppose originally Alice had four loaves and Bob only one. Then by the logic above, not only does Alice get all of Carol's $10,000 but also $4,000 more from Bob for the 2/3 of a loaf he gets from Alice.

To do the correct math one would have to know the exact utility functions of Alice, Bob and Carol, or set up an appropriate auction when distributing the bread. But since the money is split after the sharing has been done, Alice and Bob should just take $5,000 each and be happy with it.

Electronic vs Physical Program Committees

I have served on program committees that have entirely electronic discussions and others that meet in person. What works better?

Logistically physical meetings have several disadvantages.

• Must somehow cover travel costs of participants. Often this comes out of the conference budget, raising registration rates.
• Since traveling overseas is difficult just for a committee meeting, physical PCs have less international participation.
• Invariably some PC member misses the meeting and has substantially less influence on the choices.

On the other hand I have heard that a physical PC meeting rewards the PC members but allowing them to spend time together and enjoy a fine meal.

The dynamics of physical and electronic meetings differ. Both start by quickly accepting the strongest papers and rejecting the weakest. In a physical meeting the remaining papers get discussed serially. There is a tendency to accept more often at the beginning, realizing you accept too much and start being more stringent and bouncing back the other way towards the end. One also spends too much time talking about the first set of papers, leading to rushed discussions later on.

In an electronic meeting the discussion on all papers happens in parallel. When discussion seems to go a certain way, the PC chair will suggest acceptance and rejection and sees if someone objects. A vote is taken for a few contentious papers. But many papers have nobody who loves or hates them. For those the PC chair has tremendous power for no one will object to whatever they recommend.

Both types of PCs suffer from groupthink, a tendency for groups to reinforce viewpoints. A PC chair also has to make sure that everyone participates in the discussions.

My preference goes for a third approach that I have seen used in a few conferences. The PC members send their reviews to the PC chair who, after some emails for clarifications, makes all the final decisions by him or herself. Simple and, with a good PC chair, works surprisingly well.

Victims of the Digital Age

During my Thanksgiving trip two store closings caught my eye.

• The Tower Records just near Lincoln Center in New York has a going out of business sale. I used to kill time there before going to a concert or an opera. In fact all the Tower Records are closing down.
• The small Millburn Camera Shop in New Jersey is no longer.

Both of these stores just couldn't keep up with the world of the Internet. Tower Records made their mark by having an amazing collection, one of the best collection of classical in the country in their Lincoln Center store. But their collection cannot compete with online stores like Amazon, Walmart beats them in price on the popular CDs, not to mention the convenience of music downloads, both legal and illegal.

The Millburn Camera Shop supported the amateur photographer with products, advice and specialized film developing and printing services. In high school I set up a darkroom in my basement with equipment from the store and bought my Black and White film in bulk from them. But as today's amateurs now have mostly gone digital, software replaces most of the equipment and developing. Bulk film comes in the form of a tiny media card. And so the friendly neighborhood camera shop disappears.

It has become much easier to access music and to take and process pictures than it ever has in the past. But I will miss the days of browsing music and developing pictures.

An administrative note: Because of a recent large increase in comment spam I now use CAPTCHA-type tests to leave comments. Sorry for the inconvenience.

Happy Thanksgiving!

As happens every year I am off to visit my parents for Thanksgiving.

For my fellow Americans, enjoy your Thanksgiving. For the rest of you enjoy the remainder of the week.

Microfiche

A graduate student complained that Indiana University requires him to pay $60 to make a microfiche copy of his Ph.D. dissertation.

Many universities have various hidden fees they charge you just as you are about to graduate. Usually these fees total in the $100 range, low enough so that you just cough up and pay them as $100 doesn't mean too much in the grand scheme of life. Still there should be some warning, perhaps in the admissions letter.

Be aware that after you have fulfilled all the requirements, written and successfully defended your thesis, you will not receive a Ph.D. until you have also paid the following fees…

But why Microfiche? Wouldn't an electronic copy of the thesis make more sense. Several universities require a bound paper copy, partly for tradition and part just in case the PDF files of today cannot be read by next century's computers. I doubt the last part—there are too many PDFs around today for us not to have a way to look at them in the future.

I was a microfiche wizard in high school. When I did reports on 20th century history, I would go back to the original New York Times articles to get a first hand perspective. But with the Internet and back articles available electronically, microfiche is an aging technology. In the past decade I've used microfiche exactly once—to track down a box score of a baseball game I went to long ago.

I suspect microfiche will go the way of sliderules and typewriters. Before they die, someone (Google?) will scan in the old microfiche and covert them to PDFs. Wouldn't it be better for the Indiana University library to get a free high-quality PDF now instead of an expensive scanned PDF in the future?

Since We Can't All Win Turing Awards

In 1993 ACM created their Fellows program

To recognize and honor outstanding ACM members for their achievements in computer science and information technology and for their significant contributions to the mission of the ACM. The ACM Fellows serve as distinguished colleagues to whom the ACM and its members look for guidance and leadership as the world of information technology evolves.

Since then over 500 fellows have been named including several theoretical computer scientists.

Last year ACM decided that they needed more grades and recently announced their first class of senior members and distinguished engineers, scientists and members. Only a couple of theorists made these lists.

Becoming an ACM Fellow or Distinguished Scientist doesn't make you a better researcher but it does give you a little more clout in the broader CS community. Also having large numbers of Fellows and Distinguished Scientists makes the theory community seem stronger as a whole. So if you know of someone worthy (and eligible) for Distinction or Fellow, go ahead and nominate them and help give your fellow scientists and the theory community the recognition they deserve.

Favorite Theorems: Nonuniform Complexity

October Edition

The class P/poly is the set of languages that have polynomial-size circuit families, i.e., L is in P/poly if there is a k, a sequence of Boolean circuits C₀, C₁, … where C_n has n inputs and at most n^k gates, such that and all x=x₁x₂…x_n,

x is in L iff C_n(x₁,x₂,…,x_n)=1. This is a nonuniform model of computation, C₂₇ may have no relation whatsoever to C₂₈.

Suppose NP is in P/poly and has a (non-uniform) circuit family that accepts it. Karp and Lipton show that NP in P/poly implies collapses in uniform models of computation as well.

Richard Karp and Richard Lipton, Some connections between nonuniform and uniform complexity classes, STOC 1980.

The main result shows that if NP is in P/poly then the polynomial hierarchy collapses to the second level, giving us evidence that NP is not in P/poly and hope that we can prove P≠NP by showing superpolynomial lower bounds on the circuit computing some NP problem.

The paper also gives a general (though controversial) definition of advice and a collapse of EXP to Σ₂^p∩Π₂^p if EXP is in P/poly (credited to Meyer), and similar results for PSPACE and the Permanent.

Kannan uses Karp-Lipton to show that some language in Σ₂^p∩Π₂^p does not have linear-size circuits, or more generally for every k, there is a language L_k in Σ₂^p∩Π₂^p that cannot be computed by nonuniform n^k-size circuits.

Later extensions to Karp-Lipton:

1. If NP in P/poly then the polynomial-time hierarchy collapses to S₂^P ⊆ ZPP^NP ⊆ Σ₂^p∩Π₂^p. (see Cai and Köbler-Watanabe)
2. If EXP, PSPACE or the Permanent is in P/poly then EXP, PSPACE or the Permanent is in MA ⊆ S₂^P respectively. (see Babai-Fortnow-Lund)
3. If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)

Using Kannan's proof, (1) implies that S₂^P does not have n^k-size circuit for any fixed k. Can one improve (1) to show that if NP in P/poly then the polynomial-time hierarchy collapses to MA? This would imply MA does not have n^k-size circuits for any fixed k.

The Future of Science

New Scientist celebrates their 50 years by asking about 70 "Brilliant Minds" to forecast the next 50 years of science. Several researchers (all well-known though a few overrated) talk about math and computing including Tim Gowers focusing on the P versus NP problem.

This problem gets to the heart of mathematics, because mathematical research itself has the property I have described: it seems to be easier to check that a proof is correct than to discover it in the first place. Therefore, if we found a solution to the P = NP problem it would profoundly affect our understanding of mathematics, and would rank alongside the famous undecidability results of Kurt Gödel and Alan Turing.

Thanks to Chris Masse for the pointer.

Pepsi Math

I bought a Diet Pepsi yesterday and the label described a bottle top promotion: One in six wins "Buy One Get One Free". Suppose you drink a large amount of Diet Pepsi, what is your asymptotic expected discount?

If you buy six bottles then you expect to have one winning bottle top enabling you to get the next two bottles for the price of one, or eight bottles total for the price of seven. But bottles seven and eight have bottle tops too which may be winners. One can continue this process and take the limit but is there a simpler argument?

Soda bottles are interchangeable, a free soda in the future can be exchanged for your current soda. So you can assume that when you get the "Buy One Get One Free" bottle top, your current soda is free. That means you get one free soda from every six, a discount of 16 2/3%.

You get the same discount if the bottle top said "Buy Two Get One Free" or simply "Get One Free". But if the bottle top said "50% off next purchase" which seems equivalent to the original promotion, the discount is only 8 1/3%.

Key References

Carlos Castillo asks for comments on his Key References Proposal.

The key references section of a paper points to the most similar previous articles on the same topic that were extended, improved, challenged, or built upon by the paper. Key references allow the author of a research article to highlight the most closely related previous work in the specific topic of the paper. Key references are the natural complement of keywords.

An interesting idea. If it is used (and taken seriously) by many authors it might help automated search systems identify important papers in the field.

On the other hand many journals require keywords and AMS classifications although I have rarely seen this information put to good use. For humans a well-written "Previous Work" section will have much greater value than just a list of references.

Key References won't become popular unless a major publisher requires them in their journal or conference articles. Would Key References play a useful role or just become one more thing authors have to do to get their papers published?

Puzzles That Keep You Awake at Night

Dartmouth Professor Peter Winkler visited our department yesterday and today, the first stop of a two-week five-university tour. Winkler gives great seminar talks and is easy to talk to about hard combinatorial problems. Unfortunately whenever I see him he also brings very tantalizing puzzles that you have to work hard at not thinking about, lest they consume you. For example Love in Kleptopia

Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands?

From Seven Puzzles You Think You Must Not Have Heard Correctly (with solutions). For the more mathematically minded here is the Infinite Hats Problem that he told me earlier this year.

A countable number of people each have either a white hat or black hat on their heads. Each person can see everyone's hats except their own. Each person simultaneously announces a guess for the color of their hat. Is there a strategy for the people so that no matter what the arrangement of hats, only a finite number will incorrectly guess their hat color?

For more check out his book Mathematical Puzzles: A Connoisseur's Collection.

Virtual Academics

The Chicago Tribune today had a few articles on Second Life, a growing virtual world that even has its own economic markets with its own currency exchangable with US dollars. As the article says, Harvard Law School taught a class in Second Life and I have heard of many other universities in the process of establishing Second Life courses as part of their on-line degrees. Taken to an extreme, why do we need hundreds of graduate complexity courses taught world-wide every year when everyone can sit in on one of a handful of the best lecturers giving the class?

Indeed we now have the technology to have virtual seminars or even entire conferences on-line complete with "coffee breaks", business meetings and dance parties. Why not even hold an established conference, like STOC or SODA in a virtual world? The total cost would be much less than traveling to a real-world meeting and nearly every aspect of the conference experience could be simulated.

One advantage of a real-world conference is not so much what one can do but what a real-world conference prevents you from doing. While away at STOC you can't teach your course, attend committee meetings, hold office hours, meet with students, etc. You are forced by circumstance to reschedule these activities and open up your calendar to see talks and meet with your colleagues. But at a virtual meeting, can you tell your chair you have to miss your class and the faculty meeting while you sit at your computer, your body in your office but your mind in a different place?

Math-Love Songs

Guest Post from Weblog VJ Bill Gasarch

These aren't songs about loving math, these are love songs that use math as a way to express love. There are three that I know of (if you know more let me know). I'm not counting THEORY GIRL which is more of a Comp Sci song.

1. The one that inspired this post:

   A finite simple group of order two by The Klein Four.

   Lyrics are great!
   Math is actually HARD!
   Singing quality–they shouldn't quit their day jobs.
   Video Quality–they just stand around singing.
   (Actually they are grad students so its not clear they have day jobs.)

2. The Mathematics of Love

   From SQUARE ONE TV, an old PBS show about math (in a low level) that had some nice satires and songs in it. I watched it when I was younger (when I was 30 actually)
   Lyrics are nice!
   Math is easy.
   Singing quality is pretty good.
   Video quality–very good for content and quality.
   I think this IS their day job.

3. 8 percent of my love

   Also from Square One.
   Lyrics are great!
   Math is easy.
   Singing quality is pretty good.
   Video quality–very good for content, but quality is fuzzy. (I've got a better quality video of this in my collection.)
   I think this IS their day job.

Finding Academic Jobs

An anonymous student writes

I am applying for academic jobs this year. How does one come to know about them? Basically the only source I know is the CRA website. DMANET mailing list is also helpful. [And then there is word of mouth—but that seems to favor a privileged few.]

I think the way CRA puts ads on its website could be improved a lot. Right now every university puts its ad in unstructured text. Now if I want to know which university has what deadlines I have to manually sift through their ads and the deadline could be anywhere in the text (if it's there at all). Similarly, there are many other attributes that one might want to use as search criteria: such as type of position being advertised, do they need material in hard copy, or in email, or does one need to fill a web form. I think if this were there it'd save some time.

But I think one could go further; though I understand it's probably rather hard to implement what I am going to suggest for all sorts of reasons. Why not make the whole process centralized. At present one has to fill up the forms on the web for many universities which can be really painful. And then sometimes they ask the letter writers to also fill a form. Hard copies or emails are not much better either. What if there were a centralized trusted server where one applicants could submit their information along with the universities where they wanted to apply? And then their application would be delivered to those universities. This would save a lot of pain for everyone.

Most CS departments list their faculty positions in the CRA News and CACM and many job positions also get distributed over the DMANET and THEORYNT mailing lists. Also check out the departmental home pages of any university where you might have interest. Even if there is no ad you can apply to any department by sending an email to the chair with the usual supporting material (CV, research statement, teaching statement and list of references), though if the department's web page has specific instructions better to follow those. Get all your applications submitted by December 31 no matter how late the stated deadline.

Don't limit yourself to departments specifically mentioning theory as they will sometimes hire in theory once they fail to find suitable candidates in other areas. You might also consider positions overseas, while professor positions are difficult to find in most countries, there are more postdoc opportunities outside the US. Also consider a broad range of universities in the US, they might have a higher teaching load but you can still have a successful research career.

Make sure your own home page (pointed to on your CV) has on-line versions of all your papers, contact information, CV and the rest of your supporting material.

A standardized database for recruiting would make life easier for all involved but don't hold your breath.

Prediction Map Post Mortem

As I've mentioned before, David Pennock, Yiling Chen and I developed a map predicting the 2006 Senate races based on market prices from tradesports.com. So how did those predictions go? In short you can say the markets predicted every individual race correctly but got the senate wrong, but let us look a little more carefully.

At about 9 AM CST on the morning of election day I made a snap shot of the map for a Discovery Channel Website article.

Every state colored blue was won by a democrat and every state colored red went to a republican. But also note the 69% given to GOP (Republican) Senate control although this election will give control to the democrats. No outcome would have made all the states and senate control agree with the 9 AM map.

Were the markets inconsistent? No, because the markets predict not absolutely but probabilistically. For example, the markets gave a probability of winning 60% for each of Virginia and Missouri and the democrats needed both to take the senate. If these races were independent events, the probability that the democrats take both is 36% or a 64% chance of GOP senate control assuming no other surprises.

Of course the races were not independent events and there are other states involved making it more difficult to compare the probabilities of the individual races with that of senate control.

So how did the markets do as predictors? Quite well as the outcome seems quite reasonable given the markets. Other outcomes would have also been reasonable such as the Democrats losing Virginia and the senate remaining in republican hands, a possibility that came very close to happening.

We plan a map with a better design and more features for the 2008 Electoral College and Senate races. Stay tuned.

Podcast Q&A

For the next Complexitycast, Bill Gasarch and I will attempt to answer reader's questions. We will pick the best questions and answer them in the next podcast.

You can either email me your question on any topic related to this weblog or better yet record yourself asking the question (in either MP3, WAV or OGG) and send me the audio file.

Think of good questions for if we don't get many we'll make up our own.

PIR Update

A guest post from Bill Gasarch.

There have been two important NEW results in the field of Private Information Retrieval so its worth reviewing the field and the new results (Some background here).

This post is about Information-Theoretic Private Information Retrieval. We state the problem and five results in order of discovery, with the last two being the recent ones.

PROBLEM: A database is an n-bit string (my wife tells me that databases are more complicated than that). The USER wants to know the ith bit but does not want the DB to have ANY CLUE of which bit he wanted.

EASY ANSWER: Request the ENTIRE DB. That is n bits.
QUESTION: Can we do this with substantially fewer than n bits?
ANSWER: NO if there is only one copy of the database.
NEW QUESTION: What if there are k copies of the DB?

1. 2 DBs, O(n^1/3) bits; for k≥ 4, k DBs O(n^1/k)
   Private Information Retrieval, Chor, Kushilevitz, Goldreich, Sudan, JACM-1998, (Earlier version FOCS 95)

   NOTE: Introduced the field. Journal version has easy constructions. Conference version had slightly harder poly-interpolation constructions material that are a prelude to item (3) below.
   NOTE: FOCS version has O(n^1/k) result, Journal omits it since item 2 below had already appeared.
   NOTE3: k=3 gives O(n^1/3)—can't use that its 3 DB's instead of 2.

2. k DB's, O(n^1/(2k-1))
   Upper Bound on the Communication Complexity of Private Information Retrieval Ambainis, ICALP97,

   NOTE: Used Recursion. Constant is exponential. Later papers that reduced the constant to polynomial lead the way to the next paper.
   NOTE3: k=3 gives O(n^1/5).

3. k DB's, n^{O(loglog k/(k log k))}
   Breaking the O(n^1/(2k-1)) barrier for information-theoretic Private Information Retrieval Beimel, Ishai, Kushilevitz, Raymond. FOCS 02.
   NOTE: Brilliant use of polynomials.
   NOTE3: Techniques yield k=3, O(n^1/5.25)
   

4. 2 DB Ω(n^1/3) LOWER BOUND
   An Ω(n^1/3) lower bound for bilinear group based Private Information Retrieval Razborov, Yekhanin, FOCS 2006.

   NOTE: Hard paper! Modeled 2-DB-Private Information Retrieval via Latin Squares and then used representation theory of finite groups to push through the lower bound. ALL current 2-DB protocols fit the model, so lower bound is either legitimate or will point way to other techniques. My money is on legit. Even so, there aren't that many 2-DB protocols so who knows…

5. 3 DB O(n^1/32,586,658) PIR! Really!
   New Locally Decodable Codes and Private Information Retrieval Schemes, Sergey Yekhanin

   NOTE: Wins award for largest distance between GREATNESS of content and AWFULNESS of title. I would have called it

   A 3 DB O(n^1/32,586,658) PIR! Really!

   NOTE: Uses Mersenne primes. The number used is based on the largest Mersenne prime known, which is 2^32,586,658-1. If there are infinitely many Mersenne primes then, for infinite number of n, get k=3, n^{1/loglog n}-Private Information Retrieval
   NOTE: Vast improvement on k=3, n^1/5.25
   

In the constructions in items (2) and (3) above the k-DB PIR was constructed recursively out of k'-DB PIR's for k'<k. Hence this massive improvement for 3-DB PIRs leads to improvements for these schemes.
PIR scheme (2): the new 3-DB PIR leads to a k-DB, O(n^1/(bk-1)) where b is enormous.
PIR scheme (3): the new 3-DB PIR leads to the same asymptotic k-DB n^{O(loglog k/(k log k)} but with a much smaller constant in the O-of term.

Time Zones

For the first 18 years of my life I never left the Eastern time zone. Everyone I knew including all my relatives lived on the US East coast. I never had to do time conversions.

But now as an academic living in Chicago I always need to worry about time zones when I coordinate a phone or IM meeting or have a paper deadline. You end up remembering some key rules: One hour to the East Coast, seven hours to Continental Europe except for Portugal which is six hours like London, eight hours to Israel. I always have to remind myself that California is minus two hours not minus three. And of course there is India, currently eleven and a half hours ahead of Chicago. Time zones are relative—your time differences will vary.

Daylight Savings Time adds to the confusion. Europe and Israel have similar time changes but not always changing on the same weekends. India and China don't change their clocks and Down Under they change in the other direction. Savings time also mean extra thinking when converting from UTC time.

Until recently Indiana didn't do savings time but since time zones are relative, it seemed that Indiana changed from Chicago time in the summer to New York time in the winter. Now Indiana follows daylight savings time so most of the state is in New York time year round. I managed to forget the change when visiting South Bend this summer and ended up an hour late to everything.

Technology helps. You don't need to know the time zone when you send email. I used to use the World Clock to keep track of times in other places but now I use the nifty Time in City feature built into Yahoo! Search.

Sometimes time zones can work to your advantage. If you are close to deadline on a paper with a co-author in a far-away land you can each work on the paper while the other one sleeps. This strategy never worked with my most frequent co-author Harry Buhrman in Amsterdam. I am an early riser and he sleeps late so we keep the same hours, seven hours apart.

Fifteen Seconds

The University of Chicago wrote a press release about the prediction market maps for the Senate and Governor races that I created with Yahoo!'s David Pennock and Yiling Chen. The press release led to short articles on the New Scientist and Scientific American web sites and a handful of other blogs. Although even with the nice virtual ink, there was never a day more people looked at the maps than at this weblog.

What about the elections? No senate race in Illinois but a governor's race where I have yet to find anyone who likes either candidate. We do have two good candidates in my congressional district, but what difference does it make as which party has control of the house is much more important than the views of the particular candidate we send there.

The Illinois politician garnishing the biggest praise is not even running this year, our junior senator and future president.

A Thesis to Forget

It is rumored that a graduate student once wrote a whole thesis on the set of functions mapping reals to reals such that for some fixed c and α>1, |f(x)-f(y)| ≤ c|x-y|^α for all reals x and y.

A committee member then asked what happens when you compute the derivative of f.

[From The Way of Analysis by Robert Strichartz]

FCRC Deadlines

The 2007 Federated Computing Research Conference will bring together a large number computer science conferences for one meeting June 8-16 in San Diego. Here is a run down of the FCRC theory-related conferences with submission deadlines and links to their call-for-papers.

• STOC, November 20. Undergraduate Research Competition, February 23.
• EC (Electronic Commerce), Abstracts, November 30. Full Papers, December 7. Tutorial and Workshop Proposals, January 5.
• Computational Complexity, December 3.
• SPAA (Parallel Algorithms and Architectures), December 18. Brief Annoucements, January 8.
• COLT (Learning Theory), January 16. Open Problems, February 15.

Meanwhile not at FCRC

• Computational Geometry, Titles and Abstracts, November 22. Papers, December 4. Video, February 15. Conference, June 6-8 in South Korea.
• TARK (Rationality and Knowledge), January 30. Conference, June 20-22 in Belgium.
• ICALP, January 25. Workshop Proposals, November 30. Conference, July 9-13 in Poland.
• LICS (Logic in CS), Titles and Abstracts, January 15. Papers, January 22. Conference co-located with ICALP, July 10-14 in Poland.

Algorithms and Networks in The Times

Steve Lohr wrote a New York Times essay on the CSTB 2016 Symposium held earlier this month. Lohr highlights the presentations of Richard Karp on the Algorithmic Nature of Scientific Theories and Jon Kleinberg on Social Networks, both of whom gave similar presentations at FOCS.

Network Neutrality

Some members of our community have worked on network protocols that use economic mechanisms to distribute bandwidth throughout the network. Would this research violate the concept of network neutrality? That depends on what you mean by network neutrality.

The Internet pioneer Tim Berners-Lee writes

It is of the utmost importance that, if I connect to the Internet, and you connect to the Internet, that we can then run any Internet application we want, without discrimination as to who we are or what we are doing. We pay for connection to the Net as though it were a cloud which magically delivers our packets. We may pay for a higher or a lower quality of service. We may pay for a service which has the characteristics of being good for video, or quality audio. But we each pay to connect to the Net, but no one can pay for exclusive access to me.

So an ISP like Comcast could accept money from say Disney to distribute their bits faster as long as they make the same deal available to all other content providers.

Some people take a more stringent view like the (failed) Markey Amendment to the COPE Act.

Each network provider has the duty to operate its broadband network in a non-discriminatory manner so that any person can offer or provide content, applications, and services through, or over, such broadband network with equivalent or better capability than the provider tends to itself or affiliated parties, and without the imposition of a charge for such nondiscriminatory network operation.

The amendment would have required ISPs to provide the same service to all content providers without additional charge. This might prevent any market mechanism for bandwidth distribution.

Our role as theorists is not to debate the ethical issues of network neutrality but rather to help frame the debate by understanding the technical issues raised by the various definitions of network neutrality and how these rules can affect the overall efficiency of routing bits through the net.

The Generalist

As you readers know, my colleague Janos Simon went to FOCS last week. Janos wasn't an author, he wasn't on the program or organizing committees, he wasn't an invited speaker, he didn't sing in the band and he doesn't live within driving distance of Berkeley. Janos Simon went to FOCS not because he had an official reason, but rather to keep up with the latest results in theory. FOCS had low attendance this year (about 220) because it doesn't attract many Janos Simons, people who travel to FOCS because they want to, not because they feel they have to.

Janos Simon is part of a dying breed, a generalist in theoretical computer science. Janos goes to most STOC and FOCS conference and few specialized conferences like SODA and Complexity. In three decades of research, Janos has studied complexity, algorithms (distributed, parallel, randomized), VLSI and networks well as having interests in nearly every area of theory. It's impossible to arrange parallel sessions at FOCS in way that won't cause a conflict for Janos.

Back in the 70's a graduate student could keep up with the latest research in all of TCS and produce significant results in his or her career in many different areas. Today we seem to push out very specialized researchers focused not just on some subarea like algorithms or complexity but even in more specialized areas like streaming algorithms or PCPs.

Such specialization has its risks, for example getting so caught up in an area that you lose track of the motivation for studying the topic in the first place. Also we lose some sense of community when theorists in different areas lose interest in following each others work. But can a young Janos Simon survive today as a generalist or are we doomed to further specialization as students search for successful research agendas?

Whose Thesis is it Anyway?

Ten years ago Bob Soare realized that the name "recursion theory" did not do justice to his field so he single-handedly changed the name of the field to Computability theory. Now he wants to correct the early history of computability and credit to whom credit is due, naming Turing.

The canonical wisdom in most computability textbooks is that there were several researchers in the early 1930's working on various formal definitions to capture the intuitive notion of a computable function, and that Turing was just one of them and shares the credit with them. This is incorrect. It was Turing and Turing alone not Church, not Kleene, not Post, and not even Gödel himself. It was Turing who:

1. gave the first convincing model for an intuitively computable function;
2. gave a precise demonstration that this formal model captured the intuitive notion; and
3. defined the universal Turing machine, which is of immense importance.

You can see Soare's historical view here.

Yesterday Soare gave a preview of a talk at the Chicago logic seminar. He focused mostly on the work of the 30's and how Kleene later established the terminology Recursion Theory and Church's Thesis. Soare argues that Turing deserves most of the credit for the Thesis because Turing gave solid arguments for the thesis and Gödel always gave Turing credit. Church may have first formulated the thesis but Turing's work made it credible.

We computer scientists have been using "Church-Turing Thesis" for years and with Soare's historical background, Church-Turing still seems like the way to go.

Introductory CS Sequences

At most universities the first year CS courses tend to cover programming. These courses differ from first-year sequences in other departments in several important ways.

In most disciplines, the topics of the introductory sequence have not significantly changed since I went to college and even since my father went to school. In CS our introductory courses seem to change every few years. I don't think anyone currently teaches PL/C (or any other PL/1-variant) that I learned in CS 101 at Cornell. Computer Science didn't even exist as a field when my father when to college in the 50's.

In most disciplines any professor in the department deeply knows the material taught in the introductory sequence. Any professor could teach the intro sequence, or if they can't it's not because they don't know the material. This is certainly not true in computer science.

A professor at a state university noted that their CS majors had internships after their first year and commented "CS is the only discipline where we have to make the students employable after the first year."

In non-CS scientific disciplines, different universities generally teach the same material to their first-year students. Different physics departments teach with different books at different levels and maybe material in different orders but there is general agreement of what basic concepts of physics that first year students should know.

Go to any computer science conference and you'll hear discussion about what programming language gets taught at their schools. Nearly every department has people disagreeing about which programming language to teach to the first years. I tend to stay out of these fights for it is a lose-lose proposition. Win the argument and you'll end up teaching the class.

FOCS Funding, Music and Talks

Another Janos Simon report from the FOCS conference in Berkeley.

News from yesterday's Business Meeting (continued). Most of the news from NSF is a repeat of last years sorry state of affairs: no money, not enough influence.

Influence: We (TCS) are a lowly leaf, instead of a child of the root in the CS organizational tree. This is both bad for money, and very bad for influence and image. Bill Steiger is working hard for a change.

Money: bad news. More precisely, when Bill Steiger got to NSF, all his budget was already spent. (Budget = $4.1 million, plus 2.8, a share of the money for three subprograms). Of the ~500 CS proposals to NSF, about 90-100 were for Theory. Bill managed to fund 18, by hard work, persuading others to let Theory have a bit of their budget, etc. The SING (network) program was also seriously underfunded (~100 proposals, 7 funded, one of these was theory-flavored.)

Perspectives for 2007 are not good. Again, the money is pretty much spent, but Steiger will do the best he can. NSF budget should be within 10% of 2006. About 4-5 CAREER grants might be funded, no large Theory projects will be. SING will again be very competitive.

If you are interested in submitting a proposal do talk to Bill Steiger. He will try to help.

An appeal by Bill Steiger: please send "nuggets" to him—descriptions of neat Theory results. They are VERY useful.

Dick Karp spoke, and thanked Bill in the name of the Theory community. After a round of applause, Karp explained that other science communities lobby for NSF projects: astronomers get observatories, satellites; physicists get accelerators, or focused projects. They have an internal discussion and then lobby lawmakers and NSF. CS, in particular Theory, should do likewise.

He appealed for mobilizing the community. NSF wants CS to suggest visionary activities, and CRA got a few millions to organize us to suggest ideas. Theory should make sure we are well represented.

Avi briefly noted that out of 0.5 billion to CS, Theory gets 6-10 million, yet we are about 20% of the community. We need politics. We should also think of service at NSF as part of our service.

At the end of the meeting, it was announced that Hal Gabow will be the next TC chair.

The final part of the proceedings was moving to the adjacent ballroom where we were treated to a rock concert. Christos Papadimitriou, suitably dressed in all black was the keyboard player, Anna Karlin had one of the electric guitars: the rest of the band (Lady X and The Positive Eigenvalues) was unknown to me. Lady X was Andrea Frome (a Berkeley grad student), and the performances were very good. Eventually Christos also sang. (Luca reviews the concert with pictures.)

MONDAY talks.

There was an invited talk by Terry Senjowski, a distinguished neuroscientist. He talked about how vision is influenced by knowledge and expectations, and how our brains seem to have learning feedback mechanisms, and that simple neural networks can learn surprisingly complicated stuff. I can report more fully if there is interest; he did not make direct connections to Theory.

Again today there were a number of very interesting papers. A cute question from the point location talk: in 2D is nearest neighbor as hard as point location? As usual, clever crypto papers, and quantum results, including one by Xiaoming Sun and Andy Yao with real heavy duty math.

A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that NC²=P^#P—he thinks this would be cleaner than the current complexity zoo. The paper is a continuation of the research direction started with his matchgate computations. He considers "holographic reductions" that conserve number of solutions, not by direct translation as the usual parsimonious reductions do, but in complicated ways: they are many-to-many maps but still conserve counts. Using these, he is able to prove interesting stuff, like counting number of satisfying assignments mod 7 is in P, but 7 may be the only such modulus.

The paper that won the Machtey award is very nice, and Nick Harvey did a superb job of presenting it. He has probabilistic algorithms to find matchings in non-bipartite graphs that achieve time O(n^ω) where ω is the exponent of matrix multiplication. There was another algorithm with the same bound (Mucha and Sankowski, FOCS 2004), but Nick Harvey managed to do what no other general matching algorithm does: it is easy to understand. Read it!

Finally a paper I could not hear, but is interesting if only to show how taste changes. Back in the remote prehistory of CS—around the very early sixties—people were very interested in small universal machines. They wanted to see how simple could objects be and yet have undecidability "built in." More precisely, for what pairs (s,a) is there a universal Turing machine with s states and a tape symbols? (The product sa is the "size" of the machine). The smallest machines were constructed by Minsky, using as a subroutine "tag systems" that are a kind of "Post production systems" that are a kind of type 0 grammar. The simulations introduced an exponential overhead, so these smallest machines were very slow. It has been an open problem for over 40 years whether this exponential slowdown was really necessary. The paper by Woods and Neary shows that this is NOT necessary, and gives a polytime algorithm for all known minimal-size universal Turing machines.

FOCS Day 1 and Business Meeting

Janos Simon continues his reports from Berkeley.

Dick Karp gave a 1-hour invited talk in two parts. First he gave a short version of "Why TCS is important to other sciences." This is a sermon that ought to be delivered to deans, and to non-theory folks in CS.

Highlights:

• TCS points out the computational nature of natural and social processes, and provides a language for their descriptions analogous to Math providing equations that describe phenomena and methods to manipulate equations.
• TCS alters world views in other areas, providing paradigms to understand and to model.

Examples:

• Biology: cell process regulation.
• Learning: (in humans, animals) paradigms, models and algorithms from Computational Learning Theory
• Molecular self-assembly
• Strategic Behavior of companies
• Physics: Quantum Mechanics and quantum computing.
• Math: too numerous to mention, algebra, Fourier techniques, Social sciences: web, data for social interactions and behavior, etc.

Karp also gave examples of where convergence between CS and other areas benefited both disciplines including Belief propagation, error correcting codes and constraint satisfaction.

Janos' Comment: I think it is important to emphasize that CS contributes more than a passive lens: we are not a tool, but a partner.

The second part of Karp's talk was a set of examples from Computational Molecular Biology, illustrating some of the contributions/research accomplishments. He gave 5 examples of "Algorithmic Challenges in Computational Molecular Biology." [Many are associated with Berkeley because Karp is quite familiar with these]

1. Sequencing Genomes. He talked mostly about Myers' contribution to shotgun sequencing. His algorithmic ideas were crucial to the success of the technique, which, against biologists' expectations, became the standard. The technique: extract many random sequences of the genome, of known fixed length, 2, 10, 50, 150 kb pairs. read 500-1000 nucleotides from opposite ends computationally assemble the genome. Myers came up with several tricks the do NOT work for arbitrary sequences, but take into account the domain. Had to use biological knowledge.
2. Parametric Sequence Alignment. The Needleman-Wunsch algorithm (aka dynamic programming) gives best alignment of two sequences (DNA fragments) given scores for matching letters, mismatches, or matching a letter with a space (modeling insertions/deletions). What if these costs are not known? Clever algorithm by Pachter and Strumfels, using polytopes for this parametric problem
3. Inferring Evolutionary History (Daskalakis, Mossel and Roch, STOC 06)
4. Genetic Variation Zhihong Ding, Vladimir Filkov, Dan Gusfield: A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem
5. Regulation of Gene Expression (ran out of time)

Some other interesting talks I heard:

Nguyen, Ong, Vadhan: Statistical zero-knowledge from any 1-way function. Omer Reingold liked this. I did too. They prove that 1-way functions (in some sense the weakest crypto assumption) is sufficient for giving a zero-knowledge proof—under new definitions. The usual one is that soundness is statistical (absolute) and zero-knowledge is computational (guaranteed only about polynomially bounded adversaries). This paper inverts the roles, answering a question proposed in 1992. The proof technique is new.

Assaf Naor presented two difficult and impressive results, showing that problems of embedding one metric space in another have a deep mathematical background, and interesting CS applications. The papers have difficult proofs that may well be worth studying.

Santosh Vempala presented a great result (with Laci Lovasz) showing how sampling log-concave functions is related to optimization problems.

I found the results on derandomization, and hardness amplification quite interesting (section 4B) and was convinced of the virtues of smoothed analysis (concurrent section 4A). Ryan O'Donnell gave a beautiful presentation of new nonapproxability results in session 5A, and I learned that honest majority is easier in a quantum setting in session 5B.

Highlights of the business meeting:

Machtey Award for Best Student Paper: Nicholas J. A. Harvey for Algebraic Structures and Algorithms for Matching and Matroid Problems.

Stats: 243 submissions, 71 accepted (~30%), ~220 attendees. By comparison
SODA 387/139 36%
ESA 215/55 26%
STOC 280/78 27%
CCC 85/28 32%

Deadlines: CCC Dec 3, program Chair Peter Bro Miltersen, STOC Nov 20 (no joint submissions to CCC)

STOC 07 will be at FCRC in San Diego. Hotel will cost 129/139 single/double. Dates are June 11-13 for STOC, June 8-16 for FCRC.

FOCS 07 will be in Providence, RI. Program chair is Alistair Sinclair. Location is the new Renaissance Hotel, currently under construction.

FOCS 08 will be in Philadelphia.

Our community received a number of prizes, previously reported here: Jon Kleinberg, Nevanlinna Prize, Danzig Prize to Eva Tardos, and co-winners of the Fulkerson Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics, Volume 160, issue 2, 2004, Pages 781--793. and Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", J. ACM, Volume 51, Issue 4, 2004, Pages 671--697. Neil Robertson and Paul D. Seymour, "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, Volume 92, Issue 2 , 2004, Pages 325--357. (not really TCS, but we'll claim it!)

There was a new proposal by Umesh Vazirani: let us have no paper proceedings. Instead, let the papers be submitted (perhaps as little as one week before the conference) to a website. This would allow postponing submissions by perhaps 2 months, and would get extra benefits (cheaper registration, text searchable, available everywhere.

A lively discussion ensued. The economics of the proposal are unclear: would it decrease attendance? Should we worry about the economics? Some people like having the paper version at the conference. Making the "electronic proceedings" have page numbers, formatting, etc. would still imply text processing and editing. On the other hand, an electronic version would have substantial advantages. Would IEEE let us do it? What about libraries who paid for the proceedings?

It was pointed out that the IEEE electronic library is unreasonably expensive, and many institutions do not have it. A quick vote was taken, and results were inconclusive. Many wanted a CD with the proceedings. About an equal number of people wanted proceedings with CD as no proceedings and electronic versions only.

Our leaders promised to study the matter.

Finally the NSF report. Bill Steiger is going back to academia, in August. He was warmly thanked for his efforts for the community. I will give a detailed report tomorrow.

FOCS Begins

Weblog correspondent Janos Simon reports from Berkeley.

This is a pre-FOCS FOCS report, filling in for Lance.

FOCS 2006 is at Berkeley Marina, a lovely place on the Bay, with expensive sailboats next to the hotel gardens, against the beautiful backdrop of the San Francisco Bay, with the Berkeley hills on the other side. All of this even comes at a relatively cheap price.

Unfortunately the hills of Berkeley are not so near: downtown Berkeley is about 3 miles from the hotel, on the other side of train tracks and the interstate. This not only prevents one from easily strolling around the Berkeley campus and stopping at one of the nice coffeehouses or bookstores, but also makes getting dinner more of an adventure, involving a cab or a hotel shuttle. I am not complaining about the organizers: putting a conference together is a difficult balancing act, with too many constraints.

The conference itself should be excellent, with very strong papers, including the solution of the 2-player Nash equilibrium that won the best paper award. There will be three invited talks, all dealing in one way or other with Theory interacting with other areas of knowledge: tomorrow (Sunday) Karp will talk about "Theory of Computation as a Lens on the Sciences", Monday Terry Senjowski will teach us about Vision, and Tuesday Jon Kleinberg will discuss networks, social and technological. The biggest innovation relative to previous FOCS will be the presentation of Lady X and the Positive Eigenvalues, a rock concert. [For those with a historical bug, this is not an absolute first. Dexter Kozen, with Anna Karlin of the Severe Tire Damage rock band—the first to broadcast a rock concert on the internet—have in the past help expand our horizons in these directions, I believe at the Palo Alto conference, but I cannot offer precise pointers.]

The conference has parallel sessions (pros and cons have been previously and exhaustively discussed), so I will only be able to provide a very incomplete report of the papers presented. I should also add that I expect to miss many talks, not only due to my non-quantum nature and consequent lack of ability to be in two places at the same time, but also due to random phenomena: sleeping late, meeting friends, discussing ideas, wandering into the wrong lecture room, and forgetting about the time of talks I wanted to hear. So the papers I'll mention are not necessarily the ones I chose to listen to, just the ones I happened to not miss, and inferences about my taste or the quality of papers ignored would likely be mistaken.

Given that caveat, I can talk about two very nice results to be presented today. I heard them at Chicago before the conference.

The first is Tom Hayes' paper that gives a sufficient condition for certain important probabilistic models to converge rapidly. For definitions, technical details, etc read the paper. What I liked is that the paper is not only a significant technical improvement, but this seems to be the "correct" reason that lurked behind previous proofs, and this (I think) will be the proof we will teach.

The second is the paper by Belkin, Narayanan and Niyogi on estimating the surface area of a convex body. Both the area and the volume of high-dimensional convex bodies are very hard to approximate by the "natural" method of approximating the boundary by a simple smooth object: the number of parameters to do so grows too fast. For the volume, one can use random walks: an appropriate random walk on the space is stopped and we record whether we stopped inside or outside the object. The ratio of these events can be used to estimate the volume. Unfortunately this does not work for the surface area. The very cute idea of the Belkin et al paper is to put a heat source inside the object, and observe the amount of heat that leaks outside: this will be proportional to the area

Of course there are lots of technical difficulties, but they can be overcome. The details are not easy, but I thought the idea was new and nice.

Quickies

David Pennock gives a CS view of prediction markets and gambling on his new weblog Oddhead. For those interested in prediction markets also take a look at the group blog Midas Oracle.

Chris Leonard, former editor of the Elsevier theory journals, returns to academic publishing for the open-access publisher BioMed Central to help them expand into physics, math and CS. He writes about changes in scientific publishing (and other topics) in his weblog.

Should teachers try to make math interesting and relevant? No, according to Tom Loveless.

And I'd be remiss not to mention the lengthy New York Times profile on Shing-Tung Yau.

For-Profit Universities

On Monday the Chicago Bears played the Arizona Cardinals at the University of Phoenix stadium. Is this the stadium where the University of Phoenix normally plays their football games? No, the University of Phoenix doesn't even have a football team or a traditional college campus at all. Rather the University of Phoenix is a for-profit university with about 300,000 students taught at several small campuses in the US and beyond and online focusing on career-oriented majors. In an AP Interview, their new president Bill Pepicello explains their mission.

Our philosophy for serving students is the same as Harvard or Ohio State, and that is we're mission-driven. The mission of, say, Harvard is to serve a certain sector of the population and their mission is not to grow. And that's true of higher education in general. The reason the University of Phoenix exists at all is that is that all of those various (universities) and their missions did not provide access to a large number of students who are capable and wanted access to higher education. And that's our mission.

This university fills a need for training Americans for new careers as we continue to ship manufacturing and service jobs overseas. But the University of Phoenix doesn't fulfill other traditional university functions like basic or applied research or being the intellectual center of their communities.

For-profit universities haven't posed much of a threat for the traditional university model in the US. But in the long run as people get more comfortable with the virtual world of the internet, universities with a large on-line presence might radically change higher education as we know it.

Meanwhile India has a shortage of trained professionals as the country explores how to best address its higher educational needs. Germany on the other hand is focusing on encouraging high-level research by establishing elite universities, graduate schools and research clusters.

So how did the University of Phoenix get their name on the football stadium? The same reason the White Sox play in U.S. Cellular field—corporate sponsorship. At least we don't put corporate logos on the fronts of our jerseys like the European footballers.