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.
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.
posted by Luca at 4:06 PM
11 comments
