Teaching PCPs

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

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

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

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

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

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

Complexity Deadline Approaching

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

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

The accepted papers for STACS and LATIN have been posted.

Introducing a Speaker

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

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

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

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

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

Another Satisfied Customer

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

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

Relativized Collapse of P and NP

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

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

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

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

Cornell versus Intelligent Design

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

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

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

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

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

The History of RAM

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

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

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

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

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

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

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

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

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

Acceptance Rates versus Competitiveness

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

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

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

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

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

The Enemy of the Good

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

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

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

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

Favorite Theorems: Defining the Future

October Edition

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

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

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

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

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

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

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

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

Negotiating Your Job

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

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

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

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

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

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

Games for Girls

This notice came into my inbox last week.

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

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

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

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

Bringing Complexity to Your iPod

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

Whither to Compete

A guest post by Rakesh Vohra.

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

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

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

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

Losing the Office Phone

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

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

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

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

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

Competitive Analysis

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

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

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

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

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

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

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

Making Yourself Known

An assistant professor asks

How do I get on program committees and editorial boards?

PC chairs and editors-in-chief usually have several excellent candidates to choose from so you really have to make yourself stand above the crowd. How do you do this?

Prove. Easy said than done, but no better way to make yourself known than by proving great theorems. Quality counts more than quantity. Be sure to make your results public, by submitting them to sites like ECCC as well as putting them on your own homepage.

Talk. When you give a talk, take the time to prepare, sell your work, make the talk understandable and audience-appropriate. Someone told me recently they treated every talk like a job talk. Not bad advice.

Meet. Go to workshops and conferences not for the talks but to meet people. Don't just hang out with people from your own university. Skip some sessions, hang out in the hallways and talk to whomever is around. Reconnect with your old colleagues from graduate school and make an effort to meet new people. Have lunch and dinner with people you don't know.

Write. Write up your research well so people enjoy rather than suffer when reading your papers. Put some effort into your introductions and really sell the importance of your work. In addition write a survey paper, write a book, write a weblog. Get others to view you as an expert in the field.

Organize. Organize a workshop, do local arrangements for a conference or other service to the community. I don't recommend this route for assistant professors as it takes considerable time and won't help your tenure case much.

Wait. Be patient. Your time will come.

List Decoding Beyond Expectations

The recent FOCS conference had two best paper award winners, the Khot-Vishnoi paper I had mentioned in my post on unique games and Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time by Parvaresh and Vardy.

List decoding considers codes where we have too many errors in the code to uniquely decode a string. These algorithms creates a short list of all of the possible decodings. Last year I had discussed list decoding in my Favorite Theorems series and said

Guruswami and Sudan give a polynomial-time algorithm that handles what is believed to be the best possible amount of error.

Guruswami and Sudan's algorithm works for the standard Reed-Solomon codes and is likely the best possible for that code. Parvaresh and Vardy develop a new but related encoding to get an improvement on the rate of the code, the ratio of the original message length to the code length. Guruswami and Sudan show how to list decode a 1-ε fraction of errors using Reed Solomon codes with a rate of O(ε²) while Parvaresh and Vardy achieve the same errors with their code with rate O(ε/log(1/ε)).

Algorithms for a Ten-Year Old

Yesterday my fifth-grade daughter, doing her math homework, asked

Is there a faster way to find greatest common factors other than with factor trees?

I live for these days. After I impressed her with Euclid's algorithm she asked

Is there a faster way to factor than with factor trees?

I thought for a while and then just answered "No."

Joy on the South Side of Chicago

Selling Theory

Thanks to Rocco for bringing us the news from FOCS, particularly a comprehensive summary of the business meeting. I am glad to have watched my White Sox in the World Series live and read a recap of the business meeting than the other way around.

A number of bloggers including Scott, Suresh, Sariel and physicist David Bacon have weighed in on the big panel discussion on how to generate interest in theoretical computer science. There was a big push for our community to publish in Science and Nature. I have seen more than a couple rather mediocre CS papers in Science. We need more than to just send our papers to these journals, we need members of our community on the editorial board.

The most interesting comments came from science writer Sara Robinson.

There is a perception among science editors that TCS is not what people want to read about: they want stories about health, things that cost a lot of taxpayer dollars, etc.

The New York Times, which Sara Robinson has written for in the past, used to give good coverage to research in theoretical computer science. But their Tuesday section Science Times has moved over the last couple of years from a general covering of science to a focus on medicine, environment and astronomy. Not just computer science but physics and chemistry get far less coverage than they once did.

What scares me most is what I see from incoming undergraduates. Far more high school students use computers now than say ten years ago but far fewer of them know how to program. Computer science is a victim of its own success, by making computers powerful, easy to use and well-connected, we have turned computers into a commodity like cars with the mystique of computation and complexity lost on the users.

Page Six

Final guest post from FOCS attendee Rocco Servedio.

Well, another FOCS has come and gone. In 50 years -- 100, tops -- we will know which papers from the conference stood the test of time. But meanwhile on to more pressing matters. Last week Lance promised that I would provide "all the gossip from the conference;" I'd hate to disappoint, so here goes. All names have been changed to protect the guilty, and pronouns should not be used to infer gender. Presenting...

"THE THEORY TATTLER"

• POTTED PROFESSOR: WHICH thirsty theorist drank so much beer at the business meeting that his PhD students had to help him back to his room? The greedy guzzler was next spotted Monday afternoon nursing a mug of black coffee in the back row and wincing at microphone feedback.

• DINNER DILEMMA: WHICH graph theory guru created an scheduling snafu when he separately told two rival gangs of theorists that he'd "meet you in the lobby in 15 minutes?" Let's hope his administrative assistant at Famous University manages things better when he's on his home turf.

• ENOUGH ALREADY! WHICH logorrheic logician went so far over time that he "practically had to be dragged off the podium?" Our sources say the session chair was scant seconds from pulling the projector plug when the babbling bore finally zipped it.

• HEARTBREAKER: WHICH complexity theorist Casanova has a love life that's more complicated than the proof of the Parallel Repetition Theorem? It seems there's no lower bound on this cheating cad's bad behavior.

