If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.

I could write several posts on badly named complexity classes. For now let me mention two important ones.

• NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
• PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.

In Amsterdam I always go for the Uitsmijter (literally "Bouncer", like at a club), basically an open-faced sandwich with fried eggs on top. I usually go for the Rostbief Uitsmijter and the Ham-Kaas version (Ham and Cheese and the Eggs) can really clog those arteries.

But the Uitsmijter is downright healthy compared to the Porto delicacy Francesinha ("Little French Girl"). One starts with a thick slice of bread then add layers of ham, steak and sausage. Cover with another slice of bread and pour melted cheese on top. Then add the fried egg and smother the whole thing in gravy. Right now Porto is having their Festa da Francesinha by the river where restaurants from all over the city come to offer their versions of the Francesinha.

Luis Antunes says "A little bad food is good for stomach every now and then." After eating a Francesinha at lunch today I'm not sure my stomach agrees.

--
Posted by Lance to Computational Complexity at 7/13/2006 12:43:00 PM

Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.

In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.

But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.

I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.

The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.

We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.

Blogging will likely be light this week as the conference keeps me busy and I once again have limited Internet access.

One of the students in Chicago had planned to go yesterday to Israel to work for a month with Eldar Fischer at the Technion in Haifa. He postponed his trip, no so much because of the danger, but because getting to Haifa has become very difficult and the University has temporarily closed. The Technion, aka The Israel Institute of Technology, has by far the largest collection of theoretical computer scientists at any single university. Haifa University also has a nice theory group. We sincerely hope the situation resolves itself quickly and they can return to a sense of normalcy, as normal as one gets in that region.

--
Posted by Lance to Computational Complexity at 7/17/2006 02:30:00 AM

The next talk "Polynomial Identity Testing For Depth 3 Circuits" by Neeraj Kayal and Nitin Saxena is the first paper in Complexity history to win both the best paper and best student paper awards. The main result showed how to deterministically check whether an algebraic circuit was identically zero when the circuit has depth 3 with bounded fan-in on the top gate. Their advisor Manindra Agrawal was program committee chair but he did take the proper precautions in the discussions of the awards.

We had a reception last night at the Michna Palace in Prague. One young student remarked how one must be the smartest person in the world to prove new theorems. Not at all true. We have different backgrounds, different strengths, different experiences, different views on complexity that sets a situation where I can prove something that someone else would struggle with while they can prove something I would never find. Even if you have a similar background to someone "smarter than you", they don't have time to work on every problem so you can find good ones to work on your own.

Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

--
Posted by Lance to Computational Complexity at 7/18/2006 02:24:00 AM

Other notes from the business meeting:

Pavel Pudlak and Eric Allender are the new members of the conference committee taking over for Harry Buhrman and Avi Wigderson ending their three-year terms.

This year we decided to discontinue the Complexity Abstract program. The abstract program let people write up a one page abstract on any of their papers and Bill Gasarch (later Steve Fenner) would collect and distribute electronically before the conference. The conference started program back in the 80's when people who didn't have their papers in the conference wanted a forum to announce their results. But now with the ECCC and the arXiv, we no longer need this program.

The 2007 Meeting will be June 13-16 at FCRC with STOC and other conferences. Peter Bro Miltersen will be PC chair. There will not be a joint session with STOC as we had at previous FCRCs though there will be some coordination in scheduling the talks during both conferences. The 2008 meeting will be at the University of Maryland.

--
Posted by Lance to Computational Complexity at 7/20/2006 02:29:00 AM

I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the subsequent overwhelming emphasis on implementation (studied via science/math), rather than specification (perhaps better studied as an art?).

One might argue that two fields should have formed, analogous to architecture and engineering say.

Sure, the implementation part is important (e.g., efficiency), but what to implement should be equally important.

Sure, there are a few subfields of computer science where people try to come up with new sorts of applications, but I think this is worthy of much greater emphasis, a different undergraduate program, a different research methodology (perhaps not so "scientific," but more like "art"). Moreover, I suspect that completely different sorts of people would be attracted to this field.

