The Next Women in Theory Workshop

I would like to pass along the following piece of information that I received from Tal Rabin: the next bi-annual Women in Theory Workshop will be this May 28-30, 2014, in New York City, immediately preceding STOC 2014, which will also take place there.

Applications are due by January 20, 2014.

The relevant information is at

New York in Grainy Pictures

My three months in New York are over, so no more xiaolongbao at Yeah Shanghai, long rides on the New Jersey Transit trains, seminars on additive combinatorics, and hot pot at Minni’s Shabu Shabu for me.

The other night, the traffic information board on 110th and Amsterdam was saying “CCCOOORRR… FFFFFF… AAAUUUU” which is how I too felt about the weather.

This is probably meant to lure in Italian tourists

The Apple store on 5th avenue open at 2:40am (and through the night), because it’s never too late (or too early) to buy an iPhone

In the Canal stop of the N-Q-R-W. There were no signs in other languages.

I agree, it’s good.

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.”) It never ceases to amaze me 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.