Sadly, as you've probably guessed, none of these things actually took place (or if they did I didn't know about it; if so that's even sadder). In all seriousness, thanks to Lance for letting me post these last few days; it was fun, especially the chance to branch out into fiction-writing at the end.

Knuth Prize

The 2005 Knuth Prize was awarded to Mihalis Yannakakis of Columbia University. Mihalis's Knuth prize lecture was on "Probability and Recursion."

FOCS Business Meeting

Notes from the FOCS 2005 business meeting, reported by Rocco Servedio.

Yuengling, Sam Adams, Aspen Edge (low-carb).

Local arrangements: There were 144 non-student registrants and 141 students for a total of 285 registered attendees. Thanks to Avrim Blum and Anupam Gupta for a job well done on local arrangements. An interesting fact: doing local arrangements ourselves saves about $100/person on registration fees.

PC report: There were 268 submissions. 7 papers were retracted (an all-time high?); two of these were because of bugs found by the PC and five were initiated by the authors. Authors are encouraged to submit correct papers. There are 62 papers in the proceedings; 3 pairs of papers were merged (these papers got extra space in the proceedings). Distribution of authors (multiple papers means you get counted multiple times): 121 from U.S.A., 23 from Israel. 6 from Canada. 3 from Denmark, Italy, 2 from Germany, India, Czech, Hungary, 1 from Poland, Netherlands, Japan. Average # of authors per paper is 2.64 (or 2.48 depending on how you count merged papers). There were 7 single-author papers.

The two papers that were selected for Best Paper awards are "The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell_1" by Subhash Khot and Nisheeth Vishnoi, and "Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time" by Farzad Parvaresh and Alexander Vardy.

Two papers shared the Machtey Award for the best paper authored solely by students. These were "On the Complexity of Real Functions" by Mark Braverman and "On the Complexity of Two-Player Win-Lose Games" by Tim Abbott, Daniel Kane, and Paul Valiant.

As all readers of this weblog know, the next CCC (Computational Complexity Conference) will be held in Prague from July 16-20, 2006. The submission deadline is December 4.

LICS 2006 will held in Seattle in August 2006 as part of the Federated Logic Conference.

FOCS 2006 will be held in Berkeley; Sanjeev Arora will be PC chair.

Following an entertaining "Star Wars" themed bid, it was decided that FOCS 2007 will be held in Providence.

STOC 2006 will be held May 20-23, 2006 in Seattle. The submission deadline is November 3 (so stop reading this weblog and get back to work).

SPAA 2006 will be held July 30-August 2, 2006 in Cambridge, MA.

There was a panel discussion on "Exciting the public about (theoretical) computer science." The panelists were Bernard Chazelle, Dick Lipton, Ivars Peterson (writes about math and computer science for Science News), Sara Robinson (freelance writer in math and CS), Steven Rudich, and Eva Tardos; Avrim Blum moderated the discussion. A few fragmentary snapshots from the discussion:

Chazelle: Computing has never been more important, and never been more misunderstood. We are not doing as good a job of getting our work into the public eye as other fields such as physics. If the broader scientific community comes to use algorithms as a conceptual framework for the problems they are dealing with, we will have done well.

Lipton: We have lots of really profound and interesting intellectual challenges; one way to excite the public is to talk to them about these fundamental questions.

Rudich: How do we take what are doing and translate it into problems that people can relate to and care about? We have a million forms of encoding and should be able to do this; everyone can relate to the problem of trying to pack items into a suitcase of limited size.

Tardos: Whatever you do, it is probably possible to explain it to the public. There is an awful lot of stuff we do that is really not that hard to explain. A straw poll of the audience showed that very few people in our community have ever published in Science or Nature; it would be good if this could change.

Peterson: Publicity takes effort. The American Chemistry Council is spending twenty million dollars on advertising to sell the importance of research in chemistry. Astronomy often gets the front page of The New York Times; this is because of carefully orchestrated arrangements behind the scenes. The ACM, SIAM, IEEE do no publicity that I (Peterson) am aware of as a journalist. To get into the media: publish in Science and Nature. Lay language summaries and images are provided to the media a week in advance of each issue. There is always a Nature story in the newspaper on Thursday and a Science story on Friday. For newspaper coverage, one writer or a very small group can make a difference.

Robinson: Even all the approaches suggested above will have only a limited effect. Two reasons for this: (1) Theoretical computer science is hard to understand for the lay public and for reporters (and, as one audience member shouted out, for us). It is easier to write about global warming or why the coyotes are multiplying. (2) There is a perception among science editors that TCS is not what people want to read about: they want stories about health, things that cost a lot of taxpayer dollars, etc. Perhaps we should explore new models such as a dedicated math/science news agency?

(anonymous science writer audience member): "People like dinosaurs, asteroids, and things coming out of the ground...very little of what you guys have is concrete."

Finally, Dick Karp gave a report on behalf of the SIGACT committee on funding for theoretical computer science. The main goal of the committee is to improve stature and support of TCS within NSF. Based on a sample of 90 TCS investigators receiving funding between 2000 and 2004, 23% of funding came from TCS Foundations of Theoretical Computer Science and 55% came from ITR grants (now terminating). The average number of grants/year received per investigator was 2.4, and the median grant size per investigator per year was $70K. The 2005 TCS budget is about $6M. Some concrete items on the agenda for the future are to make a well-documented case that TCS is underfunded and to move TCS up a level in the CCF hierarchy.

First day of FOCS

A guest post from FOCS attendee Rocco Servedio.

Thanks to Lance for giving me this opportunity to fill in. I'm in Pittsburgh for FOCS, which started today and runs through Tuesday. Unfortunately because of travel constraints I couldn't make it to the Frieze Fest or FOCS tutorials that took place yesterday.

Pittsburgh is a city which sometimes gets a bad rap, but I've always enjoyed coming here. Besides the obvious -- at least for this blog's readers -- attraction of CMU, there are lots of neat things that you can't find anywhere else. I personally like the National Aviary, and the Carnegie museums are fun too. At the Warhol museum you can watch movies that make even the driest FOCS talk seem like a Jerry Bruckheimer production.