The MIT Media Lab is perhaps the best example of what such a field would look like.

Can one teach "what to implement" any more than an art class can teach "what to paint"? Best for us to teach the theory and tools of computation and then let the world find neat ways to use computers as they already have in countless ways.

--
Posted by Lance to Computational Complexity at 7/21/2006 08:38:00 AM

The permanent of a matrix has a simple form

where A is an n×n matrix, a_ij is the element in the ith row and jth column and the sum is taken over all permutations of {1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.

The permanent of a matrix has a simple form

where A is an n×n matrix, a_ij is the element in the ith row and jth column and the sum is taken over all permutations of {1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.

That game happened a month before. "And the Italians beat the Germans. What is your point?"

"You had said in your weblog that the game would long be forgotten before you came to Prague and I wanted to prove you wrong."

I try to keep my blogger persona separate from my real persona and not talk about the weblog when I have conversations with my colleagues. Occasionally I will start write something down, "Weblog Fodder" I'd say.

Still others bring up the weblog, usually asking the question about how much time it takes (as opposed to say any comments about the content of the weblog). So people will stop asking me, a typical non-technical post takes me about 15 minutes. The key is to not worry about perfection; people forget the silly or sloppy posts and will be very happy to point out any mistakes I make.

Then there are those who want to watch what they say to me because it might show up in the weblog. I try not to embarrass anyone or reveal personal information, but I do get most of my ideas from regular conversations with people. Anything you say to me is fair game.

--
Posted by Lance to Computational Complexity at 7/25/2006 02:05:00 PM

I started graduate school in 1985 as a member of that new-fangled email generation. When I got an email request for a paper, I tried sending a LaTeX file, sometimes getting the response "What am I supposed to do with this? Can't you just send me the paper in the mail?"

But as people became more comfortable with email I got many more email requests for papers, and responding to those requests took some time. When the the web started in the early '90s I set up a page for people to download the papers. I would still get email requests for a while, responding to the request but with a reminder that they could download my papers online. Around 1994, there was a phase shift and I nearly stopped getting any email requests, everyone knew to look for downloads first. Now most researchers put copies of their papers online and shame on those that don't.

I use a now ancient version of bib2html to generate the publications page. It makes for a functional but not very pretty page. I use the same bib file to generate both the webpage and the papers list in my CV.

I tell this story because I made the first major change on my publications page in about ten years. It looks pretty much the same, but I added links in the titles to the official publisher's page for the paper. These pages often give an abstract and if you have permission you can download the "official" version of a paper. If you don't have permission you can still download the unofficial version from my page. The publisher's page also gives you a way to link to an official description of the paper without linking directly to a file, something I like to do when I link to papers in this weblog.

I tried to use DOIs when possible or other permanent links so the links shouldn't go bad. The IEEE and the IEEE Computer Society (publishers of the FOCS and Complexity proceedings) maintain two separate digital libraries with some overlap. When I had the choice I linked to the IEEE-CS version because at the University of Chicago we have access to the IEEE-CS downloads but not the general IEEE.

Many other researchers, for example Salil Vadhan, do far better than me, maintaining their own separate page for each paper and sorting their papers by research area. Those young scientists always showing up their elders.

--
Posted by Lance to Computational Complexity at 7/27/2006 07:56:00 AM

If you see the word "onion" you have normal color vision. If you the word "color" you are red-green color blind.

I have had more official tests that show me fully red-green color blind. I don't see the world in black and white; I don't even have trouble distinguishing red and green. I do see certain color pairs as different shades of the same color: green-brown, blue-purple, red-pink and yellow-orange.

As an undergrad I took a course in computer graphics and they did a demonstration where they showed a colorful picture and then showed three variations where they would turn off one color in each. The instructor said that the original and one of the variations would look the same to a red-green color blind person. Everyone laughed but I went up closely and couldn't tell the two apart.

One day shopping with my wife, she held up two shirts and asked me which one I liked better. They looked identical to me. I claimed she was playing games with me. Now with my knowledge of interactive proofs, I could have tested her: Mix up the shirts behind my back and make her tell me which was which.

My father-in-law is also red-green color blind which means my daughters had a 50% chance of being color blind, a rarity for females. We've tested them and neither is color blind, at least not to the extent that I am.

While color blindness has no cure or fix, it is one of the easiest disabilities to live with. My wife and daughters make sure my clothes match. I have trouble when people give color-coded talks but that doesn't happen often in theoretical computer science. I try to keep colors simple on my own talks and webpages. The Red-Green 3-D glasses don't work for me at all, though the newer polarized 3-D glasses work just fine. I don't usually have trouble at traffic lights but I do have trouble telling blinking red from blinking yellow. If I can't tell from context I just stop, sometimes to the chagrin of the car behind me.

But when I look at art or nature I see one less dimension of colors than most everyone else. I will never know what I am missing.

--
Posted by Lance to Computational Complexity at 7/28/2006 08:03:00 AM

There is some language L computable in time 2^O(n) such that for some ε>0, every algorithm A computing L uses 2^εn space for sufficiently large n.

• ZPP = RP = BPP = P
• MA = AM = NP. In particular Graph Isomorphism and all of statistical zero-knowledge lie in NP∩co-NP.
• S₂P = ZPP^NP = BPP^NP = P^NP
• The polynomial-time hierarchy lies in SPP. As a corollary PH ⊆ ⊕P ∩ Mod_kP ∩ C₌P ∩ PP ∩ AWPP

1. If φ is not satisfiable then all of the ψ_i are not satisfiable.
2. If φ is satisfiable then some ψ_i has exactly one satisfying assignment.

This gives a short list containing many Ramsey graphs. We don't know how to verify a Ramsey graph efficiently so even though we have the short list we don't know how to create a single one. Contrast this to the best known deterministic construction that creates a graph with no clique or independent set of size 2^{(log n)o(1)}.

We also get essentially optimal extractors. Given an distribution D on strings of length n where every string has probability at most 2^-k and O(log n) additional truly random coins we can output a distribution on length k strings very close to uniform. The truly random coins are used both for the seed of the pseudorandom generator to create the extractor and in applying the extractor itself.

One also gets polynomial-time computable universal traversal sequences, a path that hits every vertex on any undirected graph on n nodes. The generator will give a polynomial list of sequences but one can just concatenate those sequences. The hardness assumption above won't put the sequence in log space, though we do believe such log-space computable sequences exist. Reingold's proof that we can decide undirected connectivity in logarithm space does not produce a universal traversal sequence though it does give a related exploration sequence.

There are many more implications of full derandomization including other complexity class inclusions, combinatorial constructions and some applications for resource-bounded Kolmogorov complexity.

--
Posted by Lance to Computational Complexity at 7/31/2006 08:39:00 AM

Actually I don't care, I use Gmail because I like the interface and the ability to read my email on any browser on any internet-connected computer.

Computer scientists take as a given that everyone worries about privacy. But in fact, outside of computer scientists and a few other techophobes, most people don't. Google not only has my email but also my calendar and if they ever started Google Money, my financials as well. Nearly every major and most minor transactions I make leave an electronic trace. With the right passwords on the Internet you can see what products I buy, what books I read, what movies I rent. So what?

Best as I can tell worries about privacy come from an inflated notion of self-worth. In reality nobody really cares about your private information. The safeguards we have against privacy, while far from completely secure, are enough to deter people for looking for information that just isn't that valuable. Damage will come from people writing in the open; Something someone is writing in their Myspace account today will come back to haunt them thirty years from now when they run for public office.

I do worry about my information online. I worry that people will could delete my files, assume my identity or steal my assets. However I have the ultimate protection against privacy concerns: If you look very carefully at my email, my calendar, the web pages I visit and the stuff that I buy, you'll truly discover that I'm just a really boring person.

--
Posted by Lance to Computational Complexity at 8/01/2006 06:44:00 AM

• Primes in P, Manindra Agrawal, Neeraj Kayal and Nitin Saxena
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Mark Jerrum, Alistair Sinclair and Eric Vigoda.
• Graph Minors. XX. Wagner's conjecture, Neil Robertson and Paul Seymour.

I disagree with Luca and Oded on awards. While theory is a team sport, we do like ways to recognize the very best work and individuals in our field. And awards get us talking about the best work. Even when we don't agree with the winners, the discussions that follow help us understand what we think is important.

By the end of the month we'll know the winners of the Fields Medal and the Nevanlinna prize. The excitement mounts.

--
Posted by Lance to Computational Complexity at 8/02/2006 12:37:00 PM

A Sudoku game is a 9x9 board partially filled out with numbers 1-9.

The goal is to fill out the rest of the board with numbers 1-9 such that every row, column and the 3x3 sub-boxes all have exactly one of each digit in them.

Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol.

Paula goes to a different room than Victor and chooses a random permutation σ of {1,…,9} say σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7 and σ(9)=3. Paula then permutes the solution using σ as such.

Paula then puts each entry into a lockbox (which can be implemented using cryptographic assumptions) and gives the lockboxes to Victor.

Victor can make one of 28 choices.

1. Choose one of the rows.
2. Choose one of the columns.
3. Choose one of the sub-boxes.
4. See the permuted version of the original puzzle.

Victor will accept if all of the digits in the row appear exactly once. Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question.

If Victor picked the last choice Paula would reveal

Victor accepts if this is really a permutation of the original problem. Since the permutation σ is chosen at random again Victor learns nothing about the solution from this question.

Why should Victor now be convinced that a solution exists? If there was no solution, Paula could not find a permutation that causes Victor to accept for all of his 28 choices for the permuted puzzle is just the original puzzle in disguise. If Victor makes his choice at random then he will catch a cheating Paula with probability at least 1/28.

That still gives Paula a possible 27/28 chance of cheating. So repeat the protocol 150 times, each time Paula throws away the unused lock boxes and chooses a new permutation. Paula's chance of cheating in every round is at most (27/28)¹⁵⁰ < 0.5%.

Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.

--
Posted by Lance to Computational Complexity at 8/03/2006 03:10:00 PM

The same advice holds for proving theorems. When trying to prove a difficult result, particularly a well-studied open question, it often seems some evil deity finds ways to foil your many proof attempts just as they almost seem to work. Don't give up. Remain optimistic that you can prove this theorem and keep the patience trying new approaches even as each approach gets cruelly shot down. Only when you've exhausted all of your ideas should you move on to the next result.

Over the years I have kept my optimism about proving a result, but I haven't had as much patience as earlier in my research career. Partly because as one gets older one gets more non-research responsibilities both at the university and in the community, though this is more an excuse than a reason. I also find it more difficult these days to focus on a single problem for hours or days at a time.

Let this be a lesson to young researchers. Don't worry that the older famous researchers have not solved the big open questions; most (but not all) do not have as much patience to focus on a problem and explore as many of the possible proof techniques as well as you can.

--
Posted by Lance to Computational Complexity at 8/07/2006 09:56:00 AM

But I'm not a physicist or an engineer and suppose we can overcome these obstacles and actually build a working machine. Then I can imagine the following conversation in 2025:
Quantum People: We now have a working quantum computer.
Public: Yes after 30 years and 50 billion dollars in total funding. What can it do?
Q: It can simulate quantum systems.
P: I'm happy for you. What can it do for the rest of us?
Q: It can factor numbers quickly.
P: Yes, I know. We've had to change all of our security protocols because of your machine. Does factoring have any purpose other than to break codes?
Q: Not really. But we can use Grover's algorithm for general search problems.
P: That sounds great! So we can really solve traveling salesperson and scheduling problems much faster than before?
Q: Not exactly. The quadratic speed-up we get from Grover's algorithm isn't enough the offset the slow-down by using a quantum computer combined with error correction. But we can solve Pell's equation, approximate the Jones polynomial and a few other things very quickly.
P: Are those algorithms particularly useful?
Q: No.
P: They why did you build a quantum computer?
Q: Because we could.

--
Posted by Lance to Computational Complexity at 8/08/2006 11:26:00 AM

Truth be told, the beginning of the missile season was a surprise for us all. It is true that enough people can claim to have seen it coming, but there was nothing special or expected in the date it started. One day it was business as usual at the Technion and the next day it wasn't.

Haifa has it better than most of northern Israel. We need to stay indoors at all times, and go to the reinforced rooms when we hear the alarm several times a day (our faculty building has a couple of such rooms in every floor, as any post-1992 building is required to have in Israel). Haifa gets hit with actual missiles several times a week—my father told me that it is not unlike the air-raids on Tel-Aviv that he remembers from the 1948 independence war. There are cities to the north that have it much worse, in which life over ground has practically ceased.

All academic interaction with undergraduate students has stopped, as having a concentration of so many people under one roof is deemed to be an uncalculated risk. There will be much work to do when the aborted semester-end tests are resumed and shoe-horned into what is left of the schedule. For graduate student the decision is more personal. Some of them have joined the masses of Haifa residents that have left town (parking space in Haifa has never been so abundant), and others have stayed. A good many of the undergraduate and graduate students (including one of mine) have been called to active reserve military duty, and we all hope they will come back safely.

Faculty members have faced a decision similar to that of the graduate students. Some have taken their work elsewhere (August is considered a good month for academic visits and traveling also in peaceful years), and others like me have stayed. Research at the Technion has not stopped. Thinking is turning out to be possible also in varied settings, and where needed email is taking the place of personal communication. It is not the same as when the hallways were lively with people, but research is done and you can expect good things from the Technion in the upcoming conferences.

--
Posted by Lance to Computational Complexity at 8/09/2006 08:32:00 AM

I have written about prediction (or information markets) before. Consider some future binary event like whether Hillary Clinton will be the democratic nominee for president in 2006. One can create a security 2008DEM.NOM.CLINTON that pays off $100 if Clinton wins the nomination and $0 if she doesn't. Then allow trading on the security including selling short. The price of the security will correspond to the probability that the event will occur, and studies have shown that these probabilities predict better, in general, than experts and polls. Tradesports has such a security on Clinton and the price as I write this for 2008DEM.NOM.CLINTON is 41.9 indicating Clinton has a 41.9% chance of winning the nomination.

Tradesports had another security N.KOREA.MISSILE.31JUL that would pay off if North Korea launces a test missle that leaves North Korean air space by July 31. As you might remember, North Korea did fire test missles on the fourth of July. So it seems like the security N.KOREA.MISSILE.31JUL should have paid off at $100.

Here's the rub. The fine details of the contract required that the US Department of Defense verify that the missiles left North Korean air space. Tradesports couldn't get the verification so they expired the security at $0.

Those who predicted the North Korean missile launch lost real money on a technicality which risks the accuracy of these markets. They no longer predict whether a launch occurs, just whether the DoD would acknowledge it.

More from Smart Money, the Freakonomics Blog and full details and opinions by Chris Masse.

--
Posted by Lance to Computational Complexity at 8/10/2006 10:42:00 AM

I get to experience the new airline rules, no water, toothpaste, gels and liquids of most any kind. The US government is being a bit over reactive but they were only two possibilities

• They can over react to the news and cut back restrictions later as they can more accurately understand the risk factors.
• They can possibly under react where the world learns about a new method to attack planes and the US doesn't try to prevent that new threat.

Unfortunately I come back to news of a loss of a young member of the complexity community. Mikhail Alekhnovich died in a white-water rafting accident in Russia on August 5. Misha, who just finished his first year as an assistant professor at UCSD Math, had some very deep results in theory, most notably in propositional proof complexity.

Misha did his postdoctoral work at the Institute for Advanced Study and the IAS theory page has more on this tragedy.

--
Posted by Lance to Computational Complexity at 8/20/2006 07:12:00 AM

The Editors have been concerned about the price of Topology since Elsevier gained control of the journal in 1994. We believe that the price, in combination with Elsevier's policies for pricing mathematics journals more generally, has had a significant and damaging effect on Topology's reputation in the mathematical research community, and that this is likely to become increasingly serious and difficult, indeed impossible, to reverse in the the future.

As you know, we have made efforts over the last five to ten years to negate this effect. When the alternative subscription option was introduced a few years ago (electronic access combined with annual print delivery for half the regular price), we were hopeful that it would help in this regard. However it made little impact, probably because most university libraries which subscribe to Topology do so through consortia deals.

Also the year-long Information and Computation experiment opening up online access to issues since 1995 concluded last week. Current Elsevier theory journals editor Sweitze Roffel writes

A look at the preliminary results reveals the following:

• We have seen an increase in article downloads for the journal, interestingly both from subscribed and non subscribed users.
• Some of the increase appears to result from systematic downloads, potentially from automated crawlers or from a few locations downloading many articles.
• There seems to be a relation between press coverage and usage.

To quantify and qualify these preliminary results, understand their implications, and develop recommendations, we need to perform detailed analyses. Over the next three months, I will oversee an analysis by Elsevier of the complex and diverse information generated by this experiment and will subsequently share the results and methodologies fully.

Further review of this experiment, which we hope to conduct in close collaboration with the Editorial Board, should then determine actual lessons learned and suggest future actions to be taken for Information and Computation and possibly other journals.

Elsevier is committed to such a collaborative, factual approach to testing, learning, and implementing publication methods and policies that serve the academic community, while remaining commercially sustainable. This approach has successfully led, for example, to our new and more liberal copyright policies, our responses to the concerns of funding agencies, and our sponsored articles initiative. Elsevier wants to deliver demonstrable, innovative, and sustainable benefits to the scientific and other communities it serves.

From the press release:

Jon Kleinberg's work has brought theoretical insights to bear on important practical questions that have become central to understanding and managing our increasingly networked world. He has worked in a wide range of areas, from network analysis and routing, to data mining, to comparative genomics and protein structure analysis. In addition to making fundamental contributions to research, Kleinberg has thought deeply about the impact of technology, in social, economic, and political spheres.

The Fields Medals go to Andrei Okounkov, Grigori Perelman, Terence Tao and Wendelin Werner. Perelman as expected for his work on the Poincaré Conjecture. Terence Tao played a role in work on Gowers Uniformity as well as many other areas of mathematics.

Finally Kiyoshi Ito wins the first Gauss prize for Applications of Mathematics.

Luca is in Madrid and has the on-site ICM perspective. According to Luca, Perelman has declined the Fields Medal.

--
Posted by Lance to Computational Complexity at 8/22/2006 07:41:00 AM

From the latest CACM, a short article describing a wiki set up by the ACM Health of Conferences Committee to discuss best practices for running conferences. As I write this the wiki is empty, a victim of spam attacks.

The article mentions several selected ideas for computer science conferences in general with some of my TCS oriented viewpoints.

• Accepting More Papers. What is the right acceptance rate for a conference? The article suggests 20-30%, about where we have it for many theory conferences. We don't focus so much on acceptance rates, it tends to happen automatically. If we add more talk slots, then more people tend to submit.
• Visionary Venues. Showcasing papers that present more farsighted or creative ideas. Some theory conference have informal rump and open problem sessions. Should we do more?
• Author Responses (Rebuttals). Allow the authors to provide the program committee responses to reviewers concerns. In my opinion this will add too much to the reviewing time and if the authors cannot properly express their ideas, they can update their paper for the next conference.
• Competitions. For example the Electronic Commerce conference runs competitions on various automated trading strategies. Not particularly applicable to theory conferences.
• Tracking Reviews. Passing reviews on a paper from one conference to another. Sounds too complicated for us since we have so many different overlapping conferences.
• Two-Phase Reviewing. Some conferences have introduced a two-phase review process where papers with an obvious bug, obviously non-novel or out of scope are rejected with a less rigorous review than those that are competitive. This happens already in theory conferences as it is much easier for us to separate the wheat from the chaff.
• Double-Blind Submissions. Keeping authors and/or reviewers anonymous.
• Hierarchical Program Committee. Theory conferences still aren't large enough to warrant this structure.
• Co-Located Workshops. Helps boost attendance with more focused programs. We should also have more joint conferences, even just two in the same location as well as the occasional monstrous FCRC.

You can watch the ICM invited and prize winning talks here, both live and archived. Speakers of note include Terence Tao, Avi Wigderson (the first two talks of the third session) and, of course, Jon Kleinberg (last talk of the fifth session). Avi has a paper to go with his talk.

On a lighter note watch Stephen Colbert's take on the Fields Medal by clicking here then here.

(Thanks to Lenore Blum and Bill Gasarch for the pointers above.)

In other science news, Pluto is no longer a planet. Everything I learned in grade school was a lie.

--
Posted by Lance to Computational Complexity at 8/24/2006 03:23:00 PM

Kuperberg's software also produces a large number of open questions, finding the most and least likely open relativizable containments.

Go through the list of open questions and you will find some problems that follow from known results. Let Greg know and he will update his program, which of course might list other known "open" questions, but this process must converge in a finite amount of time.

You can also find some interesting open questions you might not have thought about and you'll also find a number of long-standing open questions.

But mostly you will find problems that just don't look that interesting. Why? Kuperberg's software treats complexity classes as syntactic objects, all of equal importance. But every class has a story, invented for a reason such as to capture an interesting computation model, to understand the complexity of some real world problems, or just to help us understand the relationship of other classes. Many classes get less interesting over time because the reasons we invented them have changed. Comparing two classes developed in very different contexts, say quantum classes and crypto-based classes, doesn't give us much insight unless the classes are extremely common. Finally in most cases we expect a separation and usually one gets little credit for the effort to create an oracle to get a separation we already expected.

--
Posted by Lance to Computational Complexity at 8/28/2006 07:58:00 AM

Last night Paul Beame presented a new paper by Thomas Holenstein that simplifies and improves part of Ran Raz's proof of the Parallel Repetition Theorem, one of the more complicated arguments in computational complexity. The new result replaces roughly Section 6 of Raz's paper with a new embedding argument (Holenstein's Lemma 8), a way for two players to usually agree on the outcome of a distribution where they both have approximations of the distribution, using only shared randomness and no other communication.

Paul did take nearly an hour sketching Raz's proof (with a little help from Ran who was in the audience) before he could even describe Holenstein's contribution so we don't yet have a simple version of the parallel repetition theorem, but it has become much simpler than before.

--
Posted by Lance to Computational Complexity at 8/29/2006 08:21:00 AM

Toni Pitassi and Russell Impagliazzo highlighted a small sample of Misha's great work in proof complexity. Toni focused on automizability, given a proof system like resolution or DPLL (backtracking), how hard is it to find a proof not much larger than the original proof. Misha and his co-authors showed you cannot find

• Resolution proofs with a nearly linear factor larger than the smallest possible proof unless P=NP. (JSL 2001)
• Resolution proofs within a polynomial of the smallest proof size unless W[p] is fixed-parameter tractable, which implies SAT can be solved in time 2^εn for some ε<1. (FOCS 2001)

Russell talked about the problem of showing lower bounds for DPLL algorithms. Alekhnovich, Hirsch and Itsvkson showed that certain randomly generated satisfiable formulas cannot be solved by certain kinds of backtracking algorithms (ICALP 2004). The 2005 Complexity paper showed lower bounds even when allowing arbitrary pruning of the search tree. Work on strengthening this later paper was an ongoing project when Misha passed away.

When we lose our colleagues at or near the end of their careers we celebrate what they have given to our field. When we lose them early, like Alekhnovich at 28, we also regret what might have been. He would have continued his great research career as well as about to start a new phase in his personal life with a wedding in Russia planned for just next week. His loss still deeply affects many at this workshop.

--
Posted by Lance to Computational Complexity at 8/30/2006 07:48:00 AM