Dumplings, zeppole, and "vegetables"

Yesterday, Gowers was in Princeton to give a fascinating talk about quadratic Fourier analysis, an event that it would be worth reporting on. And on Monday Ahmadinejad was at Columbia to deliver his comic routine, not quite managing to keep a straight face when, asked about the death penalty for homosexuality in Iran, he said "we don't have homosexuals in Iran, I don't know who told you that" (go to 3:40 in the video).

But that's not what I am going to talk about, because I realize I haven't written in a while about the favorite topic of most readers.



Last Sunday I was on my third trip to Chinatown for xiao long bao (above) and it happened to be the last day of the Feast of San Gennaro in nearby Little Italy. San Gennaro is the patron saint of Naples, known for "The Miracle." A vial supposedly containing the dried blood of the saint is kept in the Naples cathedral, and brought out a few times a year, when it usually liquefies during the mass. The phenomenon has been replicated with various substances, but it's unclear what exactly is in the vial.

In New York, the San Gennaro festivities run for nearly two weeks, and close off several blocks of Mulberry street.



Many stands sold zeppole (fried dough), which looked appetizing, if not sanitary. Other stands sold stuff that looked neither appetizing nor sanitary.



Here is the border of Chinatown and Little Italy. Note the "Birra Moretti" umbrellas in front of the store with the yellow awning.



Finally, as an illustration of the difference between the "for all" and the "there exists" quantification, here is an excerpt from the menu of the Indonesian restaurant next to the Birra Moretti place.

The long-distance commuter

I am spending this semester as a member of the Institute for Advanced Study and a visiting professor at Princeton University, while living in New York and planning to spend some time at NYU and Columbia as well. Though this has no relation to my case, a friend once explained to me that the key to not having to do any work is to have (at least) two affiliations and two offices. When you are not at one place, people will think you are working at the other place and vice versa.

I haven't been to New York much ever since moving out about seven years ago, and I am sure much has changed, most dramatically in the East Village. Hopefully, even as I work very, very hard, I will have time to explore the city again.

Meanwhile, night and weekend repairs in the 1-2-3 lines cause bizarrely complicated (and largely unannounced) schedule changes. To take a local uptown train from 14th street, for example, one goes to the uptown express track (there is no sign to this effect, only word of mouth). Apparently (I haven't tested it) if one wants to go from Columbia to, say, South Ferry, one starts by going on a train that has a sign on the side that says "South Ferry." Then one changes to the 2 or 3 express line before 14th street, while, of course, waiting for it on the local track. Then one gets down at Chambers, from which one finds a shuttle bus that will do all the stops of the 1 train until South Ferry. (Reminds me of the instructions given in the first minute of this hilarious Monty Python sketch -- Note: after the first minute, the sketch keeps being famously funny, but is not, as they say, "work safe.")

Once one finds the right train, it's always impress how full the subway can be, and how safe it feels, at 3am or even 4am (to be fair, the MUNI too, in San Francisco, would probably be full around 2-2:30am, if it didn't stop running at midnight).

Yesterday I found my way to Princeton and attended Scott's talk on "algebrizing" proofs. The proof of a complexity result is algebrizing if it satisfies a certain property, all known non-relativizing and non-natural lower bound proofs are algebrizing, and an algebrizing proof cannot settles the P versus NP question.

Long ago, Goldreich, Micali and Wigderson proved that the existence of commitment schemes implies that every problem in NP has a computational zero knowledge interactive proofs. (I'll refer to this result as the GMW theorem.)

Among the issues raised during and after Scott's talk was the fact that the GMW theorem does not relativize, nor, probably, does it "algebrize." Indeed, it seems impossible to abstract the known proofs of the GMW theorem to any model except one in which NP witnesses can be verified via a series of "local" checks, and, essentially, this property characterizes NP in the real world. (Similar issues arise when thinking about the PCP theorem, see this paper for an exploration of the issue of local checkability in non-relativizing proofs.) So one goes back to a question that has surfaced every now and then in the past twenty years: is there a model or a class of proofs where one can prove that commitment schemes imply NP is in CZK, but in which the P versus NP question cannot be settled?

Relative to a PSPACE oracle, the statement of the GMW theorem is vacuously true (because commitment schemes do not exist) and P=NP (so that P$\neq$NP is unprovable), so one cannot just use the statement of the GMW theorem plus relativizing techniques to prove $P\neq NP$, but this is quite far from a satisfactory answer.

Open Access Publishing is Censorship

To take a break from controversies, let's talk about something we can all agree about: Elsevier is evil.

Consider the following business model: people make a product for free (sometimes even contributing money to it) and said product is then sold to them. This is like Kramer's idea of the make-your-own-pizza pizzeria, which actually wasn't so crazy - I certainly like to cook my own meat in a Korean barbecue place or in a restaurant that offer Beijing hot pot - mmh... Beijing hot pot ... - but I am being led astray by the thought of food, and, back to my point, it is also how for-profit publishing of academic journals works. It used to be that academic publishers performed a number of useful tasks, such as typesetting the articles, but now typsetting is done by the authors themselves, and all the work that goes into producing an academic journal, the editing, the peer-reviewing, and of course the actual research and writing-up, are done for free by the academic community. To add insult to injury, it was common for authors to have to give up all rights about their work to the publisher, so that the authors cannot even legally keep a copy of the paper posted on their page except as a link to the publisher's version, often not freely available. (Such policies have changed at many journals because of the increased restlessness of the acadmic community.)

A few years ago, Don Knuth conducted a thourough analysis of the subscription rates of academic journals, and invited fellow editors of the Journal of Algorithms, published by Elsevier, to resign en masse and to create a new journal, the ACM Transactions on Algorithms that, while not free, is published by a not-for-profit professional society and has considerably lower subscription rates. Earlier, the editors of Kuwler's Machine Learning Journal similarly resigned en masse to join a new journal with friendlier policies toward the community. Such actions have become more and more common.

Within theoretical computer science, Elsevier's journal have been often targeted as the worse offenders, with reactions ranging from the mentioned killing of the Journal of Algorithms to the decision to stop publishing special issues of STOC, FOCS and CCC in Elsevier's Journal of Computer and System Sciences. Elsevier's reaction to the community's backlash was also disappointing, with proposals to introduce compensations for editors and reviewers, rather than to reduce subscription fees and to open the online archives. (Except tentatively, like the "experimental" opening of the Information and Computation archives.)

Then there was Elsevier's participation in the international arm trade, which is going to end this year after a strong campaign initiated in the health sciences. (See for example the open letter of the editors of Elsevier's Lancet.)

Now I read that a group of publishers, which includes Elsevier, has hired PR consultant Eric Dezenhall who, according to his wikipedia biography, helped Exxon have Greenpeace audited by the IRS, and helped Enron discredit the initial whistleblower. One of his talking points about for-profit publishing will be that open access publishing equals government censorship. How, exactly? Read the Nature article.