No time for museums today, though; the FOCS schedule is full of cool-looking talks, and tonight there is the business meeting and a panel discussion on "Exciting the public about (theoretical) Computer Science." I'll give a report on the business meeting and panel discussion later.

Math in Complexity

Another guest post by Bill Gasarch

Combinatorics is a branch of Computer Science
First episode, Second Season of NUMB3RS

I could have a post on how stupid this statement is, I'd rather ask the following better question:

How much do we use Combinatorics in Complexity Theory? Do we use anything else?

Towards this end I looked through the COMPLEXITY 2005 proceedings and assigned to each paper what sort of math I thought they used. I'm sure some can be argued. But here are the results:

• Probability: 8
• Combinatorics: 6
• Linear Algebra: 6
• Abstract Algebra: 4
• Number Theory: 2
• Diagonalization and Simulation: 2
• Calculus: 1
• Dynamic Programming: 1
• Philosophy: 1

OBSERVATIONS:

1. Very little continuous math. Even the Linear Algebra is usually over a finite field.
2. Very little Diagonalization/Simulation. This is part of the general trend away from methods of logic. I suspect there was a lot more of those at the first STRUCTURES back in 1986.
3. More abstract algebra than I would have thought, but I don't know if this is unusual or not.

Football Schools

I am spending most of this week at the University of Nebraska for a talk and a workshop. What does Nebraska have to do with Notre Dame, where I visited last month? Both are traditional football powerhouses, a place where the sport dominates the school and more Americans know these universities for their teams than their academics. I've heard most universities actually lose money on their football programs (though Notre Dame is an noted exception). Still schools use football to attract students, raise school spirit and bring back alumni and their money. In many states the highest paid public employee is the football coach. Notre Dame attracted a star professor by promising him season tickets "between the 45s" and Nebraska smartly has an admissions office inside the stadium.

Many foreigners find the level of US college athletics surprising but having grown up in this country I was shocked to find out European universities, for the most part, do not play each other in any sport, not even soccer. Where's the fun in that?

My next university trip will be to the University of Rochester, not a football powerhouse and in the same Division III wannabe-ivy league as the University of Chicago. Chicago used to be a football powerhouse, part of the Big Ten and had the first Heisman trophy winner, Jay Berwanger, in 1935. But then the new president Robert Maynard Hutchins who has been claimed to say "Whenever I feel like exercising, I lie down until that feeling goes away," eliminated the athletic programs and focused the university on academics. Only in the past few decades have they even had Division III teams.

With all this traveling, I won't be going to FOCS. But don't worry, I have lined up a special guest blogger to bring us all the gossip from the conference.

Finding Nash has Same Complexity as Finding Fixed Points

In a new paper, Daskalakis, Goldberg and Papadimitriou show that finding Nash Equilibrium in matrix games with four or more players is complete for the search class PPAD. PPAD is best described by the problem: Given an exponential-size direced graph with every node having in-degre and out-degree at most one described by a polynomial-time computable function f(v) that outputs the predecessor and successor of v, and a vertex s with a successor but no predecessors, find a t≠s that either has no successors or predecessors. The underlying combinatorial statement that such a t exists is used to prove Sperner's Lemma which can be used to prove the Brouwer fixed point theorem which in turn can be used to prove the existence of Nash Equilibrium.

The authors leave open the complexity of finding Nash Equilibrium for two and three players. They conjecture that for three players the problem remains complete for PPAD but two player Nash Equilibriums can be found in polynomial time.

True Impact

How do you measure your impact as a computer scientist? You can try measures like the Citeseer rank or the h-index, but the only scientifically valid test would compare the world today with the world where you were never born.

We can never actually run such a test but we can try the thought experiment. Even if you are one of the "greats," most of your theorems, even the best and most surprising, would have been eventually proved a few months or a few years later. Other theorems would never have been proved because no one, other than the non-existent you, would have cared. Other than speeding up science a little bit, you cannot get a long-term individual impact on the field solely by proving theorems.

But proving those theorems builds your reputation and with that reputation you can shape the direction of the field. With this reputation you can, for better or for worse, help shape the direction of the field and set the research agenda for a generation of young graduate students. You also have lasting influence through your graduate students and the undergrads you convince to study computer science.

We can run this thought experiment the other way. Suppose many years ago a sperm darted right instead of left and fertilized an egg that hatched a true genius in our field. How much difference could that one person have made on our research and our lives?

Blogging and Academics

The University of Chicago denying tenure to an assistant professor is rarely a breaking news story. Yet political scientist Daniel Drezner's case received considerable press including a Chicago Tribune story. Why? Because he had a popular blog.

I doubt the content of the weblog or its existence or popularity played negatively towards his tenure case. Perhaps some feel his time would have been better spent on "real academics" but most likely they considered his more traditional academic writings and, frankly, it's very difficult to get tenure at the U of C, particularly in the social sciences.

Will Drezner's weblog help him in his future job hunt? Ivan Tribble argued that weblogs can hurt a candidate for an academic position.

The content of the blog may be less worrisome than the fact of the blog itself. Several committee members expressed concern that a blogger who joined our staff might air departmental dirty laundry (real or imagined) on the cyber clothesline for the world to see. Past good behavior is no guarantee against future lapses of professional decorum.

I disagree with Tribble. Most non-anonymous academic webloggers know better than to discuss departmental politics in their blogs and departmental hiring committees should or will realize they have nothing to fear. A popular weblog raises one visibility in and out of their field—far more people read this weblog then download my research papers, for example. A weblog like Daniel Drezner's (much more read than this one) gives him an edge over his peers, a popularity that will open some doors that others will have to fight harder for.

Fonts

Fonts are the last thing I want to worry about when I write a research paper. Unfortunately fonts have often become the last thing I need to worry about when I write a research paper.

In the olden days (circa 1990), we all wrote our LaTeX papers using the Computer Modern font. When we sent a paper to a proceedings we printed up a clean copy and sent it via Federal Express.

Now we have choices of fonts. Fonts are a surprisingly complicated process. A good font is a work of art and a scalable font is actually a computer program for each letter. If you intellectual property issues for digital music is complicated, IP for typefaces is nearly impossible to implement well.

