This work is licensed under a
Creative Commons License.
|
Friday, January 30, 2004
A Little TheoremHere's a simple result I have seen several times recently, a bit surprising when you first see it.
Theorem: co-NEXP is in NEXP/poly.
NEXP are the languages accepted in nondeterministic time 2poly(n). A language L is in C/poly for a complexity class C if there is a language A in C and a list of strings a0, a1, ... with |an| bounded by a polynomial in n such that x is in L if and only if (x,a|x|) is in A.
I don't know who first showed this theorem and since the proof is rather simple it may have never been published. Let K be a complete set for NEXP and the polynomial length advice an for strings of length n is just the number of strings of length n in K. To nondeterministically check that y of length n is not in K, just guess an strings other than y of length n and verify they are in K.
This kind of result does not likely hold for NP. Yap shows that if co-NP is in NP/poly then the polynomial-time hierarchy collapses to the third level. This theorem above does not imply co-NEXP has subexponential nondeterministic circuit since exponential circuits might be required to describe the exponential computation.
Harry Buhrman noticed you can strengthen the result to show that EXPttNP is in NEXP/poly where EXPttNP are the set of languages nonadaptively reducible to an NP set in exponential time.
4:13 AM # Comments []
Wednesday, January 28, 2004
The Defense, Part IIHein Röhrig successfully defended his Ph.D. thesis at the University of Amsterdam yesterday. The Dutch thesis defense reminds me most of a traditional American wedding. The defense takes place in a chapel. The players include the defender (Röhrig), two paranimf (the groomsmen role), the promotor (advisor, in Röhrig's case two promoters: Harry Buhrman and Paul Vitányi), a Pedel (an official position in the university now held by a woman; she plays a master of ceremonies role) and eight opponents (including myself). The defender and paranimf are in full tux and tails, the Pedel and full professors in academic gowns and the other opponents in suits. In the audience are the defender's friends and family.
The ceremony starts by the defender giving a short description of this thesis to the audience from a Podium in front of the chapel. Led by the Pedel, the promotors and opponents enter the chapel from the back and march to sit in the choir seats. For forty-five minutes the opponents, one at a time, ask hard questions to the defender about his thesis. At the end the Pedel reenters the chapel marches to the front, hits her staff on the ground and says "Hora Est" (Time has expired). The opponents and promotors march out of the chapel to a discussion room where we vote on the defense and sign the thesis. We march back in, present the diploma where the promoters read some traditional text and give a short speech.
The ceremony is followed by a receiving line and reception with dinner later on.
Call me a romantic but I truly enjoy the pomp and circumstances that accompany the Dutch defense sorely lacking in the American counterpart.
Update 1/30: Pictures from the defense are now available.
2:50 AM # Comments []
Monday, January 26, 2004
Howdy from AmsterdamI have returned to Amsterdam for the week. I did my sabbatical in Amsterdam seven years ago and I always enjoy the visit. Yesterday I saw the soccer team Amsterdam Ajax beat NEC (the team from Nijmegen, not my previous employer). Today I am visiting CWI, the Dutch math and computer science institute in the group of Harry Buhrman (my most prolific co-author) and Paul Vitányi (who co-wrote the book on Kolmogorov complexity).
Also visiting CWI is Kolya Vereshchagin from Moscow. I had an interesting idea about Kolmogorov complexity but Vereshchagin had the same idea weeks ago. Hate when that happens.
Tomorrow is Hein Röhrig's Ph.D. defense. Hein always wanted me to mention him in this weblog having mentioned both of his officemates, John Tromp and Ronald de Wolf, before. So here is my graduation present to Hein.
11:21 AM # Comments []