Computational Complexity

Here'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...

Hein Röhrig successfully defended his Ph.D. thesis at the University of Amsterdam yesterday. The Dutch thesis defense reminds me most of a t...

I 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 ...

A couple of quick notes. The list of accepted papers for the upcoming STOC conference has been posted. The most intriguing looking pape...

You've taken your classes, passed your preliminary/qualifying exams, done your research and written your thesis. What stands between yo...

[From Chris Fuchs] Dear friends in the quantum information and foundations communities, Many of you may not know it, but the concept o...

On my vacation I read Dan Brown's The Da Vinci Code , a very popular book I received recently as a gift. Warning: Minor spoilers follo...

Thanks to Scott Aaronson for covering for me last week. If you've enjoyed the last week, check out more of his writings . Maybe the w...

Sir Lance-lot has returned, and tomorrow will reclaim his fortress from this barbarian invader. He writes: "Thanks for blogging for me...

OK, now Mars. I'm sure you've all read about the dramatic successes of the Spirit rover, which incidentally raise two computer scie...

Sorry I haven't posted for a while -- QIP has left me with nary an hour to spare. Today Leonard Schulman gave a talk whose title was a...

As my plane descended toward Toronto on Monday, it felt as though I was landing on the surface of another planet (though maybe the Mars rove...

A comment to my last post asked for advice for people interested in getting into complexity research. So here it is. Keep in mind that I...

To prove theorems I need a particular kind of intense concentration, sustained for hours, that I don't need for programming, fiction wri...

Leaving home after the holidays, I said goodbye tonight to my friend since junior high school, Alex Halderman . You might have read about ...

Yeah, I know: PP has already been this weblog's complexity class of the week. But once you've seen how to define PP using super-p...

I'm honored and humbled that Lance Fortnow decided to entrust his weblog to me for the week. Lance's only request was that I obey a...

I off on vacation next week and you will have a guest weblogger, Scott Aaronson, while I am gone. I have confidence Scott will keep you all...

Some interesting science policy quotes courtesy of the American Institute of Physics. Where have the Americans gone? - DOE Office of Sc...

I posted the latest BEATCS Complexity Column, A Survey on Private Information Retrieval by Bill Gasarch. With this article I am retiri...