When some societies like the IEEE first started taking electronic uploads for their proceedings we would get the occasional disastrous effects because the IEEE fonts didn't match the fonts people used to create a paper. For example the "<" would appear as a "⇒" making some of the papers unreadable. Most of these organizations have become more aware of this issue but now require us to jump through some hoops (use the right fonts and style files and putting the paper in the appropriate format using the right program to do so). Makes me wish for the old days when I could send a paper and they would scan it, which the IEEE will still do but charge extra for.

Sometimes you'll see "¿From" in older papers. This is not a font problem but a property of sending text files through email would add a ">" to a line beginning with "From" which would come out "¿From" after LaTeX processed the file. You see it less now as files get sent via attachments instead of directly in the mail body.

Distractions from worry about something as minor as fonts really keeps us away from focusing on research and other important activities. Remember, no one was ever denied tenure for bad font selection.

Early or Late

As you can see from the timestamp of this post, I came into work quite early this morning. I had to drive and needed an early start (about 6 AM) to beat Chicago traffic and get a good parking spot. When I arrived I saw another professor in his office. I knew he wasn't the early type and likely spent the night here. When I said "Hello," he replied "Deadline."

Which one of us is keeping the crazier hours?

Favorite Theorems: Logical Characterization of NP

September Edition

Usually we think of the class NP as either languages accepted in polynomial-time by a nondeterministic Turing machine or languages with polynomial-time verifiable witnesses. Ronald Fagin gives a characterization of NP based on logic without references to Turing machines or polynomial time.

Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, 1974, pp. 43-73.

In this paper Fagin shows that NP consists of exactly the languages expressible with existential second-order formulas. For example consider a graph G described by an edge relation E(i,j) and we can define whether G is k-colorable by

∃C ∀i,j (1≤C(i)≤k ∧ (E(i,j)→C(i)≠C(j)))

With some more work you can use binary predicates. In general every language in NP has an existential second-order characterization with binary predicates and a universal first-order part.

Stockmeyer generalizes Fagin's result to characterize the polynomial-time hierarchy with second-order formulas.

Fagin's result started the area of descriptive complexity that characterized many common complexity classes in various logics and has connections to the complexity of database queries. Neil Immerman's work in descriptive complexity led him to his proof that nondeterministic space is closed under complement. Robert Szelecpsényi independently came up with a similar proof through a different approach.

Papadimitriou and Yannakakis use Fagin's result to characterize the class MAX-SNP of optimization problems. One of the first corollaries of the PCP Theorem is to show the MAX-SNP hard problems cannot be approximated within an arbitrary constant unless P=NP. In fact the concept of probabilistically checkable proof itself originally comes from a second-order view of NP that originated from Fagin's paper.

Update 10/12: Fagin adds an addendum.

Thanks to Lance and Siva for the kind words about my theorem. Let me clarify the story on the arity of the existentially quantified relations.

An existential second-order formula about, say, graphs, is a formula of the form

∃ Q₁ ... ∃ Q_k S( E, Q₁, ..., Q_k)

where E represents the edge relation, Q₁, ..., Q_k are existentially quantified predicates of arbitrary arity, and S(E, Q₁, ..., Q_k) is a first-order formula that involves only E, Q₁, ..., Q_k. As an example, 3-colorability of the graph can be expressed by an existential second-order formula

∃ Q₁ ∃ Q₂ ∃ Q₃ S(E, Q₁, Q₂, Q₃),

where Q₁, Q₂, and Q₃ are unary predicates (that represent the 3 colors), and S(E, Q₁, Q₂, Q₃) is a first-order formula that says "Each point has exactly one color, and no two points with the same color are connected by an edge''.

In the case of graphs, my theorem says that if T is a class of graphs that is closed under isomorphism (that is, whenever T contains a graph G, then it contains every graph isomorphic to G) , then T is in NP if and only if T is defined by an existential second-order formula. In the case of graphs, it is an open problem as to whether we really need to allow existentially quantified predicates of arbitrary arity. On the one hand, it is conceivable that there are NP properties of graphs that require existentially quantified predicates of arbitrarily large arity. On the other hand, it is conceivable that we can capture every NP property of graphs by allowing only a single existentially quantified binary predicate.

If we consider NP properties not just of graphs, but of arbitrary structures (such as structures with, say, two ternary relations and five 7-ary relations), then the characterization of NP in my theorem continues to hold, but in this case, it is known that existentially quantified binary predicates do not suffice. In particular, Ajtai proved (in the same amazingly rich 1983 paper [Σ₁¹-formulae on finite structures, Annals of Pure and Applied Logic 24, 1983, pp. 1-48] where, among other things, he proved the Furst-Saxe-Sipser theorem independently of Furst, Saxe and Sipser), that if we consider structures consisting of a single m-ary relation, then the statement "The number of m-tuples in the relation is even" cannot be captured in existential second-order logic with any number of existentially quantified predicates of arity less than m.

A gentle introduction to the work I've mentioned in this note and to some other work in finite model theory appears in my survey paper Finite model theory-a personal perspective.

A New Packard Fellow

Piotr Indyk, himself a 2003 Packard Fellow, writes

On the recent blog topic of awards: you might be interested to know that Venkat Guruswami just received a Packard Fellowship.

Congrats to Venkat for recognition (and money) well deserved.

NP-Completeness Papers

A colleague is refereeing a paper in a non-computer science area that shows a certain computational problem is NP-complete. The proof uses a simple reduction from a standard NP-complete problem. Should such a result be published? As long as people really care about the computational problem, then yes, such results should be published.

The greatest gift of computational complexity to society is the ability to use NP-completeness to show that a large variety of problems are likely hard. The field has also developed many tools to help easily show such problems are NP-complete. We shouldn't penalize people for using these tools.

This is one of those cases where having a "simple proof" hurts the paper. If the paper used PCP technology in the proof it would without question be published. And if the paper relied on the unique games conjecture (and thus a weaker result) the paper would likely get accepted into STOC.

Unix Free Since 1999

My first computer was a TRS-80, my second an Apple IIe. In college I mostly programmed in IBM 370 assembly code. But in graduate school (first at Berkeley and then at MIT) I starting using Unix in its various forms and its programs, first Vi and Troff, then Emacs and LaTex and reading email via the command line "mail."

