Dead-blogging FOCS’2007
For the past few days I’ve been at FOCS’2007 in Providence, Rhode Island, where apparently I’m supposed to have been live-blogging the conference. This came as news to me. (One of the organizers wrote to ask if I’d be posting live updates. I replied that I might post something eventually.)
The trouble is, I still have tons of “backblog” from my previous trip to Latvia and Germany. And so, in the hopes of someday catching up, without further ado I hereby post some photos from Europe.
Sure, I support moderate-to-liberal Democrats … as a temporary measure until zee vorkers take over zee vorl’ [laughs maniacally]
(The above photos were taken in an underground bunker a couple hours from Riga, which the Soviets secretly built in the 70’s, and to which top Communist party officials planned to retreat in case of a nuclear war. Of course, no provisions were made for the rest of the population. Apparently the Soviets built shelters like these all over Latvia. Most of them were converted to bowling alleys or library storage space, but one was preserved for tourists.)
My gracious hosts in Latvia: longtime colleague (and sometime Shtetl-Optimized commenter) Andris Ambainis, Andris’s Ambai-niece Ilze, and Ilze’s husband Girts.
When I think about Munich, Germany, so many mental associations spring immediately into my mind: the fine baroque architecture, the nearby Bavarian alps, the freshly-baked pretzels that are a Munich specialty, the open spaces perfect for rallies and demonstrations of all kinds — but most of all, of course, I think of Oktoberfest! Here you see me drinking genuine bier served by a genuine bier wench (not pictured) with my gracious hosts from the Max-Planck-Institut für Quantenoptik: Norbert Schuch, Ignacio Cirac, and Michael Wolf.
Follow
Comment #1 October 23rd, 2007 at 9:26 pm
I hope you drank more bier than these germans, to not make us look bad. Rule #1 when in foreign lands: always drink the locals under the table.
Comment #2 October 23rd, 2007 at 11:14 pm
Scott, what does a certificate look like for “yes” answers to CoNP-complete problems? Or better yet are there any guidelines for establishing whether a certificate is acceptable, certain properties it needs to conform to? How would we show, for example, that the problem of Verifying a certificate for CoNP-complete problems is itself NP-Complete if we don’t have an accepted certificate to work with? Or is there a certificate and i just didn’t find any text on it?
Comment #3 October 24th, 2007 at 6:04 am
Job, I don’t quite understand what you’re asking, but let’s see if the following is helpful.
We say a problem has polynomial-size certificates if there’s a polynomial-time algorithm V such that for every problem instance φ,
(i) if the answer is “yes” then there’s at least one polynomial-size string w such that V(φ,w) accepts, and
(ii) if the answer is “no” then there’s no w such that V(φ,w) accepts.
(This is also the definition for a problem being in NP. Thus, coNP-complete problems have polynomial-size certificates if and only if NP=coNP — which is considered extremely unlikely, almost as unlikely as P=NP.)
Notice that the definition of a certificate is just anything that causes V to accept! The reason this definition is reasonable is that we stipulated that if the answer is “no” then nothing can cause V to accept. The two requirements — that some certificate should cause V to accept a “yes” instance, and that no certificate should cause it to accept a “no” instance — are called completeness and soundness respectively.
I’m guessing what you really want to know is this: in practice, how do people go about proving that a Boolean formula is unsatisfiable? Well, one way is just to list all 2n possible satisfying assignments and show that none of them work! But there are entire fields — called proof complexity and automated reasoning — devoted to coming up with better ways. One example of a better way is what’s called a resolution proof, which basically involves smashing together clauses (“resolving” them) until you reach a contradiction. You can then conclude that the original formula must have been unsatisfiable.
In practice, many unsatisfiable formulas have short resolution proofs — but alas, Haken proved in the 80’s that some unsatisfiable formulas require exponentially-long resolution proofs.
If you come up with a proof system where the proofs of unsatisfiability always have polynomial size, you’ll have shown NP=coNP. And if you show furthermore that the proofs can always be found efficiently, you’ll have shown P=NP.
Comment #4 October 24th, 2007 at 6:22 am
I’ve never liked the term ‘live-blogging’. I mean, the medium is fundamentally non-live, so there’s no way you can make it live. Live streaming video, sure, but not live blogging. The first time I heard the term, I thought there was some new technology I hadn’t heard about, like maybe you could see the characters being typed out as the blogger types the post.
Comment #5 October 24th, 2007 at 9:33 am
James,
Since electrons, photons, and fingers all travel with finite velocity, even seeing the characters being typed out is significantly delayed from the events as they occur. In fact, even if you are in the vicinity of the events there is some brief but quantifiable delay in your perceiving them. I suggest that there is not only no such thing as live-blogging, but that there is no live-anything at all!
Comment #6 October 24th, 2007 at 9:36 am
Maybe we should set up a wiki for live-blogging. Anybody at the conference with the spare time and inclination could write (non-anonymously) about whatever talks they liked.
Comment #7 October 24th, 2007 at 10:20 am
You could blog what you expect the next sentence to be. Predictor-corrector coding, and constant updating of parameters, can make this quite accurate. Given the research of Libet et al. on how the human brain codes muscle commands some 200 milliseconds before the person is aware of the intent, combined with SQUID neuromagnetometry, could allow accurate anticipation by the speakers themselves of 1/5 second. I suspect that when direct brain-computer interfaces allow one to type 200 milliseconds before one is conscious of the content that one is typing will lead to weird stream-of-consciousness problems associated with breaking the Deja Vu Barrier. The greatest benefit may be anticipatory control of teleoperators out to 1/5 Light Second which, in particular, includes Clarke orbit.
Comment #8 October 24th, 2007 at 12:30 pm
Scott, I saw in your notes that if P != NP then maybe CoNP = NP or maybe CoNP != NP. I was thinking that even if we can’t establish anything concrete on CoNP vs NP vs P, we might be able to show that CoNP != NP iff NP != P, by showing that the problem of verifying a “yes” answer for CoNP-Complete problems, given a proof string w, is at best NP-Complete. But to define the problem formally i was looking for a concrete (and maybe minimal) definition for w (where w is of polynomial size), or wondering if an accepted such w had already been used.
I apologize for the hijacking.
Comment #9 October 24th, 2007 at 12:57 pm
Job: As you seem to realize, your question is poorly defined — since the meaning of w depends entirely on what proof system we’re talking about, and what sorts of proof systems are possible is the whole essence of the NP vs. coNP question!
To show that NP=coNP implies P=NP seems far, far beyond our current abilities — indeed, almost as hard as NP vs. coNP itself! You would need to show that any efficient proof system for coNP is “automatizable” — i.e. that the proofs can actually be found in polynomial time. Certainly any proof of this would have to be non-relativizing, and I think non-algebrizing as well (will have to check though). It’s not, repeat not, some simple observation that everyone’s overlooked.
Comment #10 October 25th, 2007 at 11:20 am
I’m the culprit. Sorry about that. One live-blogger is enough anyway and Nicole did a very thorough job. I can still ask the webmaster to remove your name from the website, if you care?
Comment #11 October 25th, 2007 at 1:13 pm
Claire: Don’t worry about it. 🙂