My future wife had one of the early "IBM Compatible" PCs and I liked some of the programs one could use, like Quicken, Prodigy (an information dial-up service), good spreadsheets and word processing. My home computer has always been a DOS/Windows machine since.

Windows had good calendar and email programs long before they were available for Unix so at one point I got a PC card for the Sun in my office which ran Microsoft Windows in an Unix window. As I found myself spending more and more time in that window, my next machine was a Windows machine with an X-Windows program so I could connect to the department's Unix machines to use Emacs and LaTex.

Soon very good Emacs and LaTex programs became available for Windows and when I moved to NEC in 1999 I went Unix free and haven't looked back. My biggest complaint about Unix was the user interface. To print pages 3 to 5 of a latex document is easy in windows, for Unix I had to do a man dvips since I could never keep straight which flags did what. Once I spent hours trying to figure out what I did wrong in a Make program (I had uses spaces instead of tabs). I'll never forget the time I accidentally typed "rm temp *" instead of "rm temp*".

Ever since people have kept telling me Linux interfaces and programs have gotten much better, and they have, but never enough to get me to switch back. Some Apple lovers have tried to get me to move to Apples, but they just never had the software available that PCs do. Windows emulators for Apples are popular but you don't see the need for the other direction.

As more and more of the programs I use become web based, the actual platform becomes less and less important. Still though as someone who likes an easy user interface and wide availability of programs and doesn't do much programming and scripting, Windows has worked well for me.

Tradition

A conversation with a graduate student today.

• Student: Why doesn't FOCS have a best paper award this year?
• Me: They often don't announce the winners until the conference begins.
• Student: Traditionally the best paper get longer talks and there are none scheduled.
• Me: There's no such thing as tradition at STOC and FOCS. Rest assured (though I have no prior knowledge) there will be a best paper award given.

I've heard that by tradition FOCS has had single sessions and STOC has had parallel sessions. Not long ago both had parallel sessions and before that FOCS had the parallel sessions (the first time with a two volume proceedings) and STOC had single sessions, and before that both had single sessions. STOC/FOCS used to be Monday-Wednesday, now they are Saturday-Tuesday and sometimes not. STOC/FOCS were always in North American and then they weren't. FOCS once had the only best student paper award and then had the only best student paper award named after somebody. Now they both do. We've had invited speakers. We've not had invited speakers. We've had tutorials. We've not had tutorials. One day one of the conferences will have electronic proceedings and the other won't and that will be tradition.

The decisions of how STOC and FOCS are run are up to the program committee with constraints on schedule and the local arrangements site. Two or three years of the same in a row becomes a "tradition" and hard to change. But we shouldn't let these "traditions" prevent us from running the best possible conferences and nor should you count on them to continue as is. Traditions keep us in the past, change pushes us to the future.

DNA Testing for Sports

In the second biggest sports story in Chicago (after the White Sox rout of Boston), the Chicago Bulls basketball team traded Eddy Curry to the New York Knicks. The Bulls had wanted Curry to take a DNA test to check for a certain heart condition and Curry refused so finally they decided to trade him to the Knicks who will not require the DNA test. I understand the Bulls' position but testing DNA for diseases for employment opens up a big can of worms. Shades of Gattaca?

On a completely different note, one-time guest blogger Scott Aaronson has joined the blogosphere himself. What took him so long?

Euthanizing a Virtual Pet

We had a high pitch tone coming from somewhere in our family room but we couldn't find the source. I shut down the power in case the sound was coming from the stereo system or lights but the tone remained. Finally we found the culprit, my daughter's Tamagotchi buried under some books.

Pressing the buttons failed to quiet the device, so I attempted to open the unit up to remove the battery. When that failed I finally put the Tamagotchi in a plastic bag and hit it several times with a hammer until it finally shut up.

Later I confessed the destruction of the virtual pet to my daughter who seemed not to care in the least. The fad had ended. But next on my daughters' wish list: Nintendogs.

Awards

The Nobel Prizes will be announced this week and I predict that no one will win the Nobel Prize in computer science for the 105th consecutive year. Computer Science's highest honor, the Turing Award will be announced in early 2006 (February 16 last year).

We also have some awards coming up for theorists. At every third STOC/FOCS conference, the Knuth Prize is given for outstanding sustained contributions to theoretical computer science. We will find out the next winner at the upcoming FOCS Conference in a couple of weeks.

Every four years the International Math Union awards the Nevanlinna Prize for contributions in "mathematical aspects of information sciences" to a scientist under forty. The previous winners have all been computer science theorists and we have several excellent candidates for the 2006 prize as well.

ACM SIGACT sponsors or co-sponsors several other awards such as the Gödel Prize given to the best recent journal paper (where the definition of "recent" keeps changing) and the Paris Kanellakis Theory and Practice Award given to theorists whose work had practical applications.

Cocktail Conversations

I once met a professor at Chicago that would say "My business is war, and business is good." I have a food scientist friend from college who did his doctorate on starch and had a catch phrase "Everything you eat is healthy, safe and nutritious." But when I start having a conversation with non-scientists it often goes like this:

• Them: "What do you do?"
• Me: "I'm a professor at the University of Chicago."
• "That's neat. What do you teach?"
• "Computer Science."
• (a) "Oh. Excuse me, I see someone I know," or
  (b) "I'm setting up a wireless network in my house.", or
  (c) "I don't use the computers much but my kids are really into it."

I'm sure many of you have had similar experiences. On occasion they will ask me about my research and I will regale them with stories about traveling salesman and Arthur and Merlin, but that rarely goes far. It could be worse, I might have done my research on Hopf algebras.

How do you discuss your research with non-specialists? I'm sure some of you solve this problem by not having any non-CS/Math friends. But if we can't easily discuss our work one-on-one how do we convince the public that our research is important to them and society at large.

Circuit Complexity and P versus NP

In 1983, Michael Sipser suggested an approach to separating P and NP.

One way to gain insight into polynomial time would be to study the expressive power of polynomial-sized circuits. Perhaps the P=?NP question will be settled by showing that some problem in NP does not have polynomial-sized circuits. Unfortunately, there are currently no known techniques for establishing significant lower bounds on circuit size for NP problems. The strongest results to date give linear lower bounds, and it does not seem likely that the ideas there can go much beyond that.

Over the next few years, circuit complexity played a central role in theoretical computer science. In 1985, Yao showed parity required exponential-sized constant-depth circuits, greatly strengthening the bounds given by Furst, Saxe and Sipser. Håstad quickly followed with essentially tight bounds.

Shortly after Razborov showed that the clique function requires large monotone circuits. If we could just handle those pesky NOT gates, then we would have proven P≠NP.

Then Razborov (in Russian) and Smolensky showed strong lower bounds for computing the mod_p function using constant depth circuits with mod_q gates for distinct primes p and q. These great circuit results kept coming one after another. We could taste P≠NP.

But then it stopped. We still saw many good circuit complexity papers and some beautiful connections between circuit complexity and communication complexity, derandomization and proof complexity. But the march of great circuit results toward P≠NP hit a wall after the 1987 Razborov-Smolensky papers. As far as we know today, NP still could have linear-sized circuits and NEXP could have polynomial-sized constant-depth circuits with Mod₆ gates.

Boppana and Sipser wrote a wonderful survey on these results in the Handbook of Theoretical Computer Science The survey remains surprisingly up to date.

Exciting Baseball Ahead

The last week of the major league baseball regular season starts tonight with some tight races ahead. The wild card adds some interesting complexity to the mix (so I can justify this post on the weblog).

My team, the Chicago White Sox (94-61), who have squandered most of their 15 game lead, still leads the Cleveland Indians (92-64) by 2 1/2 games in the AL Central. The White Sox finish the season with three games at Cleveland starting Friday.

Meanwhile the Boston Red Sox (a team many theorists root for since many of us spent time in Boston) are tied with their rivals, the New York Yankees at 91-64 in the AL East. Boston hosts the Yankees for the final three games also starting Friday.

The White Sox magic number is five (White Sox wins + Cleveland losses) to win the division. For the wild card their number is also five (White Sox wins + max(Boston losses, New York losses)). The White Sox get into the playoffs with only three wins since Boston or New York has to lose at least two of their three game series.

White Sox, Red Sox, Yankees, Indians: Three will go to the playoffs. One will end their season.

There are still some races open in the other divisions but it's hard to care, though it will be interesting to see if San Diego wins the NL West with a losing record.

Update 9/29: White Sox have clinched the central division!!! At worse they will be tied with the Indians, but because they will have a better record than any second place team (since the Yankees and Red Sox can't both win the rest of their games since they play each other), there will be no extra game, the White Sox would win the division based on a head-to-head tie breaker and the Indians would be the wild card team. So complex that the Chicago Tribune didn't get it right this morning and the champagne was barely ready in time.

Game Theory

Speaking of names, the associated press released a story yesterday More Colleges Offering Game Theory Courses about new courses on creating video games. CNN originally used this title and has since retitled the article More colleges offer gaming theory courses, and some sites now have the more accurate title More Colleges Offering Video Game Courses.

Many fields have historically bad names (like Computer Science) but Game Theory has a name that invokes an area of study quite different than what it actually does. Bob Soare led the charge to change recursion theory to computability theory with some success. Should the game theory community try to do the same? And what should they call it?

The Price of Freedom?

An anonymous guest post.

I was at a conference this summer where I saw several talks about distributed optimization that used the terms "social optimum" and "price of anarchy". (I believe that Christos Papadimitriou coined these terms.) Most of the speakers that I saw using these terms were European, and I found myself wondering if different terminology would have been chosen if an American theorist had initiated this line of research. (e.g., Nash only named it an "equilibrium"…) What do you readers think?

Egos Needed

I've often heard that scientists have unusually big egos. I don't disagree, egos are a part of being a scientist, a great motivator for us. I still love that feeling when a paper gets accepted in a conference, when someone mentions my name in a research talk or a paper, or that rare moment when the popular press picks up on our research. Even that quiet feeling of self-satisfaction when you find your own solution to a difficult but already solved problem. That need to feed the ego keeps us producing results, trying to please our peers. For better or for worse, it keeps us from doing weird research that no one will understand or follow.

Use your ego for motivation but try to not let it affect your outward personality, difficult to do in a community of strong egos. Sometimes our community even rewards those whose brag about themselves, if they can do so convincingly.

Egos vary dramatically. There must be scientists out there who work purely for the love of science, but I have yet to meet one. And then there are those on the other end of the spectrum. Several years ago, Stephen Wolfram came to Chicago to introduce Mathematica 2 and said "First there was Euclid, then there was Gödel and then there was Mathematica."

Short Takes

Congratulations to Jon Kleinberg, theory's newest genius.

Suresh reports that Tobias Gerken has shown that given any large enough set of points in the plane in general position (no three colinear), six of them form a convex hexagon containing none of the others. That is a geometry theorem even I can understand.

Sanjeev Arora gives an update on the SIGACT funding committee. I foresee very lengthy STOC and FOCS business meetings.

Lisa Randall, Harvard physicist and sister of CS theorist Dana Randall, wrote an op-ed piece in the Times on how scientific terms like "relativity", "uncertainty principle" and "global warming" often give the public the wrong impression of these concepts. Personally I would be excited if the general public knew enough about computational complexity to misunderstand it.

Thanks a Bunch STACS

The STACS conference has ruined my weekend. How? They extended their submission deadline from Friday to today. Why don't I just pretend the deadline was Friday and I would be none the worse off? Co-authors.

The extended deadline let one of my co-authors slack off. Another set of co-authors decided to submit a result to STACS that we probably would have held off for another conference. So I'm spending too much of this weekend reading over and editing papers.

For better or for worse, computer scientists schedule their lives around conference deadlines. It would be best if they weren't moving targets.

Proof

The movie Proof opens today after more than two years after a number of the scenes were filmed at the University of Chicago, some right in Ryerson (home to computer science). The movie got caught up in the Disney-Miramax divorce and is one of a half-dozen movies being released by Miramax before the September 30 separation date.

I saw the play as part of the excursion during the 2002 QIP conference and enjoyed it though I felt the mathematician's life didn't feel right, it went a bit too far on the pressure to produce.

I rarely see non-children's movies in the theaters these days so I probably won't see Proof until it is out on DVD. But let me know what you think about the film (careful about spoilers) and who makes the better mathematician: Jake Gyllenhaal (Proof) or David Krumholtz (Numb3rs).

Anatomy of a Theorem

A comment to Tuesday's post mentions the result

If Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses.

He gives credit to Schöning but this theorem combines results from a variety of papers.

Goldreich, Micali and Wigderson had a breakthrough paper with three main results.

1. If one way functions exist, every language in NP has a (cryptographic) zero-knowledge proof,
2. Graph Isomorphism has a statistical zero-knowledge proof (where the verifier learns nothing except that the graphs are isomorphic in an information-theoretic sense), and
3. Graph Non-Isomorphism has a bounded-round interactive proof.

It's the last result that we need. The protocol is rather simple.

Input: (G₁,G₂)
Verifier: Pick i∈{1,2} and a permutation π of the vertices uniformly at random. Let G=π(G_i).
Verifier→Prover: G
Prover→Verifier: j
Verifier: Accept if i=j.

If the two graphs are not isomorphic a powerful prover can determine which graph the verifier originally chose. If the two graphs were isomorphic the prover would only have a 1/2 probability to getting the answer right. We can lower the error with parallel repetition.

This protocol requires private coins that the verifier can flip but the prover can't see. Goldwasser and Sipser show how to convert any private-coin protocol to a public-coin protocol where the verifier flips the coins in front of the prover.

Babai and Moran show how to take any bounded-round public-coin protocol and create an equivalent protocol where the verifier flips random coins and the prover responds, the class AM.

Boppana, Håstad and Zachos (which combined two earlier papers) show that if co-NP is contained in AM then the polynomial-time hierarchy collapses to the second level.

Putting it all together, if graph isomorphism is NP-complete then graph non-isomorphism is co-NP-complete and we have co-NP in AM implying the hierarchy collapses.

Schöning gives a self-contained proof and shows that graph isomorphism is in the low hierarchy.

In my first STOC paper I show that for any language that has a statistical zero-knowledge proof, there is a bounded-round interactive proof for the complement of that language. Running through the same set of papers as above one gets that if NP-complete sets have statistical zero-knowledge proofs then the polynomial-time hierarchy collapses.

Jonathan and Me

My brother is out in California co-producing a movie Certifiably Jonathan, a quasi-documentary about Jonathan Winters. The basic story: Jonathan Winters loses his sense of humor and visits a number of comedians (such as Robin Williams and Rob Reiner) to help him get it back.
When I was out in California in August, I had the opportunity to watch a filming of a segment of the movie. Howie Mandel decided to take Jonathan to the Target because you can find anything (including a sense of humor) at the Target. I watched as Howie and Jonathan first met where Howie had this look of awe while talking to his idol. For the film they drove around the store in the handicapped carts making some pretty funny jokes along the way.
Afterwards I had lunch with Jonathan and the crew from the movie which was where the picture above was taken. Jonathan spent most of the time telling stories of his youth, sometimes sad but always in a funny way.
I know many of you readers are too young or foreign to know who Jonathan Winters is. But for an American of my generation it was great fun to meet and talk to one of the funniest people alive.

Favorite Theorems: NP-Incomplete Sets

August Edition

In the 1950's Friedberg and Muchnik independently showed there existed computably enumerable but non-computable sets that are strictly weaker than the halting problem. How about a polynomial-time version? We have some natural sets that are good candidates like Factoring and Graph Isomorphism but no proofs that these sets lie in-between P and NP. Any proof would imply P≠NP and Ladner, in a theorem that now bears his name, shows that P≠NP is the only assumption you need.

Richard Ladner, On the Structure of Polynomial Time Reducibility, JACM 1975.

Ladner shows that if P≠NP there exists an A such that

• A is not in P,
• A is in NP, and
• A is not NP-complete.

Here is my write-up of two proofs of this result, one due to Ladner and the other to Russell Impagliazzo. Ladner proves a more general result, given any computable sets A and B with B reduces to A but A does not reduce to B, there is a set C such that B reduces to C and C reduces to A and A does not reduce to C and C does not reduce to B. This result holds for any reasonable notion of resource-bounded reduction, and in fact you can embed any partial order between B and A.

Ladner's proof works by blowing holes in SAT using a clever looking-back technique to keep the set in NP. In the end it is a little unsatisfying because from the viewpoint of any fixed length, the set is either NP-complete or easy on that length. Impagliazzo's proof tries to get around this by slowing down the reduction but his proof still leaves large gaps of easily computable inputs. But until we learn how to show P≠NP we won't have any other method for proving the existence of incomplete sets.

Comments on Comments

If you only read these posts, say through the mailing list or a newsreader, then you miss the best writing on this weblog—the comments. Take some time (and it will take some time) and read through the comments of last Monday's post SODA Rising.

Otto von Bismarck said "If you like laws and sausages, you should never watch either one being made." The same could go for a conference program. With some notable exceptions, great papers will be accepted, lousy papers will get rejected. But the majority of submissions fall into a middle range where decisions get made by the tastes of the program committee, not only in area but on whether to emphasize deep techniques versus importance and usefulness of the result. Different PCs make very different decisions and one shouldn't make any conclusions about how one paper fares in different submissions.

On the purpose of STOC and FOCS: STOC started in 1969 because the Switching and Automata Theory (SWAT) conference had too much switching and automata theory and not enough of the newly growing areas of complexity and algorithms. Eventually SWAT became FOCS and followed suit. The only official role they have today is to be the flagship conferences of two theory societies, ACM SIGACT (STOC) and the IEEE-CS TC on Mathematical Foundation of Computer Science (FOCS). What purpose do they play now in a diverse theory community is a good but not well-answered question. So we have kept the status quo where, except for adding parallel sessions, have followed the same basic model since the 60's.

As a commenter has pointed out, the accepted papers list of the upcoming SODA Conference came out last week. I'll leave it to bloggers who care more about algorithms to talk about the good papers there.

Do Wikis Work?

John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki. For those not up on the nomenclature, a wiki is a specially designed web page that anyone can change usually with mechanisms for tracking and undoing those changes if necessary. Ideally a wiki will allow the zoo to remain up-to-date without continual intervention from Scott. But will it work?

The Wikipedia has a number of entries for various complexity classes. I generally find them for the most part accurate but not complete. Take for example the NL entry which doesn't note that NL is closed under complement but instead has the misleading result that RL=NL (where one allows the randomized machine to have infinite computation paths). Sure I could fix the entry in wikipedia but there are at least two problems:

• There aren't enough people in the field who have the time and patience to go through all the entries and update them.
• I firmly believe RL should be what Wikipedia calls RLP. But what right do I have to impose my naming conventions on the whole wikipedia universe.

Sanjeev Arora and Boaz Barak set up Theory Matters as one big wiki. Boaz once said the following in a weblog comment.

Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.

But people are reluctant, for whatever the reason, to edit the wiki. Outside of the "Survey Collection" you can nearly count the number of contributors to the wiki on one hand.

In short wikis, like anything else on the web, can be a good source of information but are often incomplete sometimes in important ways. Just because anyone can edit a wiki doesn't mean that they do.

P/poly

A student asked me why P/poly was an interesting class? A very interesting class with a funny name. It combines time and program-size complexity, and characterizes non-uniform efficient time and languages with small circuit complexity.

Here are two equivalent definitions of P/poly.

• A language L is in P/poly if there is a language A in P and a set of advice strings {a₀,a₁,…} such that |a_n|≤n^O(1) and x is in L if and only if (x,a_|x|) is in A.
• There is a family of circuits {C₀,C₁,…} such that |C_n|≤n^O(1) and for all n and all x=x₁…x_n, x is in L if and only if C_n(x₁,…,x_n) accepts.

The equivalence comes from Ladner's proof that the circuit value problem is P-complete. Some argue that P/poly is a better notion of efficient computation than P since we allow the program size as well as the time to grow as the input grows. Techniques from Adleman show that BPP is contained in P/poly. However P/poly contains noncomputable and in fact an uncountable number of languages

Here are just a few areas where P/poly plays a crucial role.

• Combinatorial Approach to P versus NP: Karp and Lipton show that if NP is in P/poly then the polynomial-time hierarchy collapses. So one approach popular in the 80's to show P≠NP tried to show an NP problem did not have polynomial-size circuits. Razborov shows the clique problem did not have polynomial-size monotone circuits.
• Derandomization: Nisan and Wigderson show that hardness against nonuniform classes can give us pseudorandom-number generators. Building on their work, Babai, Fortnow, Nisan and Wigderson show that if EXP is not in P/poly then BPP can be simulated in subexponential time on infinitely many input lengths.
• Cryptography: Often security is defined against P/poly adversaries to capture extraneous information in the system.
• Learning Theory: Learning polynomial circuits would be the Mecca of learning theory. Can't be done in the usual models unless factoring is easy. Bshouty et. al. show we can learn circuits probabilistically with an NP-oracle and hypothesis queries.

FOCS

From Anupam Gupta

A favor: the FOCS conference registration site is open; could you put up a small post on your blogs letting people know this, along with the fact that the advance registration deadline is September 23rd?

I did send mail to theorynet and dmanet, but clearly blogs are where the action really is.... :) thanks a ton, gents!

Done but my readers shouldn't count on the weblogs to tell them when to register or submit papers. Subscribe to DMANET or Theorynet, check the Theory Calendar or, most reliably, Google the conference to find out the appropriate deadlines.

SODA Rising

As theoretical computer science grew during the past twenty years, the general theory conferences STOC and FOCS could no longer present all of the good papers in theoretical computer science and a number of smaller specialized conferences arose, for example Computational Complexity, Learning Theory (COLT), Computational Geometry (SoCG) and many others. But one of these specialized conferences, the Symposium on Discrete Algorithms (SODA) has grown larger than STOC and FOCS both in submissions and attendance. Perhaps this should not be too surprising in that algorithms is a broad area and there is only one SODA each year and two STOC/FOCS conferences.

Recently though I've seen a few circumstances where SODA gets mentioned in the same breath as STOC and FOCS as an equal. For example, the SIGACT Home Page lists the upcoming FOCS, STOC and SODA conferences. OK, SIGACT co-sponsors SODA but the bottom of the upcoming FOCS Home Page (side note: Early Registration Deadline Sept. 23) list the previous FOCS, STOC and SODA pages. FOCS is an IEEE conference with no official connection to SODA. Finally Cathy McGeoch is trying to set up a hockey game at an upcoming FOCS, STOC or SODA conference. Can you have a true TCS World Cup with just algorithms people?

Are SODA papers getting the same prestige as STOC and FOCS papers? Not yet but we are heading that way. Is it truly a good thing to move from a STOC/FOCS/specialized conferences system towards a STOC/FOCS/SODA/other specialized conferences system?

Questions About Crypto

Bill Gasarch wants your help to judge a new book.

I am reviewing Encyclopedia of Cryptography and Security for a future SIGACT NEWS book review column. I will review it by asking various people for THINGS THEY WANT TO KNOW ABOUT from such a book, then I look them up, and see how the book does. (ease of finding it, value of information, etc.)

So, I request that you EMAIL me (gasarch@cs.umd.edu) a question that you would like to see in an encyclopedia of Crypto and Security.

If you know someone who probably doesn't read this blog but has good questions (e.g., a colleague working in Systems who works on security) pass this on to them.

Hard Times for the Big Easy

I have been to New Orleans twice. First for the 1991 STOC conference which overlapped the Jazz and Heritage festival. Then again in 1994, one last fling when my wife was pregnant with our first child. We went to the French quarter for crawfish and listened to Jazz at Preservation Hall, took the trolley down St. Charles Avenue, got our baseball fix with the New Orleans Zephyrs AAA team (the major league teams were on strike) and saw the Mother's Day Parade ("Mother" being a famous New Orleans transvestite).

Now this famous city lies mostly flooded, one of the victims of Hurricane Katrina. A major city, which has hosted many Superbowls and the biggest party in America in the days before lent, lies devastated by the hurricane, not to mention the tremendous damage in other Gulf Coast communities. With the tsunami last December, nature has not been kind to us this year.